|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r49861 - in sandbox/SOC/2008/graphs/trunk/libs/graphs: include/boost/descriptors include/boost/graphs include/boost/graphs/adjacency_list include/boost/graphs/adjacency_list/es include/boost/graphs/adjacency_list/ies include/boost/graphs/adjacency_list/vs test
From: asutton_at_[hidden]
Date: 2008-11-21 14:52:12
Author: asutton
Date: 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
New Revision: 49861
URL: http://svn.boost.org/trac/boost/changeset/49861
Log:
Started rewriting the undirected graph class.
Added:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/list.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/ies/
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/ies/list.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/ies/set.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/ies/vector.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_store.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/index_descriptor.hpp | 13
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/node_descriptor.hpp | 13
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp | 78 +++
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/set.hpp | 11
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/vector.hpp | 7
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp | 771 ++-------------------------------------
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp | 111 +++++
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/list.hpp | 11
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/map.hpp | 19
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/set.hpp | 16
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/vector.hpp | 14
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/edge.hpp | 16
sandbox/SOC/2008/graphs/trunk/libs/graphs/test/CMakeLists.txt | 6
sandbox/SOC/2008/graphs/trunk/libs/graphs/test/edge_store.cpp | 2
14 files changed, 283 insertions(+), 805 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/index_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/index_descriptor.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/index_descriptor.hpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -11,13 +11,12 @@
* The index_descriptor simply maintains the descriptor as an index into the
* given offset.
*/
-template <typename Index, typename Kind = basic_descriptor_kind>
+template <typename Index>
struct index_descriptor
{
- typedef index_descriptor<Index, Kind> this_type;
+ typedef index_descriptor<Index> this_type;
typedef Index this_type::*unspecified_bool_type;
- typedef Kind descriptor_kind;
typedef Index descriptor_type;
inline index_descriptor()
@@ -76,15 +75,15 @@
};
// A hash function for indexed descriptors.
-template <typename Index, typename Kind>
-std::size_t hash_value(index_descriptor<Index, Kind> const& x)
+template <typename Index>
+std::size_t hash_value(index_descriptor<Index> const& x)
{
using boost::hash_value;
return hash_value(x.value);
}
-template <typename Index, typename Kind>
-std::ostream& operator<<(std::ostream& os, index_descriptor<Index, Kind> const& x)
+template <typename Index>
+std::ostream& operator<<(std::ostream& os, index_descriptor<Index> const& x)
{ return os << x.value; }
} /* namespace boost */
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/node_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/node_descriptor.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/node_descriptor.hpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -11,13 +11,12 @@
* container iterator is just a pattern for the actual iterator and has no
* real type (it's opaque).
*/
-template <typename Blob, typename Kind = basic_descriptor_kind>
+template <typename Blob>
struct node_descriptor
{
- typedef node_descriptor<Blob, Kind> this_type;
+ typedef node_descriptor<Blob> this_type;
typedef Blob this_type::*unspecified_bool_type;
- typedef Kind descriptor_kind;
typedef Blob descriptor_type;
inline node_descriptor()
@@ -76,15 +75,15 @@
};
// A hash function for indexed descriptors.
-template <typename Blob, typename Kind>
-std::size_t hash_value(node_descriptor<Blob, Kind> const& x)
+template <typename Blob>
+std::size_t hash_value(node_descriptor<Blob> const& x)
{
using boost::hash_value;
return hash_value(x.value);
}
-template <typename Blob, typename Kind>
-std::ostream& operator<<(std::ostream& os, node_descriptor<Blob, Kind> const& d)
+template <typename Blob>
+std::ostream& operator<<(std::ostream& os, node_descriptor<Blob> const& d)
{ return os << hash_value(d); }
} /* namespace boost */
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-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -2,8 +2,6 @@
#ifndef BOOST_GRAPH_ADJLIST_EDGE_STORE_TRAITS_HPP
#define BOOST_GRAPH_ADJLIST_EDGE_STORE_TRAITS_HPP
-#include <boost/concept_check.hpp>
-
#include <boost/containers.hpp>
#include <boost/descriptors.hpp>
@@ -11,8 +9,8 @@
#include <boost/graphs/edge.hpp>
// Include specializations for the label and edge interfaces.
-#include <boost/graphs/adjacency_list/es/sequence.hpp>
-#include <boost/graphs/adjacency_list/es/association.hpp>
+#include <boost/graphs/adjacency_list/es/seq_edge.hpp>
+#include <boost/graphs/adjacency_list/es/assoc_edge.hpp>
// The edge store interface defines generic operations on an edge store for
// undirected graphs.
@@ -30,6 +28,10 @@
struct edge_store_traits
{
typedef typename Store::value_type edge_type;
+
+ // These are provided for convenience.
+ typedef typename edge_traits<edge_type>::edge_ends edge_ends;
+ typedef typename label_traits<edge_type>::label_type edge_label;
};
namespace es {
@@ -53,37 +55,95 @@
inline typename Store::iterator
dispatch_insert(Store& store, Ends e, Label&& l, pair_associative_container_tag)
{
- if(!(e.first < e.second)) swap(e.first, e.second);
+ // 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.
+ typedef typename Ends::first_type VertexDesc;
+ std::less<typename Ends::first_type> comp;
+ if(!comp(e.first, e.second)) {
+ swap(e.first, e.second);
+ }
return container_insert(store, make_edge(store, e, l));
}
}
-/** Insert . */
+/** Insert an edge into the graph. */
template <typename Store, typename Ends, typename Label>
inline typename descriptor_traits<Store>::descriptor_type
insert(Store& store, Ends e, Label&& l)
-{ return make_descriptor(store, detail::dispatch_insert(store, e, l, container_category(store))); }
+{
+ typedef typename Store::iterator Iterator;
+ typedef typename descriptor_traits<Store>::descriptor_type Descriptor;
+
+ // Start by inserting the edge globally. Could be O(1), O(lgE).
+ Iterator i = detail::dispatch_insert(store, e, l, container_category(store));
+ Descriptor d = make_descriptor(store, i);
+
+ // Insert the edge into the incidence lists of each vertex.
+ // TODO: implement me!
+ // ies::insert(e.first, d);
+ // ies::insert(e.second, d);
+ return d;
+}
+
+/** @name Find Edge
+ * Find an edge with the given endpoints, and return a descriptor to the first
+ * such edge found.
+ */
+//@{
+template <typename Store, typename Ends>
+inline typename descriptor_traits<Store>::descriptor_type
+find(Store& store, Ends e)
+{
+ // Search the incidene list of the smaller vertex for an edge who's endpoint
+ // is given as the other.
+ // if(ies::size(e.first) < ies::size(e.second)
+}
+
+template <typename Store, typename Ends>
+inline typename descriptor_traits<Store>::descriptor_type
+find(Store const& store, Ends e)
+{ return find(const_cast<Store&>(store), e); }
+//@}
/** Return the number of edges in the edge store. */
template <typename Store>
typename Store::size_type size(Store const& store)
{ return store.size(); }
+/** Return true if the global edge set is empty. */
+template <typename Store>
+bool empty(Store const& store)
+{ return store.empty(); }
+
/** @name Edge Label
* Return a lable for the given edge.
*/
//@{
template <typename Store>
-inline typename label_traits<typename edge_store_traits<Store>::edge_type>::label_type&
+inline typename edge_store_traits<Store>::edge_label&
label(Store& store, typename descriptor_traits<Store>::descriptor_type d)
{ return graphs::label(*make_iterator(store, d)); }
template <typename Store>
-inline typename label_traits<typename edge_store_traits<Store>::edge_type>::label_type const&
+inline typename edge_store_traits<Store>::edge_label const&
label(Store const& store, typename descriptor_traits<Store>::descriptor_type d)
{ return graphs::label(*make_iterator(store, d)); }
//@}
+/** @name Endpoints
+ * Return a pair of endpoints for the edge referenced by the given descriptor.
+ * Note that Edge endpoints are always passed and returned by value.
+ */
+//@{
+template <typename Store>
+inline typename edge_store_traits<Store>::edge_ends
+ends(Store& store, typename descriptor_traits<Store>::descriptor_type d)
+{
+ graphs::ends(*make_iterator(store, d));
+}
+//@}
+
} /* namespace es */
} } } /* namespace boost::graphs::adjacency_list */
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/list.hpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -0,0 +1,34 @@
+
+#ifndef BOOST_GRAPHS_ADJLIST_ES_LIST_HPP
+#define BOOST_GRAPHS_ADJLIST_ES_LIST_HPP
+
+#include <boost/counted_list.hpp>
+
+namespace boost { namespace graphs { namespace adjacency_list {
+
+/**
+ * @param Alloc A unary template class that will allocate stored vertices.
+ */
+template <template <typename> class Alloc = std::allocator>
+struct edge_list
+{
+ typedef typename descriptor_traits<
+ counted_list<int, Alloc<int>>
+ >::descriptor_type edge_descriptor;
+
+ // Ends must be a pair of vertices.
+ template <typename Vertex, typename Label>
+ struct store
+ {
+ private:
+ typedef std::pair<Vertex, Vertex> ends;
+ typedef std::pair<ends, Label> edge;
+ typedef Alloc<edge> allocator;
+ public:
+ typedef counted_list<edge, allocator> type;
+ };
+};
+
+} } } /* namespace boost::graphs::adjacency_list */
+
+#endif
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/set.hpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -25,13 +25,14 @@
// This quietly implements a map, not a set because we'll be using the
// endpoints as keys to the label.
- template <typename Ends, typename Label>
- struct edge_store
+ template <typename Vertex, typename Label>
+ struct store
{
- typedef Compare<Ends> compare;
- typedef Alloc<std::pair<Ends, Label>> allocator;
+ typedef std::pair<Vertex, Vertex> ends;
+ typedef Compare<ends> compare;
+ typedef Alloc<std::pair<ends, Label>> allocator;
public:
- typedef std::map<Ends, Label, compare, allocator> type;
+ typedef std::map<ends, Label, compare, allocator> type;
};
};
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/vector.hpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -17,11 +17,12 @@
>::descriptor_type edge_descriptor;
// Ends must be a pair of vertices.
- template <typename Ends, typename Label>
- struct edge_store
+ template <typename Vertex, typename Label>
+ struct store
{
private:
- typedef std::pair<Ends, Label> edge;
+ typedef std::pair<Vertex, Vertex> ends;
+ typedef std::pair<ends, Label> edge;
typedef Alloc<edge> allocator;
public:
typedef std::vector<edge, allocator> type;
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/ies/list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/ies/list.hpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -0,0 +1,26 @@
+
+#ifndef BOOST_GRAPHS_ADJLIST_IES_LIST_HPP
+#define BOOST_GRAPHS_ADJLIST_IES_LIST_HPP
+
+#include <boost/counted_list.hpp>
+
+namespace boost { namespace graphs { namespace adjacency_list {
+
+template <template <typename> class Alloc = std::allocator>
+struct incidence_list
+{
+ template <typename EdgeDesc>
+ struct store
+ {
+ private:
+ typedef Alloc<EdgeDesc> allocator;
+ public:
+ typedef counted_list<EdgeDesc, allocator> type;
+ };
+};
+
+} } }
+
+#endif
+
+
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/ies/set.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/ies/set.hpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -0,0 +1,29 @@
+
+#ifndef BOOST_GRAPHS_ADJLIST_IES_SET_HPP
+#define BOOST_GRAPHS_ADJLIST_IES_SET_HPP
+
+#include <set>
+
+namespace boost { namespace graphs { namespace adjacency_list {
+
+template <
+ template <typename> class Compare = std::less,
+ template <typename> class Alloc = std::allocator>
+struct incidence_set
+{
+ template <typename EdgeDesc>
+ struct store
+ {
+ private:
+ typedef Compare<EdgeDesc> compare;
+ typedef Alloc<EdgeDesc> allocator;
+ public:
+ typedef std::set<EdgeDesc, compare, allocator> type;
+ };
+};
+
+} } }
+
+#endif
+
+
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/ies/vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/ies/vector.hpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -0,0 +1,26 @@
+
+#ifndef BOOST_GRAPHS_ADJLIST_IES_VECTOR_HPP
+#define BOOST_GRAPHS_ADJLIST_IES_VECTOR_HPP
+
+#include <vector>
+
+namespace boost { namespace graphs { namespace adjacency_list {
+
+template <template <typename> class Alloc = std::allocator>
+struct incidence_vector
+{
+ template <typename EdgeDesc>
+ struct store
+ {
+ private:
+ typedef Alloc<EdgeDesc> allocator;
+ public:
+ typedef std::vector<EdgeDesc, allocator> type;
+ };
+};
+
+} } }
+
+#endif
+
+
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_store.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_store.hpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -0,0 +1,33 @@
+
+#ifndef BOOST_GRAPHS_ADJLIST_INCIDENCE_STORE_HPP
+#define BOOST_GRAPHS_ADJLIST_INCIDENCE_STORE_HPP
+
+#include <vector>
+
+// 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.
+
+namespace boost { namespace graphs { namespace adjacency_list {
+
+namespace ies
+{
+
+/** Return the size of an adjacency list for the given vertex. */
+template <typename Store>
+inline typename Store::size_type size(Store const& store)
+{ return store.size(); }
+
+}
+
+} } }
+
+// 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>
+
+#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-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -5,754 +5,75 @@
#include <boost/assert.hpp>
#include <boost/none.hpp>
-#include <boost/graphs/adjacency_list/undirected_types.hpp>
-#include <boost/graphs/adjacency_list/adjacency_iterator.hpp>
+#include <boost/graphs/adjacency_list/vertex_store.hpp>
+#include <boost/graphs/adjacency_list/edge_store.hpp>
+#include <boost/graphs/adjacency_list/incidence_store.hpp>
namespace boost { namespace graphs { namespace adjacency_list {
/**
- * The undirected graph class.
+ * The undirected graph class...
*/
-template <typename VertexLabel, typename EdgeLabel, typename VertexStore, typename EdgeStore>
+template <
+ typename VertexLabel,
+ typename EdgeLabel,
+ typename VertexStore,
+ typename EdgeStore,
+ typename IncidenceStore>
class undirected_graph
{
- typedef undirected_types<VertexLabel, EdgeLabel, VertexStore, EdgeStore> types;
- typedef undirected_graph<VertexLabel, EdgeLabel, VertexStore, EdgeStore> this_type;
public:
+ // Describe labels
typedef VertexLabel vertex_label;
typedef EdgeLabel edge_label;
- typedef VertexStore vertex_store_selector;
- typedef EdgeStore edge_store_selector;
- // Underlying stores
- typedef typename types::property_store property_store;
- typedef typename types::incidence_store incidence_store;
- typedef typename types::vertex_store vertex_store;
- typedef typename types::vertex_key vertex_key;
- typedef typename types::vertex_type vertex_type;
-
- // Vertex/Property/Edge descriptors
- typedef typename types::vertex_descriptor vertex_descriptor;
- typedef typename types::edge_descriptor edge_descriptor;
- typedef typename types::label_descriptor label_descriptor;
- typedef typename types::incidence_descriptor incidence_descriptor;
-
- // Iterators and ranges
- typedef typename types::vertex_iterator vertex_iterator;
- typedef typename types::vertex_range vertex_range;
- typedef typename types::edge_iterator edge_iterator;
- typedef typename types::edge_range edge_range;
- typedef typename types::incident_edge_iterator incident_edge_iterator;
- typedef typename types::incident_edge_range incident_edge_range;
- typedef typename types::adjacent_vertex_iterator adjacent_vertex_iterator;
- typedef typename types::adjacent_vertex_range adjacent_vertex_range;
-
- // Sizes for vertices, edges, and degree.
- typedef typename types::vertices_size_type vertices_size_type;
- typedef typename types::edges_size_type edges_size_type;
- typedef typename types::incident_edges_size_type incident_edges_size_type;
-
-
- // Constructors
- undirected_graph();
-
- /** @name Add Vertex
- * Add a vertex to the graph. Add operations are determined by the concepts
- * modeled by the vertex set.
- *
- * UnlabeledVertices add_vertex()
- * LabeledVerteces add_vertex(vertex_label)
- * LabeledUniqueVertices add_vertex(vertex_label)
- * MappedUniqueVertices add_vertex(vertex_key)
- */
- //@{
- vertex_descriptor add_vertex();
- vertex_descriptor add_vertex(vertex_label const&);
- vertex_descriptor add_vertex(vertex_key const&, vertex_label const&);
- //@}
-
- /** @name Find Vertex
- * Find a vertex in the graph. These methods only exist for graphs that
- * have UniqueVertices. These functions can also be used to find the first
- * vertex of a non-unique vertices.
- *
- * LabeledUniqueVertices find_vertex(vertex_label)
- * MappedUniqueVertices find_vertex(vertex_key)
- */
- //@{
- vertex_descriptor find_vertex(vertex_label const&) const;
- vertex_descriptor find_vertex(vertex_key const&) const;
- //@}
-
- /** @name Vertex Key
- * Return the key for the given vertex. This is only provided for graphs
- * with MappedVertices (can be multimapped).
- */
- //@{
- vertex_key const& key(vertex_descriptor) const;
- //@}
-
- /** @name Remove Vertex
- * Remove a vertex from the graph. These functions only exist for graphs
- * with ReducibleVertexSets. Functions that take label or keys are
- * provided for convenience, but have additional requirements and cost.
- * These additional functions are equivalent to remove_vertex(find_vertex(x))
- * where x is either a vertex_label or vertex_key.
- *
- * ReducibleVertexSet remove_vertex(vertex_descriptor)
- * LabeledUniqueVertices remove_vertex(vertex_label)
- * MappedUniqueVertices remove_vertex(vertex_key)
- */
- //@{
- void remove_vertex(vertex_descriptor);
- void remove_vertex(vertex_label const&);
- void remove_vertex(vertex_key const&);
- //@}
-
- /** @name Add Edge
- * Add an edge, connecting two vertices, to the graph. There are a number of
- * variations of this function, depending on the type of vertex store and
- * whether or not the edges are labeled. Convenience functions are provided
- * for graphs with UniqueVertices. Graphs with LabeledEdges can be added
- * with edge label. Convenience functions are equivalent to the
- * expression add_edge(find_vertex(x), find_vertex(y), p) with x and y
- * eithe vertex proeprties or vertex keys and p optional edge label.
- *
- * ExtendableEdgeSet add_edge(vertex_descriptor, vertex_descriptor)
- * && LabeledEdges add_edge(vertex_descriptor, vertex_descriptor, edge_label)
- *
- * LabeledUniqueVertices add_edge(vertex_label, vertex_label)
- * && LabeledEdges add_edge(vertex_label, vertex_label, edge_label)
- *
- * MappedUniqueVertices add_edge(vertex_key, vertex_key)
- * & LabeledEdges add_edge(vertex_key, vertex_key, edge_label)
- */
- //@{
- // Unlabeled edge adders.
- edge_descriptor add_edge(vertex_descriptor, vertex_descriptor);
- edge_descriptor add_edge(vertex_label const&, vertex_label const&);
- edge_descriptor add_edge(vertex_key const&, vertex_key const&);
-
- // Labeled edge adders.
- edge_descriptor add_edge(vertex_descriptor, vertex_descriptor, edge_label const&);
- edge_descriptor add_edge(vertex_label const&, vertex_label const&, edge_label const&);
- edge_descriptor add_edge(vertex_key const&, vertex_key const&, edge_label const&);
- //@}
-
- /** @name Test Edge
- * Determine if the edge, given by two vertices exists. This function a few
- * convenience overloads that depend on the type of vertex store.
- */
- //@{
- edge_descriptor edge(vertex_descriptor, vertex_descriptor) const;
- edge_descriptor edge(vertex_label const&, vertex_label const&) const;
- edge_descriptor edge(vertex_key const&, vertex_key const&) const;
- //@}
-
- /** @name Remove Edge(s)
- * Remove one or more edges from the graph. The function taking a single
- * edge descriptor removes exactly that edge. The fucntion(s) taking
- * a single vertex descriptor remove all edges incident to that vertex. The
- * function(s) taking two vertices remove all edges connecting the two
- * vertices.
- */
- //@{
- void remove_edge(edge_descriptor);
-
- void remove_edges(vertex_descriptor);
- void remove_edges(vertex_label const&);
- void remove_edges(vertex_key const&);
-
- void remove_edges(vertex_descriptor, vertex_descriptor);
- void remove_edges(vertex_label const&, vertex_label const&);
- void remove_edges(vertex_key const&, vertex_key const&);
- //@}
-
- /** @name Size and Degree */
- //@{
- vertices_size_type num_vertices() const;
- edges_size_type num_edges() const;
- incident_edges_size_type degree(vertex_descriptor) const;
- //@}
-
- /** @name Iterators */
- //@{
- vertex_range vertices() const;
- vertex_iterator begin_vertices() const;
- vertex_iterator end_vertices() const;
-
- edge_range edges() const;
- edge_iterator begin_edges() const;
- edge_iterator end_edges() const;
-
- incident_edge_iterator begin_incident_edges(vertex_descriptor) const;
- incident_edge_iterator end_incident_edges(vertex_descriptor) const;
- incident_edge_range incident_edges(vertex_descriptor) const;
-
- adjacent_vertex_iterator begin_adjacent_vertices(vertex_descriptor) const;
- adjacent_vertex_iterator end_adjacent_vertices(vertex_descriptor) const;
- adjacent_vertex_range adjacent_vertices(vertex_descriptor) const;
- //@}
-
- /** @name Property Accessors
- * Access the label of the given vertex or edge.
- */
- //@{
- vertex_label& operator[](vertex_descriptor);
- vertex_label const& operator[](vertex_descriptor) const;
-
- edge_label& operator[](edge_descriptor);
- edge_label const& operator[](edge_descriptor) const;
- //@}
+ // Generate descriptors
+ typedef typename VertexStore::vertex_descriptor vertex_descriptor;
+ typedef typename EdgeStore::edge_descriptor edge_descriptor;
+
+ // Generate incidence store
+ typedef typename IncidenceStore::template store<edge_descriptor>::type incidence_store;
+ typedef typename VertexStore::template store<incidence_store, VertexLabel>::type vertex_store;
+ typedef typename EdgeStore::template store<vertex_descriptor, EdgeLabel>::type edge_store;
+
+ // Misc types
+ typedef typename VertexStore::key_type vertex_key;
+ typedef typename vertex_store::size_type vertices_size_type;
- mutable property_store _props;
- mutable vertex_store _verts;
+public:
+ vertex_store v;
+ edge_store e;
};
-#define BOOST_GRAPH_UG_PARAMS \
- typename VP, typename EP, typename VS, typename ES
-
-template <BOOST_GRAPH_UG_PARAMS>
-undirected_graph<VP,EP,VS,ES>::undirected_graph()
- : _props()
- , _verts()
-{ }
-
-/**
- * Add a vertex to the graph with no or default label, and return a
- * descriptor to the vertex. Although supported for all adjacency lists, this
- * function should not be used with graphs that have LabeledUniqueVertices
- * as it will always return the same default-propertied vertex iterator.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
-undirected_graph<VP,EP,VS,ES>::add_vertex()
-{
- return _verts.add();
-}
-
-/**
- * Add a vertex to the graph with the given label, and return a descriptor
- * to the added vertes. If the graph has LabeledUniqe vertices, and a vertex
- * with the given label already exists in the graph, then a new vertex
- * is not added and returned descriptor refers to the existing vertex.
- *
- * @requires LabeledVertices<Graph>
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
-undirected_graph<VP,EP,VS,ES>::add_vertex(vertex_label const& vp)
-{
- return _verts.add(vp);
-}
-
-/**
- * Add a new vertex with the given label to the graph and map it to the
- * given key.
- *
- * @requires MappedUniqueVertices<Graph>
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
-undirected_graph<VP,EP,VS,ES>::add_vertex(vertex_key const& k, vertex_label const& vp)
-{
- return _verts.add(k, vp);
-}
-
-/**
- * Find the vertex with the given label, returning a descriptor to it.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
-undirected_graph<VP,EP,VS,ES>::find_vertex(vertex_label const& vp) const
-{
- BOOST_STATIC_ASSERT(is_not_none<vertex_label>::value);
- return _verts.find(vp);
-}
-
-/**
- * Find the vertex with the given label, returning a descriptor to it.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
-undirected_graph<VP,EP,VS,ES>::find_vertex(vertex_key const& k) const
-{
- return _verts.find(k);
-}
-
-/**
- * Remove the vertex from the graph. This will disconnect the vertex from the
- * graph prior to remove.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_vertex(vertex_descriptor v)
-{
- remove_edges(v);
- _verts.remove(v);
-}
-
-/**
- * Remove the vertex from the graph identified by the given label.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_vertex(vertex_label const& vp)
-{
- BOOST_STATIC_ASSERT(is_not_none<vertex_label>::value);
- remove_edges(vp);
- _verts.remove(vp);
-}
-
-/**
- * Remove the vertex from the graph identified by the given key.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_vertex(vertex_key const& k)
-{
- remove_edges(k);
- _verts.remove(k);
-}
-
-/**
- * Return the key associated with the given vertex. This function is only
- * available for graphs with mapped vertices.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_key const&
-undirected_graph<VP,EP,VS,ES>::key(vertex_descriptor v) const
-{
- return _verts.key(v);
-}
-
-
-/**
- * Create an edge, connecting the vertices u and v.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::add_edge(vertex_descriptor u,
- vertex_descriptor v)
-{
- return add_edge(u, v, edge_label());
-}
-
-/**
- * Create an edge with the given label that connects the vertices u and v.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::add_edge(vertex_descriptor u,
- vertex_descriptor v,
- edge_label const& ep)
-{
- // Get vertices for the descriptors
- reorder(u, v);
- vertex_type& src = _verts.vertex(u);
- vertex_type& tgt = _verts.vertex(v);
-
- // Insert algorithm: Try to stub out the edge locally first. If it succeeds,
- // then add the global property, and finally bind the incidence and property
- // descitpros into their respective "slots".
- insertion_result<incidence_descriptor> first = src.connect(v);
- if(first.succeeded()) {
- // Stub the incident edge on the other vertex. Logically speaking, if
- // an edge (u, v) can be added, then (v,u) must not exist.
- insertion_result<incidence_descriptor> second = tgt.connect(u);
- BOOST_ASSERT(second.succeeded());
-
- // Add the property and bind everything together.
- label_descriptor p = _props.add(ep);
- src.bind(first.value, p);
- tgt.bind(second.value, p);
- _props.bind(p,make_pair(make_pair(u, first.value), make_pair(v, second.value)));
- return edge_descriptor(u, v, p);
- }
- else if(first.retained()) {
- label_descriptor p = src.label(first.value);
- return edge_descriptor(u, v, p);
- }
- else {
- return edge_descriptor();
- }
-}
-
-/**
- * Add an edge to the graph that connects the two vertices identified by the
- * given label. The edge is either unlabeled or has default label.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::add_edge(vertex_label const& u,
- vertex_label const& v)
-{
- return add_edge(u, v, edge_label());
-}
-
-/**
- * Add an edge to the graph that connects the two vertices identified by the
- * given label and has the given edge label.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::add_edge(vertex_label const& u,
- vertex_label const& v,
- edge_label const& ep)
-{
- return add_edge(find_vertex(u), find_vertex(v), ep);
-}
-
-/**
- * Add an edge to the graph that connects the two vertices identified by the
- * given keys. The edge is either unlabeled or has default label.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::add_edge(vertex_key const& u,
- vertex_key const& v)
-{
- return add_edge(u, v, edge_label());
-}
-
-/**
- * Determine if any edge exists connecting the vertices u and v. Return a
- * pair containing the edge descriptor (if it exists) and a bool determing
- * whether or not the edge did exist.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::edge(vertex_descriptor u, vertex_descriptor v) const
-{
- reorder(u, v);
- vertex_type const& src = _verts.vertex(u);
- incidence_descriptor i = src.find(v);
- return i ? edge_descriptor(u, v, src.label(i)) : edge_descriptor();
-}
-
-/**
- * Determine if any edge exists connecting the vertices identified by the given
- * label. Return a pair containing the edge descriptor (if it exists) and
- * a bool determining whether or not the edge did exist. This is equivalent to
- * edge(find_vertex(u), find_vertex(v)).
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::edge(vertex_label const& u,
- vertex_label const& v) const
+template <typename VL, typename EL, typename VS, typename ES, typename IS>
+typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor
+add_vertex(undirected_graph<VL,EL,VS,ES,IS>& g)
{
- return edge(find_vertex(u), find_vertex(v));
+ typedef typename undirected_graph<VL,EL,VS,ES,IS>::vertex_label VertexLabel;
+ return vs::insert(g.v, VertexLabel());
}
-/**
- * Determine if any edge exists connecting the vertices identified by the given
- * keys. Return a pair containing the edge descriptor (if it exists) and a bool
- * determining whether or not the edge did exist. This is equivalent to the
- * expression edge(find_vertex(u), find_vertex(v)).
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::edge(vertex_key const& u,
- vertex_key const& v) const
-{
- return edge(find_vertex(u), find_vertex(v));
-}
+template <typename VL, typename EL, typename VS, typename ES, typename IS>
+typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor
+add_vertex(undirected_graph<VL,EL,VS,ES,IS>& g,
+ typename undirected_graph<VL,EL,VS,ES,IS>::vertex_label&& l)
+{ return vs::insert(g.v, l); }
-/**
- * Remove only the given edge from graph. This disconnects both vertices in
- * the edge and removes the property from the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_edge(edge_descriptor e)
-{
- // Grab descriptors out of the edge.
- label_descriptor p = e.label();
- vertex_descriptor u = e.first(), v = e.second();
- vertex_type &src = _verts.vertex(u), &tgt = _verts.vertex(v);
-
- // Get incidence iterators from the property and arranging them to match
- // their owning vertices.
- incidence_descriptor i = _props.first_edge(p), j = _props.second_edge(p);
- if(src.opposite(i) == v) {
- i.swap(j);
- }
-
- // Disconnect the incidence ends and then remove the property from the
- // global property store.
- src.disconnect(j);
- tgt.disconnect(i);
- _props.remove(p);
-}
+template <typename VL, typename EL, typename VS, typename ES, typename IS>
+typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor
+add_vertex(undirected_graph<VL,EL,VS,ES,IS>& g,
+ typename undirected_graph<VL,EL,VS,ES,IS>::vertex_key const& k,
+ typename undirected_graph<VL,EL,VS,ES,IS>::vertex_label&& l)
+{ return vs::insert(g.v, k, l); }
-/**
- * Remove all edges incident to the given vertex, effectively disconnecting
- * it from the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor v)
-{
- vertex_type& src = _verts.vertex(v);
- // Start by disconnecting all of the incident edges from adjacent vertices.
- incident_edge_range rng = incident_edges(v);
- for(incident_edge_iterator i = rng.first ; i != rng.second; ++i) {
- edge_descriptor e = *i;
- vertex_type& tgt = _verts.vertex(e.opposite(v));
-
- // Get an incidence descriptor into the target into tgt's edge store,
- // so we can remove the edge record and the label of the removed
- // edge.
- label_descriptor p = e.label();
- std::pair<incidence_descriptor, incidence_descriptor> x =
- std::make_pair(_props.first_edge(p), _props.second_edge(p));
- if(src.opposite(x.first) != v) {
- x.first.swap(x.second);
- }
- tgt.disconnect(x.first);
- _props.remove(e.label());
- }
-
- // Clear the incident edge set of the vertex. We can't do this in the
- // previous loop because it will invalidate the our iterators.
- src.clear();
-}
-/**
- * Disconnect the vertex having the given label from the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_label const& vp)
-{
- BOOST_STATIC_ASSERT(is_not_none<vertex_label>::value);
- remove_edges(find_vertex(vp));
-}
-
-/**
- * Disconnect the vertex having the given key from the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_key const& k)
-{
- remove_edges(find_vertex(k));
-}
-
-/**
- * Remove all edges connecting the vertices u and v.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor u,
- vertex_descriptor v)
-{
- // Canonicalize the ordering of vertices first and the get the vertices.
- reorder(u, v);
- vertex_type& src = _verts.vertex(u);
- vertex_type& tgt = _verts.vertex(v);
-
- // Iterate over the incident edges of the source vertex. If we the edge
- // (u, *i) is the same as (u, v), then we need to remove that edge. We
- // also have to cache these iterators and remove them in a second pass.
- std::vector<incidence_descriptor> iters;
- incident_edge_range rng = incident_edges(u);
- for(incident_edge_iterator i = rng.first ; i != rng.second; ++i) {
- edge_descriptor e = *i;
- vertex_descriptor o = e.opposite(u);
- if(o == v) {
- // Grab descriptors to the property and the incident edge on the
- // target vertex and remove them,
- label_descriptor p = e.label();
- std::pair<incidence_descriptor, incidence_descriptor> x =
- std::make_pair(_props.first_edge(p), _props.second_edge(p));
- if(src.opposite(x.first) == v) {
- x.first.swap(x.second);
- }
- tgt.disconnect(x.first);
- _props.remove(p);
-
- // Stash the iterator for the second pass.
- iters.push_back(x.second);
- }
- }
-
- // Second pass: disconnect all of the incident edges from src.
- typename std::vector<incidence_descriptor>::iterator i, end = iters.end();
- for(i = iters.begin(); i != end; ++i) {
- src.disconnect(*i);
- }
-}
-
-/**
- * Remove all edges connecting the vertices identified by the given label.
- * This is equivalent to remove_edges(find_vertex(u), find_vertex(v)).
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_label const& u,
- vertex_label const& v)
-{
- return remove_edges(find_vertex(u), find_vertex(v));
-}
-
-/**
- * Remove all edges connecting the vertices identified by the given keys. This
- * is equivalent to remove_edges(find_vertex(u), find_vertex(v)).
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_key const& u,
- vertex_key const& v)
-{
- return remove_edges(find_vertex(u), find_vertex(v));
-}
-
-/**
- * Return an iterator range over the vertices of the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_range
-undirected_graph<VP,EP,VS,ES>::vertices() const
-{
- return _verts.vertices();
-}
-
-/**
- * Return an iterator to the first iterator in the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_iterator
-undirected_graph<VP,EP,VS,ES>::begin_vertices() const
-{
- return _verts.begin_vertices();
-}
-
-/**
- * Return an iterator past the end of the vertices in the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_iterator
-undirected_graph<VP,EP,VS,ES>::end_vertices() const
-{
- return _verts.end_vertices();
-}
-
-/** Return an iterator to the first edge. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_iterator
-undirected_graph<VP,EP,VS,ES>::begin_edges() const
-{ return edge_iterator(_props, _props.begin()); }
-
-/** Return an iterator past the end of the edges. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_iterator
-undirected_graph<VP,EP,VS,ES>::end_edges() const
-{ return edge_iterator(_props, _props.end()); }
-
-/** Return an iterator range over the edges in the graph. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_range
-undirected_graph<VP,EP,VS,ES>::edges() const
-{ return std::make_pair(begin_edges(), end_edges()); }
-
-/** Return the number of iterators in this graph. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertices_size_type
-undirected_graph<VP,EP,VS,ES>::num_vertices() const
-{ return _verts.size(); }
-
-/** Return the number of edges in this graph. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edges_size_type
-undirected_graph<VP,EP,VS,ES>::num_edges() const
-{ return _props.size(); }
-
-/** Return an iterator to the first incident edge of the given vertex. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::incident_edge_iterator
-undirected_graph<VP,EP,VS,ES>::begin_incident_edges(vertex_descriptor v) const
-{ return incident_edge_iterator(v, _verts.vertex(v).begin()); }
-
-/** Return an iterator past the end of the incident edges of the given vertex. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::incident_edge_iterator
-undirected_graph<VP,EP,VS,ES>::end_incident_edges(vertex_descriptor v) const
-{ return incident_edge_iterator(v, _verts.vertex(v).end()); }
-
-/** Return an iterator range over the incident edges of the given vertex. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::incident_edge_range
-undirected_graph<VP,EP,VS,ES>::incident_edges(vertex_descriptor v) const
-{ return make_pair(begin_incident_edges(v), end_incident_edges(v)); }
-
-/**
- * Return an iterator to the first adjacent vertex of the the given vertex.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::adjacent_vertex_iterator
-undirected_graph<VP,EP,VS,ES>::begin_adjacent_vertices(vertex_descriptor v) const
-{
- return begin_incident_edges(v);
-}
-
-/**
- * Return an iterator past the end of the adjacent vertices of the given vertex.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::adjacent_vertex_iterator
-undirected_graph<VP,EP,VS,ES>::end_adjacent_vertices(vertex_descriptor v) const
-{
- return end_incident_edges(v);
-}
-
-/**
- * Return an iterator range over the adjacent vertices of the given vertex.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::adjacent_vertex_range
-undirected_graph<VP,EP,VS,ES>::adjacent_vertices(vertex_descriptor v) const
-{
- return std::make_pair(begin_adjacent_vertices(v), end_adjacent_vertices(v));
-}
-
-
-/**
- * Return the degree (number of incdent edges) of the given vertex.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::incident_edges_size_type
-undirected_graph<VP,EP,VS,ES>::degree(vertex_descriptor v) const
-{
- return _verts.vertex(v).degree();
-}
-/** Return the label for the given vertex. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_label&
-undirected_graph<VP,EP,VS,ES>::operator[](vertex_descriptor v)
-{ return _verts.label(v); }
-
-/** Return the label for the given vertex. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_label const&
-undirected_graph<VP,EP,VS,ES>::operator[](vertex_descriptor v) const
-{ return _verts.label(v); }
-
-/** Return the label for the given edge. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_label&
-undirected_graph<VP,EP,VS,ES>::operator[](edge_descriptor e)
-{ return _props.label(e.label()); }
-
-/** Return the label for the given edge. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_label const&
-undirected_graph<VP,EP,VS,ES>::operator[](edge_descriptor e) const
-{ return _props.label(e.label()); }
+template <typename VL, typename EL, typename VS, typename ES, typename IS>
+typename undirected_graph<VL,EL,VS,ES,IS>::vertices_size_type
+num_vertices(undirected_graph<VL,EL,VS,ES,IS> const& g)
+{ return vs::size(g.v); }
-#undef BOOST_GRAPH_UG_PARAMS
} } } /* namespace boost::graphs::adjacency_list */
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-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -2,13 +2,22 @@
#ifndef BOOST_GRAPH_ADJLIST_VERTEX_STORE_TRAITS_HPP
#define BOOST_GRAPH_ADJLIST_VERTEX_STORE_TRAITS_HPP
+
#include <boost/concept_check.hpp>
+#include <boost/mpl/bool.hpp>
+
#include <boost/containers.hpp>
#include <boost/descriptors.hpp>
#include <boost/graphs/label.hpp>
+// Include type selectors for the different vertex store implementations
+#include <boost/graphs/adjacency_list/vs/vector.hpp>
+#include <boost/graphs/adjacency_list/vs/list.hpp>
+#include <boost/graphs/adjacency_list/vs/set.hpp>
+#include <boost/graphs/adjacency_list/vs/map.hpp>
+
// The Vertex Store defines the generic interface for working with a vertex
// set for both directed and undirected adjacency lists. Its primary goal is
// to provide generic interfaces that abstract common operations on these
@@ -34,6 +43,33 @@
namespace boost { namespace graphs { namespace adjacency_list {
/**
+ * The incidence traits class provides a means of accessing type information
+ * about the incidence store of a vertex.
+ */
+template <typename Vertex>
+struct vertex_traits
+{
+ typedef typename Vertex::label_type vertex_label;
+ typedef typename Vertex::vertex_edges vertex_edges;
+};
+
+// Specialization for any vertex type implemented as a pair - which all are.
+template <typename Edges, typename Label>
+struct vertex_traits<std::pair<Edges, Label>>
+{
+ typedef Label vertex_label;
+ typedef Edges vertex_edges;
+};
+
+// Specialization for vertex_set, which quietly implements the set as a map.
+template <typename Edges, typename Label>
+struct vertex_traits<std::pair<Label const, Edges>>
+{
+ typedef Label vertex_label;
+ typedef Edges vertex_edges;
+};
+
+/**
* The vertex_store_traits relates associated types with a kind of vertex store.
* Mostly, this is useful in cases where we have to get the vertex type from
* simple and pair associative containers.
@@ -44,10 +80,50 @@
typedef typename Store::value_type vertex_type;
};
+// Specialization for vertex map. This will not match for vertex set since the
+// vertex type of a that selector is not a pair.
+template <typename Key, typename Edges, typename Label, typename Compare, typename Alloc>
+struct vertex_store_traits<std::map<Key, std::pair<Edges, Label>, Compare, Alloc>>
+{
+ typedef typename std::map<Key, std::pair<Edges, Label>, Compare, Alloc>::mapped_type vertex_type;
+};
+
namespace vs {
namespace detail {
+ // For some reason (possbily a GCC bug), we have to do a better job
+ // specializing the make_vertex functions. No idea why... Either way, this
+ // looks a bit hacky.
+ template <typename Vertex, typename Alloc, typename Label>
+ inline Vertex
+ make_vertex(std::vector<Vertex, Alloc> const&, Label&& l)
+ {
+ typedef typename vertex_traits<Vertex>::vertex_edges Edges;
+ return Vertex(Edges(), l);
+ }
+
+ template <typename Vertex, typename Alloc, typename Label>
+ inline Vertex
+ make_vertex(counted_list<Vertex, Alloc> const&, Label&& l)
+ {
+ typedef typename vertex_traits<Vertex>::vertex_edges Edges;
+ return Vertex(Edges(), l);
+ }
+
+ // Specialization for vertex_set
+ template <typename Label, typename Edges, typename Compare, typename Alloc>
+ inline std::pair<Label const, Edges>
+ make_vertex(std::map<Label, Edges, Compare, Alloc> const&, Label const& l)
+ { return std::make_pair(l, Edges()); }
+
+ // Specialization for vertex_map
+ template <typename Key, typename Edges, typename Label, typename Compare, typename Alloc>
+ inline std::pair<Edges, Label>
+ make_vertex(std::map<Key, std::pair<Edges, Label>, Compare, Alloc> const&, Label&& l)
+ { return std::make_pair(l, Edges()); }
+
+
// Iterate and compare for sequences.
template <typename Store, typename Label>
inline typename Store::iterator
@@ -99,21 +175,34 @@
/** @name Add Vertex
* Add a vertex to the given store, returning an iterator to the new vertex
- * vertex. The semantics and performance of this function depend on the kind
- * of vertex store.
+ * vertex. New vertices are created without an empty incidence list - they
+ * have no neighbors.
*/
//@{
/** Insert a vertex into the container. */
-template <typename Store, typename Vertex>
+template <typename Store, typename Label>
inline typename descriptor_traits<Store>::descriptor_type
-insert(Store& store, Vertex&& v)
-{ return make_descriptor(store, container_insert(store, v)); }
+insert(Store& store, Label&& l)
+{
+ typedef typename Store::iterator Iterator;
+ Iterator i = container_insert(store, detail::make_vertex(store, l));
+ return make_descriptor(store, i);
+}
/** Insert a vertex into the container, mapped to the given key. */
-template <typename Store, typename Key, typename Vertex>
+template <typename Store, typename Key, typename Label>
inline typename descriptor_traits<Store>::descriptor_type
-insert(Store& store, Key const& k, Vertex&& v)
-{ return make_descriptor(store, container_insert(store, std::make_pair(k, v))); }
+insert(Store& store, Key const& k, Label&& l)
+{
+ // TODO: This is a bit hacky w.r.t. the generic make_vertex function
+ // in that it doesn't call it - but it probably should. For some reason,
+ // the make_vertex that I think should match, doesn't.
+ typedef typename Store::iterator Iterator;
+ typedef typename vertex_store_traits<Store>::vertex_type Vertex;
+ typedef typename vertex_traits<Vertex>::vertex_edges Edges;
+ Iterator i = container_insert(store, std::make_pair(k, Vertex(Edges(), l)));
+ return make_descriptor(store, i);
+}
//@}
/** @name Try to Add Vertex
@@ -197,10 +286,4 @@
} } } /* namespace boost::graphs::adjacency_list */
-// Include type selectors for the different vertex store implementations
-#include <boost/graphs/adjacency_list/vs/vector.hpp>
-#include <boost/graphs/adjacency_list/vs/list.hpp>
-#include <boost/graphs/adjacency_list/vs/set.hpp>
-#include <boost/graphs/adjacency_list/vs/map.hpp>
-
#endif
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/list.hpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -18,11 +18,14 @@
std::list<int, Alloc<int>>
>::descriptor_type vertex_descriptor;
- template <typename Vertex>
- struct vertex_store
+ template <typename Edges, typename Label>
+ struct store
{
- typedef Alloc<Vertex> allocator;
- typedef counted_list<Vertex, allocator> type;
+ private:
+ typedef std::pair<Edges, Label> vertex;
+ typedef Alloc<vertex> allocator;
+ public:
+ typedef counted_list<vertex, allocator> type;
};
};
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/map.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/map.hpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -25,23 +25,18 @@
std::map<Key, int, Compare<Key>, Alloc<std::pair<Key, int>>>
>::descriptor_type vertex_descriptor;
- template <typename Vertex>
- struct vertex_store
+ template <typename Edges, typename Label>
+ struct store
{
- typedef Alloc<std::pair<Key, Vertex>> allocator;
+ private:
+ typedef std::pair<Edges, Label> vertex;
typedef Compare<Key> compare;
- typedef std::map<Key, Vertex, compare, allocator> type;
+ typedef Alloc<std::pair<Key, vertex>> allocator;
+ public:
+ typedef std::map<Key, vertex, compare, allocator> type;
};
};
-// Specialize the vertex store traits to refer to the mapped type instead
-// of the value type.
-template <typename Key, typename Value, typename Compare, typename Alloc>
-struct vertex_store_traits<std::map<Key, Value, Compare, Alloc>>
-{
- typedef typename std::map<Key, Value, Compare, Alloc>::mapped_type vertex_type;
-};
-
} } } /* namespace boost::graphs::adjacency_list */
#endif
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/set.hpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -2,7 +2,7 @@
#ifndef BOOST_GRAPHS_ADJLIST_VS_SET_HPP
#define BOOST_GRAPHS_ADJLIST_VS_SET_HPP
-#include <set>
+#include <map>
#include <boost/graphs/label.hpp>
@@ -24,15 +24,17 @@
std::set<int, Compare<int>, Alloc<int>>
>::descriptor_type vertex_descriptor;
- template <typename Vertex>
- struct vertex_store
+ // Quietly define a set as a map from label (which is the key being
+ // compared) to the vertex which is actually just the set of edges.
+ template <typename Edges, typename Label>
+ struct store
{
private:
- typedef Alloc<Vertex> allocator;
- typedef typename label_traits<Vertex>::label_type label_type;
- typedef labelled_compare<Vertex, Compare<label_type>> compare;
+ typedef Edges vertex;
+ typedef Compare<Label> compare;
+ typedef Alloc<std::pair<Label, vertex>> allocator;
public:
- typedef std::set<Vertex, compare, allocator> type;
+ typedef std::map<Label, vertex, compare, allocator> type;
};
};
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/vector.hpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -18,14 +18,14 @@
std::vector<int, Alloc<int>>
>::descriptor_type vertex_descriptor;
- // The store metafunction generates the type used to store vertices in
- // either a directed or undirected graph. This metafunction takes the
- // fully configured vertex type as a type parameter.
- template <typename Vertex>
- struct vertex_store
+ template <typename Edges, typename Label>
+ struct store
{
- typedef Alloc<Vertex> allocator;
- typedef std::vector<Vertex, allocator> type;
+ private:
+ typedef std::pair<Edges, Label> vertex;
+ typedef Alloc<vertex> allocator;
+ public:
+ typedef std::vector<vertex, allocator> type;
};
};
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/edge.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/edge.hpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -6,7 +6,18 @@
namespace boost { namespace graphs {
-// The edge interface...
+// There are two faces of the edge interface - the generic specification for
+// edge objects is used internally by varios graph components and relies
+// entirely on implementations defined by the edge stores.
+// - Ends ends(Edge)
+// - VertexDesc first(Edge)
+// - VertexDesc second(Edge)
+// - VertexDesc source(Edge) - Same as first()
+// - VertexDesc target(Edge) - Same as second()
+// - VertexDesc opposite(Edge, VertexDesc)
+
+// The public, generic interface is written in terms of graph objects and
+// descriptors.
/**
* The edge traits class provides information about the end points and semantics
@@ -15,7 +26,8 @@
template <typename Edge>
struct edge_traits
{
- typedef typename Edge::end_pair end_pair;
+ typedef typename Edge::vertex_descriptor vertex_descriptor;
+ typedef typename Edge::edge_ends edge_ends;
};
} } /* namespace boost::graphs */
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/CMakeLists.txt
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test/CMakeLists.txt (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/CMakeLists.txt 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -1,5 +1,7 @@
include_directories(${Graphs_INCLUDE_DIRS} ${Boost_INCLUDE_DIRS})
-add_exec(vertex_store vertex_store.cpp)
-add_exec(edge_store edge_store.cpp)
+# add_exec(vertex_store vertex_store.cpp)
+# add_exec(edge_store edge_store.cpp)
+
+add_exec(undirected undirected.cpp)
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/edge_store.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test/edge_store.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/edge_store.cpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -16,7 +16,7 @@
void test()
{
typedef typename edge_store_traits<Store>::edge_type Edge;
- typedef typename edge_traits<Edge>::end_pair Ends;
+ typedef typename edge_traits<Edge>::edge_ends Ends;
typedef typename descriptor_traits<Store>::descriptor_type EdgeDesc;
Store store;
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp 2008-11-21 14:52:10 EST (Fri, 21 Nov 2008)
@@ -0,0 +1,86 @@
+
+#include <iostream>
+
+#include <boost/assert.hpp>
+#include <boost/mpl/bool.hpp>
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
+
+#include "typestr.hpp"
+
+using namespace std;
+using namespace boost;
+using namespace boost::graphs::adjacency_list;
+
+template <typename Graph>
+struct _has_mapped_vertices
+{ typedef mpl::false_ type; };
+
+template <
+ typename VL, typename EL,
+ typename K, template <typename> class C, template <typename> class A,
+ typename ES, typename IS>
+struct _has_mapped_vertices<undirected_graph<VL, EL, vertex_map<K,C,A>, ES, IS>>
+{ typedef mpl::true_ type; };
+
+template <typename Graph>
+typename _has_mapped_vertices<Graph>::type
+has_mapped_vertices(Graph const& g)
+{ return typename _has_mapped_vertices<Graph>::type(); }
+
+struct node
+{
+ node() : n() { }
+ node(int n) : n(n) { }
+
+ bool operator<(node const& x) const { return n < x.n; }
+
+ int n;
+};
+
+struct arc
+{
+ arc() : n() { }
+ arc(int n) : n(n) { }
+ int n;
+};
+
+template <typename Graph>
+void add_vertices(Graph& g, mpl::false_)
+{
+ add_vertex(g);
+ add_vertex(g, node(3));
+ add_vertex(g, std::move(node(5)));
+ BOOST_ASSERT(num_vertices(g) == 3);
+}
+
+template <typename Graph>
+void add_vertices(Graph& g, mpl::true_)
+{
+ add_vertex(g, "a", node());
+ add_vertex(g, "b", node(3));
+ add_vertex(g, "c", std::move(node(5)));
+ BOOST_ASSERT(num_vertices(g) == 3);
+}
+
+template <typename Graph>
+void test()
+{
+ Graph g;
+ BOOST_ASSERT(num_vertices(g) == 0);
+
+ add_vertices(g, has_mapped_vertices(g));
+}
+
+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<string>, edge_vector<>, incidence_vector<>> MVV;
+
+ test<VVV>();
+ test<LVV>();
+ test<SVV>();
+ test<MVV>();
+}
+
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk