|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r50012 - in sandbox/SOC/2008/graphs/trunk/libs/graphs: include/boost/graphs/adjacency_list include/boost/graphs/adjacency_list/es test
From: asutton_at_[hidden]
Date: 2008-11-29 08:53:14
Author: asutton
Date: 2008-11-29 08:53:13 EST (Sat, 29 Nov 2008)
New Revision: 50012
URL: http://svn.boost.org/trac/boost/changeset/50012
Log:
- Partially implemented the ability to remove vertices from undirected
graphs. Needs the edge store for completion.
- Migrated code from the edge impl files into edge store.
- Implemented the base functionality for adding edges, still need to finish
stitching the incidence stores back to the edge set.
Removed:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/assoc_edge.hpp
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/seq_edge.hpp
Text files modified:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp | 164 +++++++++++++++++++++++++++++++--------
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp | 69 +++++++++++++--
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp | 17 +--
sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp | 121 ++++++++++++++++++++++------
4 files changed, 289 insertions(+), 82 deletions(-)
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 08:53:13 EST (Sat, 29 Nov 2008)
@@ -15,32 +15,132 @@
#include <boost/graphs/adjacency_list/es/list.hpp>
#include <boost/graphs/adjacency_list/es/set.hpp>
-// Include specializations for the label and edge interfaces.
-// TODO: Migrate code from these files to here.
-#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.
// NOTE: Directed graphs do not use a global edge store. They use out and in
// edge stores and have a completely different interface.
-// TODO: There is a significant overlap between the sequence selectors for
-// vertex and edge stores. These could easily be integrated into a kind of
-// general purpose selector mechanism. For now, they're separate.
+namespace boost { namespace graphs {
+
+/** @name Label Traits [edge_vector, edge_list] */
+//@{
+template <typename Vertex, typename Label>
+struct label_traits<std::pair<std::pair<Vertex, Vertex>, Label>>
+{
+ typedef Label label_type;
+};
+
+template <typename Vertex, typename Label>
+inline Label&
+label(std::pair<std::pair<Vertex, Vertex>, Label>& edge)
+{ return edge.second; }
+
+template <typename Vertex, typename Label>
+inline Label const&
+label(std::pair<std::pair<Vertex, Vertex>, Label> const& edge)
+{ return edge.second; }
+//@}
+
+/** @name Label Traits [edge_set] */
+//@{
+template <typename Vertex, typename Label>
+struct label_traits<std::pair<std::pair<Vertex, Vertex> const, Label>>
+{
+ typedef Label label_type;
+};
+
+template <typename Vertex, typename Label>
+inline Label&
+label(std::pair<std::pair<Vertex, Vertex> const, Label>& edge)
+{ return edge.second; }
+
+template <typename Vertex, typename Label>
+inline Label const&
+label(std::pair<std::pair<Vertex, Vertex> const, Label> const& edge)
+{ return edge.second; }
+//@}
+
+// NOTE: The difference between the specialization of edge traits over the
+// edge types is quite subtle. Compare:
+// std::pair<std::pair<Vertex, Vertex>, Label> <- Vector and List
+// std::pair<std::pair<Vertex, Vertex> const, Label> <- Set
+// Even worse, there's no functional difference between then.
+
+/** @name Edge Traits [edge_vector, edge_list] */
+//@{
+template <typename Vertex, typename Label>
+struct edge_traits<std::pair<std::pair<Vertex, Vertex>, Label>>
+{
+ typedef Vertex vertex_descriptor;
+ typedef std::pair<Vertex, Vertex> edge_ends;
+};
+
+template <typename Vertex, typename Label>
+inline Label const&
+ends(std::pair<std::pair<Vertex, Vertex>, Label> const& edge)
+{ return edge.first; }
+
+template <typename Vertex, typename Label>
+inline Vertex
+first(std::pair<std::pair<Vertex, Vertex>, Label> const& edge)
+{ return edge.first.first; }
+
+template <typename Vertex, typename Label>
+inline Vertex
+second(std::pair<std::pair<Vertex, Vertex>, Label> const& edge)
+{ return edge.first.second; }
+
+template <typename Vertex, typename Label>
+inline Vertex
+oppposite(std::pair<std::pair<Vertex, Vertex>, Label> const& edge, Vertex which)
+{ return which == first(edge) ? second(edge) : first(edge); }
+//@}
+
+/** @name Edge Traits [edge_set] */
+//@{
+template <typename Vertex, typename Label>
+struct edge_traits<std::pair<std::pair<Vertex, Vertex> const, Label>>
+{
+ typedef Vertex vertex_descriptor;
+ typedef std::pair<Vertex, Vertex> edge_ends;
+};
+
+template <typename Vertex, typename Label>
+inline std::pair<Vertex, Vertex>
+ends(std::pair<std::pair<Vertex, Vertex> const, Label> const& edge)
+{ return edge.first; }
+
+template <typename Vertex, typename Label>
+inline Vertex
+first(std::pair<std::pair<Vertex, Vertex> const, Label> const& edge)
+{ return edge.first.first; }
+
+template <typename Vertex, typename Label>
+inline Vertex
+second(std::pair<std::pair<Vertex, Vertex> const, Label> const& edge)
+{ return edge.first.second; }
+
+template <typename Vertex, typename Label>
+inline Vertex
+oppposite(std::pair<std::pair<Vertex, Vertex> const, Label> const& edge, Vertex which)
+{ return which == first(edge) ? second(edge) : first(edge); }
+//@}
-namespace boost { namespace graphs { namespace adjacency_list {
+namespace adjacency_list {
template <typename Store>
struct edge_store_traits
{
- typedef typename descriptor_traits<Store, edge_descriptor_kind>::descriptor_kind
+ typedef typename Store::size_type edges_size_type;
+ typedef typename descriptor_traits<Store, edge_descriptor_kind>::descriptor_type
edge_descriptor;
typedef typename Store::value_type edge_type;
typedef typename edge_traits<edge_type>::edge_ends edge_ends;
typedef typename label_traits<edge_type>::label_type edge_label;
+
+ typedef typename edge_traits<edge_type>::vertex_descriptor vertex_descriptor;
};
namespace es {
@@ -51,48 +151,44 @@
make_edge(Store const&, Ends e, Label&& l)
{ return typename edge_store_traits<Store>::edge_type(e, l); }
- template <typename Store, typename Ends, typename Label>
+ // Just push the edge into the sequence. Since these types support a
+ // multigraph, the ordering of endpoints is essentially irrelevant.
+ template <typename Store, typename Vertex, typename Label>
inline typename Store::iterator
- dispatch_insert(Store& store, Ends e, Label&& l, sequence_tag)
- { return store.insert(store.end(), make_edge(store, e, l)); }
+ 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)); }
// 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.
- template <typename Store, typename Ends, typename Label>
+ template <typename Store, typename Vertex, typename Label>
inline typename Store::iterator
- dispatch_insert(Store& store, Ends e, Label&& l, pair_associative_container_tag)
+ dispatch_insert(Store& store, Vertex u, Vertex v, Label&& l, pair_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.
- typedef typename Ends::first_type VertexDesc;
- std::less<typename Ends::first_type> comp;
- if(!comp(e.first, e.second)) {
- swap(e.first, e.second);
+ std::less<Vertex> comp;
+ if(!comp(u, v)) {
+ using std::swap;
+ swap(u, v);
}
- return container_insert(store, make_edge(store, e, l));
+ return container_insert(store, make_edge(store, std::make_pair(u, v), l));
}
-}
+} /* namespace detail */
/** 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)
+template <typename Store, typename Vertex, typename Label>
+inline typename edge_store_traits<Store>::edge_descriptor
+insert(Store& store, Vertex u, Vertex v, Label&& l)
{
typedef typename Store::iterator Iterator;
- typedef typename descriptor_traits<Store>::descriptor_type Descriptor;
+ 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, 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;
+ Iterator i = detail::dispatch_insert(store, u, v, l, container_category(store));
+ return make_descriptor(store, i, edge_descriptor_kind());
}
/** @name Find Edge
@@ -117,7 +213,7 @@
/** Return the number of edges in the edge store. */
template <typename Store>
-typename Store::size_type size(Store const& store)
+typename edge_store_traits<Store>::edges_size_type size(Store const& store)
{ return store.size(); }
/** Return true if the global edge set is empty. */
Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/assoc_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/assoc_edge.hpp 2008-11-29 08:53:13 EST (Sat, 29 Nov 2008)
+++ (empty file)
@@ -1,65 +0,0 @@
-
-#ifndef BOOST_GRAPHS_ADJLIST_ES_ASSOCIATION_HPP
-#define BOOST_GRAPHS_ADJLIST_ES_ASSOCIATION_HPP
-
-namespace boost { namespace graphs {
-
-// NOTE: The code in this module is identical to that in sequence.hpp except
-// for the fact that the edge pair is const. Is there a graceful way to get
-// around this? Probably, but it might involve pushing more code through traits
-// classes.
-
-// Specializations to support labels for undirected edges for edge vectors,
-// and lists.
-
-template <typename VertexDesc, typename EdgeLabel>
-struct label_traits<std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel>>
-{
- typedef EdgeLabel label_type;
-};
-
-template <typename VertexDesc, typename EdgeLabel>
-inline EdgeLabel&
-label(std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel>& edge)
-{ return edge.second; }
-
-template <typename VertexDesc, typename EdgeLabel>
-inline EdgeLabel const&
-label(std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel> const& edge)
-{ return edge.second; }
-
-// Specializations of the edge interface for edge sequences (vectors and lists).
-
-// NOTE: I'm un-consting the key type for an associative container. Will this
-// cause problems later? Possibly.
-template <typename VertexDesc, typename EdgeLabel>
-struct edge_traits<std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel>>
-{
- typedef VertexDesc vertex_descriptor;
- typedef std::pair<VertexDesc, VertexDesc> edge_ends;
-};
-
-template <typename VertexDesc, typename EdgeLabel>
-inline std::pair<VertexDesc, VertexDesc>
-ends(std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel> const& edge)
-{ return edge.first; }
-
-template <typename VertexDesc, typename EdgeLabel>
-inline VertexDesc
-first(std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel> const& edge)
-{ return edge.first.first; }
-
-template <typename VertexDesc, typename EdgeLabel>
-inline VertexDesc
-second(std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel> const& edge)
-{ return edge.first.second; }
-
-template <typename VertexDesc, typename EdgeLabel>
-inline VertexDesc
-oppposite(std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel> const& edge, VertexDesc which)
-{ return which == first(edge) ? second(edge) : first(edge); }
-
-
-} } /* namespace boost::graphs */
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/seq_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/seq_edge.hpp 2008-11-29 08:53:13 EST (Sat, 29 Nov 2008)
+++ (empty file)
@@ -1,61 +0,0 @@
-
-#ifndef BOOST_GRAPHS_ADJLIST_ES_SEQUENCE_HPP
-#define BOOST_GRAPHS_ADJLIST_ES_SEQUENCE_HPP
-
-namespace boost { namespace graphs {
-
-// Specializations to support labels for undirected edges for edge vectors,
-// and lists.
-
-// TODO: I'm a little worried about the possibility of type collisions. I may
-// be required to introduce a tagging system to label and edge traits to help
-// distinguish the intent of the specialization.
-
-template <typename VertexDesc, typename EdgeLabel>
-struct label_traits<std::pair<std::pair<VertexDesc, VertexDesc>, EdgeLabel>>
-{
- typedef EdgeLabel label_type;
-};
-
-template <typename VertexDesc, typename EdgeLabel>
-inline EdgeLabel&
-label(std::pair<std::pair<VertexDesc, VertexDesc>, EdgeLabel>& edge)
-{ return edge.second; }
-
-template <typename VertexDesc, typename EdgeLabel>
-inline EdgeLabel const&
-label(std::pair<std::pair<VertexDesc, VertexDesc>, EdgeLabel> const& edge)
-{ return edge.second; }
-
-// Specializations of the edge interface for edge sequences (vectors and lists).
-
-template <typename VertexDesc, typename EdgeLabel>
-struct edge_traits<std::pair<std::pair<VertexDesc, VertexDesc>, EdgeLabel>>
-{
- typedef VertexDesc vertex_descriptor;
- typedef std::pair<VertexDesc, VertexDesc> edge_ends;
-};
-
-} } /* namespace boost::graphs */
-
-template <typename VertexDesc, typename EdgeLabel>
-inline EdgeLabel const&
-ends(std::pair<std::pair<VertexDesc, VertexDesc>, EdgeLabel> const& edge)
-{ return edge.first; }
-
-template <typename VertexDesc, typename EdgeLabel>
-inline VertexDesc
-first(std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel> const& edge)
-{ return edge.first.first; }
-
-template <typename VertexDesc, typename EdgeLabel>
-inline VertexDesc
-second(std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel> const& edge)
-{ return edge.first.second; }
-
-template <typename VertexDesc, typename EdgeLabel>
-inline VertexDesc
-oppposite(std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel> const& edge, VertexDesc which)
-{ return which == first(edge) ? second(edge) : first(edge); }
-
-#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 08:53:13 EST (Sat, 29 Nov 2008)
@@ -38,7 +38,8 @@
// Misc types
typedef typename VertexStore::key_type vertex_key;
- typedef typename vertex_store::size_type vertices_size_type;
+ typedef typename vertex_store_traits<vertex_store>::vertices_size_type vertices_size_type;
+ typedef typename edge_store_traits<edge_store>::edges_size_type edges_size_type;
vertex_label& operator[](vertex_descriptor d)
{ return vs::label(v, d); }
@@ -61,7 +62,7 @@
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 vs::insert(g.v, typename undirected_graph<VL,EL,VS,ES,IS>::vertex_label()); }
+{ return add_vertex(g, typename undirected_graph<VL,EL,VS,ES,IS>::vertex_label()); }
template <typename VL, typename EL, typename VS, typename ES, typename IS>
typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor
@@ -84,35 +85,79 @@
* their label, the other based on their key. The latter is only applicable
* for graphs with mapped vertices.
*
- * @note, These overloads are ambigous for mapped vertex graphs if the key
- * and label are the same type. We should probably provide special function to
+ * @note These overloads are ambigous for mapped vertex graphs if the key and
+ * label are the same type. We should probably provide special function to
* differentiate these functions.
*/
//@{
template <typename VL, typename EL, typename VS, typename ES, typename IS>
-typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor
-find_vertex(undirected_graph<VL,EL,VS,ES,IS> const& g,
- typename undirected_graph<VL,EL,VS,ES,IS>::vertex_label const& l)
+inline typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor
+vertex(undirected_graph<VL,EL,VS,ES,IS> const& g,
+ typename undirected_graph<VL,EL,VS,ES,IS>::vertex_label const& l)
{ return vs::find(g.v, l); }
template <typename VL, typename EL, typename VS, typename ES, typename IS>
-typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor
-find_vertex(undirected_graph<VL,EL,VS,ES,IS> const& g,
- typename undirected_graph<VL,EL,VS,ES,IS>::vertex_key const& k)
+inline typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor
+vertex(undirected_graph<VL,EL,VS,ES,IS> const& g,
+ typename undirected_graph<VL,EL,VS,ES,IS>::vertex_key const& k)
{ return vs::find(g.v, k); }
//@}
/** @name Remove Vertex
- * Remove the given vertex from the graph.
+ * Remove the given vertex from the graph. This will also remove all incident
+ * edges from the vertex before removing it from the graph.
+ * @todo Implement remove_edges.
*/
//@{
+template <typename VL, typename EL, typename VS, typename ES, typename IS>
+inline void
+remove_vertex(undirected_graph<VL,EL,VS,ES,IS>& g,
+ typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor v)
+{
+ // remove_edges();
+ return vs::erase(g.v, v);
+}
//@}
+/** Return the number of vertices in the graph. */
template <typename VL, typename EL, typename VS, typename ES, typename IS>
-typename undirected_graph<VL,EL,VS,ES,IS>::vertices_size_type
+inline 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); }
+/** @name Remove Vertex
+ * Remove the given vertex from the graph. This will also remove all incident
+ * edges from the vertex before removing it from the graph.
+ * @todo Implement remove_edges.
+ */
+//@{
+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,
+ typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor u,
+ 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()); }
+
+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,
+ typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor u,
+ typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor v,
+ 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;
+}
+//@}
+
+/** Return the number of edges in the graph. */
+template <typename VL, typename EL, typename VS, typename ES, typename IS>
+inline typename undirected_graph<VL,EL,VS,ES,IS>::edges_size_type
+num_edges(undirected_graph<VL,EL,VS,ES,IS> const& g)
+{ return es::size(g.e); }
+
+
} } } /* 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-29 08:53:13 EST (Sat, 29 Nov 2008)
@@ -253,11 +253,11 @@
// Explicitly remove the ability use this function, by failing a concept
// check when it is instantiated.
template <typename Store>
- void dispatch_remove(Store&, typename Store::iterator, vector_tag)
- { function_requires(Integer<Store>()); }
+ void dispatch_erase(Store&, typename Store::iterator, vector_tag)
+ { BOOST_CONCEPT_ASSERT((Integer<Store>)); }
template <typename Store, typename Tag>
- void dispatch_remove(Store& store, typename Store::iterator i, Tag)
+ void dispatch_erase(Store& store, typename Store::iterator i, Tag)
{ store.erase(i); }
} /* namespace detail */
@@ -271,8 +271,7 @@
/** Insert a vertex into the container. */
template <typename Store>
inline typename vertex_store_traits<Store>::vertex_descriptor
-insert(Store& store,
- typename vertex_store_traits<Store>::vertex_label&& l)
+insert(Store& store, typename vertex_store_traits<Store>::vertex_label&& l)
{
typedef typename Store::iterator Iterator;
Iterator i = container_insert(store, detail::make_vertex(store, l));
@@ -352,15 +351,15 @@
//@}
/**
- * @name Remove Vertex
+ * @name Erase Vertex
* Remove the vertex from the store. This will only remove the vertex from the
- * store, it cannot operate on edges.
+ * store, it does not remove any incident edges.
*/
//@{
template <typename Store>
inline void
-remove(Store& store, typename descriptor_traits<Store>::descriptor_type d)
-{ detail::dispatch_remove(store, make_iterator(store, d), container_category(store)); }
+erase(Store& store, typename vertex_store_traits<Store>::vertex_descriptor d)
+{ detail::dispatch_erase(store, make_iterator(store, d), container_category(store)); }
//@}
/** @name Vertex Object */
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 08:53:13 EST (Sat, 29 Nov 2008)
@@ -11,6 +11,8 @@
using namespace boost;
using namespace boost::graphs::adjacency_list;
+/** @name Has Mapped Vertices */
+//@{
template <typename Graph>
struct _has_mapped_vertices
{ typedef mpl::false_ type; };
@@ -26,6 +28,26 @@
typename _has_mapped_vertices<Graph>::type
has_mapped_vertices(Graph const& g)
{ return typename _has_mapped_vertices<Graph>::type(); }
+//@}
+
+/** @name Can Remove Vertices */
+//@{
+template <typename Graph>
+struct _can_remove_vertices
+{ typedef mpl::true_ type; };
+
+template <
+ typename VL, typename EL,
+ template <typename> class A,
+ typename ES, typename IS>
+struct _can_remove_vertices<undirected_graph<VL, EL, vertex_vector<A>, ES, IS>>
+{ typedef mpl::false_ type; };
+
+template <typename Graph>
+typename _can_remove_vertices<Graph>::type
+can_remove_vertices(Graph const& g)
+{ return typename _can_remove_vertices<Graph>::type(); }
+//@}
struct node
{
@@ -45,45 +67,88 @@
int n;
};
+
+namespace impl {
+ template <typename Graph>
+ typename Graph::vertex_descriptor do_add(Graph& g, int id, mpl::false_)
+ { return add_vertex(g, node(id)); }
+
+ template <typename Graph>
+ typename Graph::vertex_descriptor do_add(Graph& g, int id, mpl::true_)
+ { return add_vertex(g, id, node(id)); }
+} /* namespace impl */
+
template <typename Graph>
-void add_vertices(Graph& g, mpl::false_)
+typename Graph::vertex_descriptor add_vertex(Graph& g, int id)
+{ return impl::do_add(g, id, has_mapped_vertices(g)); }
+
+
+// Can't remove vertices... Don't do anything.
+template <typename Graph, typename Vertex>
+void test_remove_vert(Graph& g, Vertex v, mpl::false_)
+{ }
+
+template <typename Graph, typename Vertex>
+void test_remove_vert(Graph& g, Vertex v, mpl::true_)
{
- add_vertex(g); // This is really a test for unlabeled verts
- add_vertex(g, node(3));
- add_vertex(g, std::move(node(5)));
+ remove_vertex(g, v);
+ BOOST_ASSERT(num_vertices(g) == 2);
+}
+
+// TODO: Combine these test to make them more generic.
+// Test vertices for simple vertex graphs
+template <typename Graph>
+void test_verts(Graph& g, mpl::false_)
+{
+ add_vertex(g, 1);
+ add_vertex(g, 3);
+ add_vertex(g, 5);
BOOST_ASSERT(num_vertices(g) == 3);
// Test the non-cosnt find
- {
- typedef typename Graph::vertex_descriptor VertexDesc;
- VertexDesc v = find_vertex(g, node(3));
- BOOST_ASSERT(!v.is_null());
- BOOST_ASSERT(g[v] == node(3));
- }
-
- // Test the const find.
- {
- Graph const& h = g;
- typedef typename Graph::vertex_descriptor VertexDesc;
- VertexDesc v = find_vertex(h, node(3));
- BOOST_ASSERT(!v.is_null());
- BOOST_ASSERT(h[v] == node(3));
- }
+ typedef typename Graph::vertex_descriptor VertexDesc;
+ VertexDesc v = vertex(g, node(3));
+ BOOST_ASSERT(!v.is_null());
+ BOOST_ASSERT(g[v] == node(3));
+
+ test_remove_vert(g, v, can_remove_vertices(g));
}
+// Test vertices for mapped vertex graphs
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)));
+void test_verts(Graph& g, mpl::true_)
+{
+ add_vertex(g, 1);
+ add_vertex(g, 3);
+ add_vertex(g, 5);
BOOST_ASSERT(num_vertices(g) == 3);
// Test the find also.
typedef typename Graph::vertex_descriptor VertexDesc;
- VertexDesc v = find_vertex(g, "b");
+ VertexDesc v = vertex(g, 3);
BOOST_ASSERT(!v.is_null());
BOOST_ASSERT(g[v] == node(3));
+
+ // Try to remove the vertex
+ remove_vertex(g, v);
+ BOOST_ASSERT(num_vertices(g) == 2);
+}
+
+
+template <typename Graph>
+void test_edges(Graph& g)
+{
+ typedef typename Graph::vertex_descriptor Vertex;
+ typedef typename Graph::edge_descriptor Edge;
+
+ Vertex u = add_vertex(g, 100);
+ Vertex v = add_vertex(g, 101);
+ Vertex w = add_vertex(g, 102);
+ Edge e1 = add_edge(g, u, v, arc(200));
+ Edge e2 = add_edge(g, v, w, arc(201));
+ Edge e3 = add_edge(g, w, u, arc(202));
+
+ BOOST_ASSERT(num_edges(g) == 3);
}
template <typename Graph>
@@ -92,7 +157,8 @@
Graph g;
BOOST_ASSERT(num_vertices(g) == 0);
- add_vertices(g, has_mapped_vertices(g));
+ test_verts(g, has_mapped_vertices(g));
+ test_edges(g);
}
int main()
@@ -100,11 +166,12 @@
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;
+ typedef undirected_graph<node, arc, vertex_map<int>, 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