Subject: [Boost-commit] svn:boost r50016 - in sandbox/SOC/2008/graphs/trunk/libs/graphs: include/boost include/boost/graphs/adjacency_list include/boost/graphs/adjacency_list/ies include/boost/graphs/adjacency_list/incs test
From: asutton_at_[hidden]
Date: 2008-11-29 10:36:44
Author: asutton
Date: 2008-11-29 10:36:43 EST (Sat, 29 Nov 2008)
New Revision: 50016
URL: http://svn.boost.org/trac/boost/changeset/50016
Log:
- Moving some files around
- Implemented the binding of edges to vertices during addtion.
Added:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incs/ (props changed)
- copied from r49983, /sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/ies/
Removed:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/ies/
Text files modified:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/counted_list.hpp | 2
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp | 72 ++++++++++++++++++++++++++-------------
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_store.hpp | 35 +++++++++++++-----
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp | 26 +++++++++++++-
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp | 45 ++++++++++++++++++++-----
sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp | 20 ++++++----
6 files changed, 145 insertions(+), 55 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/counted_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/counted_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/counted_list.hpp 2008-11-29 10:36:43 EST (Sat, 29 Nov 2008)
@@ -118,7 +118,7 @@
{ _list.clear(); _size = 0; }
counted_list& swap(counted_list&& x)
- { _list.swap(x); return* this; }
+ { _list.swap(x._list); return* this; }
counted_list& operator=(counted_list const& x)
{ return swap(counted_list(x)); }
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp 2008-11-29 10:36:43 EST (Sat, 29 Nov 2008)
@@ -151,44 +151,66 @@
make_edge(Store const&, Ends e, Label&& l)
{ return typename edge_store_traits<Store>::edge_type(e, l); }
+ // This is one of the few non-generic components of the library. We're
+ // fixing the ordering of vertices within the end pair as strictly less.
+ // Since descriptors are required to define this operation, we're in good
+ // shape.
+ template <typename Vertex>
+ inline typename std::pair<Vertex, Vertex> order_verts(Vertex& u, Vertex& v)
+ { return (u < v) ? std::make_pair(u, v) : std::make_pair(v, u); }
+
// Just push the edge into the sequence. Since these types support a
- // multigraph, the ordering of endpoints is essentially irrelevant.
+ // multigraph, the ordering of endpoints is essentially irrelevant. This
+ // always inserts so the returned pair is always true.
template <typename Store, typename Vertex, typename Label>
- inline typename Store::iterator
+ inline std::pair<typename Store::iterator, bool>
dispatch_insert(Store& store, Vertex u, Vertex v, Label&& l, sequence_tag)
- { return store.insert(store.end(), make_edge(store, std::make_pair(u, v), l)); }
+ {
+ typename edge_store_traits<Store>::edge_type e =
+ make_edge(store, std::make_pair(u, v), l);
+ return std::make_pair(store.insert(store.end(), e), true);
+ }
- // This re-orders the endpoints before inerting in order to guarantee a
- // canonical ordering edges, and preserving uniqueness, if required.
- // TODO: Is there a way to convert Comp<pair<VD,VD>> to Comp<VD>? Yeah, but
- // it's kind of nasty and uses template template parameters.
+ // Unique associative containers may fail the insertion, returning false
+ // as the second.
+ template <typename Store, typename Edge>
+ inline std::pair<typename Store::iterator, bool>
+ assoc_insert(Store& store, Edge&& e, unique_associative_container_tag)
+ { return store.insert(e); }
+
+ // Pair associative containers always permit insertion.
+ template<typename Store, typename Edge>
+ inline std::pair<typename Store::iterator, bool>
+ assoc_insert(Store& store, Edge&& e, multiple_associative_container_tag)
+ { return std::make_pair(store.insert(e), true); }
+
+ // This matches all associative containers, but we have to dispatch
+ // separately for unique and multiple.
template <typename Store, typename Vertex, typename Label>
- inline typename Store::iterator
- dispatch_insert(Store& store, Vertex u, Vertex v, Label&& l, pair_associative_container_tag)
+ inline std::pair<typename Store::iterator, bool>
+ dispatch_insert(Store& store, Vertex u, Vertex v, Label&& l, associative_container_tag)
{
- // NOTE: Ends must be Pair<VD,VD>. For some reason, writing the expression
- // e.first < e.second tries to open a new template and gives an error
- // about constant expressions.
- std::less<Vertex> comp;
- if(!comp(u, v)) {
- using std::swap;
- swap(u, v);
- }
- return container_insert(store, make_edge(store, std::make_pair(u, v), l));
+ typename edge_store_traits<Store>::edge_type e =
+ make_edge(store, order_verts(u, v), l);
+ return assoc_insert(store, std::move(e), container_category(store));
}
} /* namespace detail */
-/** Insert an edge into the graph. */
+/**
+ * Insert an edge into the graph. If the edge set is uniquely associative, then
+ * this may not insert the edge, and will return a descriptor to the exsiting
+ * edge.
+ */
template <typename Store, typename Vertex, typename Label>
-inline typename edge_store_traits<Store>::edge_descriptor
+inline std::pair<typename edge_store_traits<Store>::edge_descriptor, bool>
insert(Store& store, Vertex u, Vertex v, Label&& l)
{
typedef typename Store::iterator Iterator;
- typedef typename edge_store_traits<Store>::edge_descriptor Descriptor;
-
- // Start by inserting the edge globally. Could be O(1), O(lgE).
- Iterator i = detail::dispatch_insert(store, u, v, l, container_category(store));
- return make_descriptor(store, i, edge_descriptor_kind());
+ typedef typename edge_store_traits<Store>::edge_descriptor Edge;
+ std::pair<Iterator, bool> x =
+ detail::dispatch_insert(store, u, v, l, container_category(store));
+ Edge e = make_descriptor(store, x.first, edge_descriptor_kind());
+ return std::make_pair(e, x.second);
}
/** @name Find Edge
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_store.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_store.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_store.hpp 2008-11-29 10:36:43 EST (Sat, 29 Nov 2008)
@@ -4,29 +4,44 @@
#include <vector>
+// Pull all of the incidence list type selectors
+#include <boost/graphs/adjacency_list/incs/vector.hpp>
+#include <boost/graphs/adjacency_list/incs/list.hpp>
+#include <boost/graphs/adjacency_list/incs/set.hpp>
+
// The incidence store provides a means of selecting different kinds of storage
// mechanisms for the list of incident edges on undirected vertices. An
// incidence store simply contains the edge descriptors that are incident to
// a vertex - nothing more.
+// The incidence store should be more appropriately called the adjacency store,
+// but we're talking about incident edges, not adjacent vertices.
+
namespace boost { namespace graphs { namespace adjacency_list {
-namespace ies
+template <typename Store>
+struct incidence_store_traits
{
+ typedef typename Store::size_type incident_edges_size_type;
+};
-/** Return the size of an adjacency list for the given vertex. */
+namespace incs {
+
+/** Insert an edge descriptor into the incidence store of the vertex. */
+template <typename Store, typename Edge>
+typename Store::iterator
+insert(Store& store, Edge e)
+{ return container_insert(store, e); }
+
+/** Return the size of an adjacency list for the given vertex, its degree. */
template <typename Store>
-inline typename Store::size_type size(Store const& store)
+inline typename incidence_store_traits<Store>::incident_edges_size_type
+size(Store const& store)
{ return store.size(); }
-}
+} /* namespace incs */
-} } }
-
-// Pull all of the incidence list type selectors
-#include <boost/graphs/adjacency_list/ies/vector.hpp>
-#include <boost/graphs/adjacency_list/ies/list.hpp>
-#include <boost/graphs/adjacency_list/ies/set.hpp>
+} } } /* namespace boost::graphs::adjacency_list */
#endif
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp 2008-11-29 10:36:43 EST (Sat, 29 Nov 2008)
@@ -138,6 +138,27 @@
typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor v)
{ return add_edge(g, u, v, typename undirected_graph<VL,EL,VS,ES,IS>::edge_label()); }
+namespace detail {
+ // Specialize the binding of edge descriptors into the vertex by recognizing
+ // that only unique associative containers actually need to test the result
+ // of the insertion before binding.
+ template <typename VS, typename V, typename Ins, typename Tag>
+ inline void bind_edges(VS& vs, V u, V v, Ins ins, Tag)
+ {
+ incs::insert(vs::edges(vs, u), ins.first);
+ incs::insert(vs::edges(vs, v), ins.first);
+ }
+
+ template <typename VS, typename V, typename Ins, typename Tag>
+ inline void bind_edges(VS& vs, V u, V v, Ins ins, unique_associative_container_tag)
+ {
+ if(ins.second) {
+ incs::insert(vs::edges(vs, u), ins.first);
+ incs::insert(vs::edges(vs, v), ins.first);
+ }
+ }
+} /* namespace detail */
+
template <typename VL, typename EL, typename VS, typename ES, typename IS>
inline typename undirected_graph<VL,EL,VS,ES,IS>::edge_descriptor
add_edge(undirected_graph<VL,EL,VS,ES,IS>& g,
@@ -146,8 +167,9 @@
typename undirected_graph<VL,EL,VS,ES,IS>::edge_label&& l)
{
typedef typename undirected_graph<VL,EL,VS,ES,IS>::edge_descriptor Edge;
- Edge e = es::insert(g.e, u, v, l);
- return e;
+ std::pair<Edge, bool> x = es::insert(g.e, u, v, l);
+ detail::bind_edges(g.v, u, v, x, container_category(g.e));
+ return x.first;
}
//@}
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp 2008-11-29 10:36:43 EST (Sat, 29 Nov 2008)
@@ -212,6 +212,28 @@
{ return i->second; }
//@}
+ /** @internal @name Get Edges */
+ //@{
+ // Overload for all stores with edges first in the vertex.
+ template <typename Store, typename Vertex>
+ inline typename vertex_store_traits<Store>::vertex_edges&
+ get_edges(Store& store, Vertex v)
+ { return get_vertex(store, make_iterator(store, v)).first; }
+
+ // Overload for maps - identical to above, but has to be separate because
+ // the cause to get_vertex doesn't appear to return the right type when
+ // instantiated with this specialization.
+ template <typename Key, typename Edges, typename Label, typename Compare, typename Alloc, typename Vertex>
+ inline Edges&
+ get_edges(std::map<Key, std::pair<Edges, Label>, Compare, Alloc>& store, Vertex v)
+ { return get_vertex(store, make_iterator(store, v)).first; }
+
+ // Overload for sets (edges second).
+ template <typename Label, typename Edges, typename Compare, typename Alloc, typename Vertex>
+ inline Edges&
+ get_edges(std::map<Label, Edges, Compare, Alloc>& store, Vertex v)
+ { return get_vertex(store, make_iterator(store, v)).second; }
+ //@}
// Iterate and compare for sequences.
template <typename Store, typename Label>
@@ -375,15 +397,7 @@
{ return detail::get_vertex(store, make_iterator(store, v)); }
//@}
-/** @name Vertex Label
- *
- * @todo There's a problem with vertex_sets that causes the compiler to select
- * a non-const return type and then causes an error because we can't convert
- * the const label to the non-const label. One solution would be to provide an
- * internal overload that casted out the const - this isn't a terribly bad idea
- * since its easily possible that the only part of the label required to be
- * immutable is the part involved in the comparison and sorting.
- */
+/** @name Vertex Label */
//@{
template <typename Store>
inline typename vertex_store_traits<Store>::vertex_label&
@@ -396,6 +410,19 @@
{ return graphs::label(vertex(store, v)); }
//@}
+/** @name Vertex Edges */
+//@{
+template <typename Store>
+inline typename vertex_store_traits<Store>::vertex_edges&
+edges(Store& store, typename vertex_store_traits<Store>::vertex_descriptor v)
+{ return detail::get_edges(store, v); }
+
+template <typename Store>
+inline typename vertex_store_traits<Store>::vertex_edges const&
+edges(Store const& store, typename vertex_store_traits<Store>::vertex_descriptor v)
+{ return edges(const_cast<Store&>(store), v); }
+//@}
+
/** Return the number of elements in the vertex store. */
template <typename Store>
inline typename vertex_store_traits<Store>::vertices_size_type
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp 2008-11-29 10:36:43 EST (Sat, 29 Nov 2008)
@@ -163,15 +163,19 @@
int main()
{
- typedef undirected_graph<node, arc, vertex_vector<>, edge_vector<>, incidence_vector<>> VVV;
- typedef undirected_graph<node, arc, vertex_list<>, edge_vector<>, incidence_vector<>> LVV;
- typedef undirected_graph<node, arc, vertex_set<>, edge_vector<>, incidence_vector<>> SVV;
- typedef undirected_graph<node, arc, vertex_map<int>, edge_vector<>, incidence_vector<>> MVV;
+ typedef undirected_graph<node, arc, vertex_vector<>, edge_vector<>, incidence_vector<>> V_V_V;
+ typedef undirected_graph<node, arc, vertex_list<>, edge_vector<>, incidence_vector<>> L_V_V;
+ typedef undirected_graph<node, arc, vertex_set<>, edge_vector<>, incidence_vector<>> S_V_V;
+ typedef undirected_graph<node, arc, vertex_map<int>, edge_vector<>, incidence_vector<>> M_V_V;
- test<VVV>();
- test<LVV>();
- test<SVV>();
- test<MVV>();
+ typedef undirected_graph<node, arc, vertex_vector<>, edge_list<>, incidence_list<>> V_L_L;
+ typedef undirected_graph<node, arc, vertex_vector<>, edge_set<>, incidence_set<>> V_S_S;
+ test<V_V_V>();
+ test<L_V_V>();
+ test<S_V_V>();
+ test<M_V_V>();
+ test<V_L_L>();
+ test<V_S_S>();
}