Boost logo

Boost-Commit :

Date view Thread view Subject view Author view

From: asutton_at_[hidden]
Date: 2008-06-11 10:38:32

Author: asutton
Date: 2008-06-11 10:38:31 EDT (Wed, 11 Jun 2008)
New Revision: 46330
URL: http://svn.boost.org/trac/boost/changeset/46330

Log:
Rewrote edge-adding code so that edge sets actually implement /sets/. Vertices
and incidence sets now implement a "allow" protocol that determines whether
or not adjacent vertices can be connected and, if they already exist, the
iterator referencing that connection.

Text files modified:
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_list.hpp | 48 ++++++++++++++-----
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp | 49 ++++++++++++++-----
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_vector.hpp | 41 ++++++++++++-----
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/none.hpp | 10 ----
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp | 55 +++++++++++++---------
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp | 64 ++++++++++++++++++--------
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex.hpp | 35 ++++++++++++++
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_set.hpp | 17 +++++-
   sandbox/SOC/2008/graphs/branches/iu/libs/graphs/Jamfile | 2
   sandbox/SOC/2008/graphs/branches/iu/libs/graphs/un.cpp | 94 ++++++++++++++++++++++++++++++++++-----
   10 files changed, 305 insertions(+), 110 deletions(-)

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_list.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_list.hpp 2008-06-11 10:38:31 EDT (Wed, 11 Jun 2008)
@@ -33,6 +33,7 @@
 
     inline void add(incidence_pair);
 
+ inline std::pair<const_iterator, bool> allow(vertex_descriptor) const;
     inline iterator find(incidence_pair);
     inline const_iterator find(incidence_pair) const;
 
@@ -41,21 +42,34 @@
 
     inline void clear();
 
- size_type size() const;
+
+ inline size_type size() const
+ { return _edges.size(); }
+
+ inline const_iterator begin() const
+ { return _edges.begin(); }
+
+ inline const_iterator end() const
+ { return _edges.end(); }
 
 private:
     store_type _edges;
 };
 
-#define BOOST_GRAPHS_IL_PARAMS \
+#define BOOST_GRAPH_IL_PARAMS \
     typename E, typename A
 
-template <BOOST_GRAPHS_IL_PARAMS>
+template <BOOST_GRAPH_IL_PARAMS>
 incidence_list<E,A>::incidence_list()
     : _edges()
 { }
 
-template <BOOST_GRAPHS_IL_PARAMS>
+/**
+ * Add the incident edge to the incidence set.
+ *
+ * @complexity O(1)
+ */
+template <BOOST_GRAPH_IL_PARAMS>
 void
 incidence_list<E,A>::add(incidence_pair p)
 {
@@ -63,6 +77,20 @@
 }
 
 /**
+ * Incidence lists always allow the addition of edges, assuming that no policy
+ * conflicts exist. The first element of the return is the end() of the list.
+ *
+ * @complexity O(1)
+ */
+template <BOOST_GRAPH_IL_PARAMS>
+std::pair<typename incidence_list<E,A>::const_iterator, bool>
+incidence_list<E,A>::allow(vertex_descriptor v) const
+{
+ // Since there's no policy, there we must be able to add the edge.
+ return make_pair(_edges.end(), true);
+}
+
+/**
  * Remove the incidence pair from the list. This operation is linear with
  * respect to the number of incident edges.
  *
@@ -70,7 +98,7 @@
  * @require EqualityComparable<property_descriptor>
  * @complexity O(d)
  */
-template <BOOST_GRAPHS_IL_PARAMS>
+template <BOOST_GRAPH_IL_PARAMS>
 void
 incidence_list<E,A>::remove(incidence_pair p)
 {
@@ -87,7 +115,7 @@
  * @require EqualityComparable<property_descriptor>
  * @complexity Theta(d)
  */
-template <BOOST_GRAPHS_IL_PARAMS>
+template <BOOST_GRAPH_IL_PARAMS>
 template <typename Eraser>
 void
 incidence_list<E,A>::remove(vertex_descriptor v, Eraser erase)
@@ -95,6 +123,7 @@
     iterator i = _edges.begin(), end = _edges.end();
     for( ; i != end; ) {
         if(i->first == v) {
+ erase(i->second);
             i = _edges.erase(i);
         }
         else {
@@ -103,13 +132,6 @@
     }
 }
 
-template <BOOST_GRAPHS_IL_PARAMS>
-typename incidence_list<E,A>::size_type
-incidence_list<E,A>::size() const
-{
- return _edges.size();
-}
-
 #if 0
 
 // Functions

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp 2008-06-11 10:38:31 EDT (Wed, 11 Jun 2008)
@@ -35,19 +35,32 @@
     // Constructors
     incidence_set();
 
+ // Add an incident edge.
     inline void add(incidence_pair);
 
+ // Allow a connection to the edge?
+ inline std::pair<const_iterator, bool> allow(vertex_descriptor) const;
+
+ // Find the edge record in question.
     inline iterator find(incidence_pair);
     inline const_iterator find(incidence_pair) const;
 
+ // Remove the edge.
     inline void remove(incidence_pair);
+ template <typename Eraser> inline void remove(vertex_descriptor, Eraser);
 
- template <typename Eraser>
- inline void remove(vertex_descriptor, Eraser);
-
+ // Remove all edges.
     inline void clear();
 
- inline size_type size() const;
+
+ inline size_type size() const
+ { return _edges.size(); }
+
+ inline const_iterator begin() const
+ { return _edges.begin(); }
+
+ inline const_iterator end() const
+ { return _edges.end(); }
 
 private:
     store_type _edges;
@@ -64,6 +77,24 @@
 { }
 
 /**
+ * Deteremine whether or not the edge exists or is even allowed to be added.
+ * This returns a pair containing an iterator indicating the position of the
+ * edge if it already exists and a bool value indicating whether or not the
+ * addition would even be allowed by policy.
+ *
+ * @complexity O(lg(d))
+ */
+template <BOOST_GRAPH_IS_PARAMS>
+std::pair<typename incidence_set<E,C,A>::const_iterator, bool>
+incidence_set<E,C,A>::allow(vertex_descriptor v) const
+{
+ // For now, always assume that the edge is allowed by policy, and determine
+ // "addability" based on whehter or not the edge exists.
+ return make_pair(_edges.find(v), true);
+}
+
+
+/**
  * Add the incidence pair to the set.
  *
  * @complexity O(lg(d))
@@ -106,16 +137,6 @@
     erase(p);
 }
 
-/**
- * Return the number of incident edges (degree) in the set.
- */
-template <BOOST_GRAPH_IS_PARAMS>
-typename incidence_set<E,C,A>::size_type
-incidence_set<E,C,A>::size() const
-{
- return _edges.size();
-}
-
 #undef BOOST_GRAPH_IS_PARAMS
 
 #if 0

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_vector.hpp 2008-06-11 10:38:31 EDT (Wed, 11 Jun 2008)
@@ -33,38 +33,55 @@
 
     void add(incidence_pair);
 
+ std::pair<const_iterator, bool> allow(vertex_descriptor) const;
     iterator find(incidence_pair);
     const_iterator find(incidence_pair) const;
 
- size_type size() const;
+ inline size_type size() const
+ { return _edges.size(); }
+
+ inline const_iterator begin() const
+ { return _edges.begin(); }
+
+ inline const_iterator end() const
+ { return _edges.end(); }
 
 private:
     store_type _edges;
 };
 
-#define BOOST_GRAPHS_IV_PARAMS \
- typename IE, typename A
+#define BOOST_GRAPH_IV_PARAMS \
+ typename E, typename A
 
-template <BOOST_GRAPHS_IV_PARAMS>
-incidence_vector<IE,A>::incidence_vector()
+template <BOOST_GRAPH_IV_PARAMS>
+incidence_vector<E,A>::incidence_vector()
     : _edges()
 { }
 
-template <BOOST_GRAPHS_IV_PARAMS>
+template <BOOST_GRAPH_IV_PARAMS>
 void
-incidence_vector<IE,A>::add(incidence_pair e)
+incidence_vector<E,A>::add(incidence_pair e)
 {
     _edges.push_back(e);
 }
 
-template <BOOST_GRAPHS_IV_PARAMS>
-typename incidence_vector<IE,A>::size_type
-incidence_vector<IE,A>::size() const
+/**
+ * Incidence vectors always allow the addition of edges, assuming that no
+ * policy conflicts exist. The first element of the return is the end() of the
+ * vector.
+ *
+ * @complexity O(1)
+ */
+template <BOOST_GRAPH_IV_PARAMS>
+std::pair<typename incidence_vector<E,A>::const_iterator, bool>
+incidence_vector<E,A>::allow(vertex_descriptor v) const
 {
- return _edges.size();
+ // Since there's no policy, there we must be able to add the edge.
+ return make_pair(_edges.end(), true);
 }
 
-#undef BOOST_GRAPHS_IV_PARAMS
+
+#undef BOOST_GRAPH_IV_PARAMS
 
 #if 0
 

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/none.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/none.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/none.hpp 2008-06-11 10:38:31 EDT (Wed, 11 Jun 2008)
@@ -5,15 +5,5 @@
 // The canonical none type.
 struct none { };
 
-// A little weird, but there are times when it makes sense to create noop
-// operations. This takes a single parameter.
-template <typename T>
-struct noop
-{
- typedef void result_type;
- void operator()(T const&)
- { }
-};
-
 #endif
 

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp 2008-06-11 10:38:31 EDT (Wed, 11 Jun 2008)
@@ -32,7 +32,7 @@
     // Property access.
     inline property_type& properties(property_descriptor);
 
-private:
+public:
     store_type _props;
 };
 
@@ -107,38 +107,47 @@
 template <typename Iter>
 struct proplist_descriptor
 {
- inline proplist_descriptor(Iter const&);
+ inline proplist_descriptor()
+ : iter()
+ { }
+
+ inline proplist_descriptor(Iter const& iter)
+ : iter(iter)
+ { }
 
- inline bool operator==(proplist_descriptor const&) const;
- inline bool operator<(proplist_descriptor const&) const;
+ inline bool operator==(proplist_descriptor const& x) const
+ { return iter == x.iter; }
+
+ inline bool operator<(proplist_descriptor const& x) const
+ { return &*iter < &*x.iter; }
 
     Iter iter;
 };
 
-template <typename I>
-proplist_descriptor<I>::proplist_descriptor(I const& iter)
- : iter(iter)
-{ }
 
-template <typename I>
-bool
-proplist_descriptor<I>::operator==(proplist_descriptor const& x) const
+// This helper type is used to erase global edge properties during edge removal
+// of undirected graphs.
+template <typename PropList>
+struct property_eraser
 {
- return iter == x.iter;
-}
+ property_eraser(PropList& props)
+ : props(props)
+ { }
 
-template <typename I>
-bool
-proplist_descriptor<I>::operator<(proplist_descriptor const& x) const
-{
- return &*iter < &*x.iter;
-}
+ template <typename PropDesc>
+ void operator()(PropDesc p)
+ { props.remove(p); }
 
-// Property list algorithm objects
-template <typename PropList>
-struct eraser
+ PropList& props;
+};
+
+// The noop eraser does nothing.
+struct noop_eraser
 {
- eraser(PropList& props)
+ noop_eraser() { }
+
+ template <typename PropDesc>
+ void operator()(PropDesc)
     { }
 };
 

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp 2008-06-11 10:38:31 EDT (Wed, 11 Jun 2008)
@@ -106,6 +106,8 @@
 private:
     property_store _props;
     vertex_store _verts;
+
+ std::size_t _edges;
 };
 
 #define BOOST_GRAPH_UG_PARAMS \
@@ -147,16 +149,10 @@
  */
 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)
+undirected_graph<VP,EP,VS,ES>::add_edge(vertex_descriptor u,
+ vertex_descriptor v)
 {
- // Start by getting a property descriptor for the edge.
- property_descriptor p = _props.add();
- vertex_type& src = _verts.vertex(u);
- vertex_type& tgt = _verts.vertex(v);
- src.connect(v, p);
- tgt.connect(u, p);
-
- return edge_descriptor(u, v, p);
+ return add_edge(u, v, edge_properties());
 }
 
 /**
@@ -168,14 +164,40 @@
                                         vertex_descriptor v,
                                         edge_properties const& ep)
 {
- // Start by getting a property descriptor for the edge.
- property_descriptor p = _props.add(ep);
+ typedef typename incidence_store::const_iterator inc_iterator;
+
+ // To add the edge or not... We need to consult the virtual edge set
+ // to determine whether or not this edge already exists. For multigraph
+ // stores, this should always return false. The protocol is: ask the source
+ // if it can be connected to the target. If so, connect them. If they're
+ // connected, return the existing edge. If they can't be connected, return
+ // a null descriptor.
     vertex_type& src = _verts.vertex(u);
     vertex_type& tgt = _verts.vertex(v);
- src.connect(v, p);
- tgt.connect(u, p);
 
- return edge_descriptor(u, v, p);
+ std::pair<inc_iterator, bool> ins = src.allow(v);
+ if(ins.second) {
+ // If the returned iterator is past the end, then we need to add this
+ // edge. Otherwise, we can simply return an edge over the existing
+ // iterator.
+ if(ins.first == src.end()) {
+ property_descriptor p = _props.add();
+ src.connect(v, p);
+ tgt.connect(u, p);
+ std::cout << "added new edge" << std::endl;
+ return edge_descriptor(u, v, p);
+ }
+ else {
+ std::cout << "reusing old edge" << std::endl;
+ return edge_descriptor(u, v, ins.first->second);
+ }
+ }
+ else {
+ std::cout << "can't add?" << std::endl;
+ }
+
+ // This is a null iterator
+ return edge_descriptor();
 }
 
 /**
@@ -213,20 +235,20 @@
     using boost::bind;
     using boost::ref;
 
+ vertex_type& src = _verts.vertex(u);
+ vertex_type& tgt = _verts.vertex(v);
+
     // The implementation of this function is... not pretty because of the
     // number of efficient ways to do this for both lists, sets and maps.
     // Remember that we have to remove the same basic edge structures from
     // both source and target, but only need to remove the global properties
     // once.
-
- vertex_type& src = _verts.vertex(u);
- vertex_type& tgt = _verts.vertex(v);
-
- // Disconnect v from the src, removing global properties,. Then disconnect
+ //
+ // Disconnect v from the src, removing global properties. Then disconnect
     // u from tgt, but don't actually do anything with the properties (they're
     // already gone!).
- src.disconnect(v, bind(&property_store::remove, ref(_props), _1));
- tgt.disconnect(u, bind(noop<property_descriptor>(), _1));
+ src.disconnect(v, property_eraser<property_store>(_props));
+ tgt.disconnect(u, noop_eraser());
 }
 
 /**

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex.hpp 2008-06-11 10:38:31 EDT (Wed, 11 Jun 2008)
@@ -19,11 +19,13 @@
     typedef typename incidence_store::vertex_descriptor vertex_descriptor;
     typedef typename incidence_store::property_descriptor property_descriptor;
 
+ typedef typename incidence_store::const_iterator iterator;
     typedef typename incidence_store::size_type incidence_size_type;
 
     inline vertex();
     inline vertex(vertex_properties const& vp);
 
+ inline std::pair<iterator, bool> allow(vertex_descriptor) const;
     inline void connect(vertex_descriptor, property_descriptor);
     inline void disconnect(vertex_descriptor, property_descriptor);
     template <typename Eraser> inline void disconnect(vertex_descriptor, Eraser);
@@ -31,6 +33,14 @@
     inline incidence_size_type degree() const;
 
     inline vertex_properties& properties();
+ inline vertex_properties const& properties() const;
+
+
+ inline iterator begin() const
+ { return _edges.begin(); }
+
+ inline iterator end() const
+ { return _edges.end(); }
 
     inline bool operator<(vertex const&) const;
 
@@ -52,6 +62,21 @@
 { }
 
 /**
+ * Deteremine whether or not the edge exists or is even allowed to be added.
+ * This returns a pair containing an iterator indicating the position of the
+ * edge if it already exists and a bool value indicating whether or not the
+ * addition would even be allowed by policy.
+ *
+ * @complexity O(lg(d))
+ */
+template <typename VP, typename IS>
+std::pair<typename vertex<VP,IS>::iterator, bool>
+vertex<VP,IS>::allow(vertex_descriptor v) const
+{
+ return _edges.allow(v);
+}
+
+/**
  * Connect this vertex to the vertex v with edge properties p.
  */
 template <typename VP, typename IS>
@@ -100,6 +125,16 @@
 }
 
 /**
+ * Return the properties associated with this vertex (if any).
+ */
+template <typename VP, typename IS>
+typename vertex<VP,IS>::vertex_properties const&
+vertex<VP,IS>::properties() const
+{
+ return _props;
+}
+
+/**
  * The default comparison of vertices always delegates the comparison to the
  * stored vertex properties. This allows developers to express custom
  * comparitors with respect to the properties and have the vertex sets or other

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_set.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_set.hpp 2008-06-11 10:38:31 EDT (Wed, 11 Jun 2008)
@@ -93,8 +93,9 @@
     // Remove vertices.
     void remove(vertex_descriptor v);
 
- // Find a vertex based on its properties.
- vertex_descriptor find(vertex_properties const& vp) const;
+ // Find the given vertex.
+ const_iterator find(vertex_descriptor v) const;
+ const_iterator find(vertex_properties const& vp);
 
     // Number of vertices.
     size_type size() const;
@@ -163,6 +164,16 @@
 }
 
 /**
+ * Find a vertex in the set.
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+typename vertex_set_impl<V,C,A>::const_iterator
+vertex_set_impl<V,C,A>::find(vertex_descriptor v) const
+{
+ return find(vertex(v).properties());
+}
+
+/**
  * Return an iterator range over the vertices in this graph.
  */
 template <BOOST_GRAPH_VS_PARAMS>
@@ -290,7 +301,7 @@
 template <BOOST_GRAPH_VS_PARAMS>
 void
 vertex_set_impl<V,C,A>::remove_vertex(vertex_properties const& vp)
-{
+{4
     remove_vertex(find(vp));
 }
 

Modified: sandbox/SOC/2008/graphs/branches/iu/libs/graphs/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/libs/graphs/Jamfile (original)
+++ sandbox/SOC/2008/graphs/branches/iu/libs/graphs/Jamfile 2008-06-11 10:38:31 EDT (Wed, 11 Jun 2008)
@@ -1,4 +1,2 @@
 
 exe un : un.cpp : <include>../../ <include>/usr/local/include ;
-
-exe test : test.cpp ;

Modified: sandbox/SOC/2008/graphs/branches/iu/libs/graphs/un.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/libs/graphs/un.cpp (original)
+++ sandbox/SOC/2008/graphs/branches/iu/libs/graphs/un.cpp 2008-06-11 10:38:31 EDT (Wed, 11 Jun 2008)
@@ -2,17 +2,20 @@
 #include <iostream>
 #include <set>
 
+#include <boost/utility.hpp>
 #include <boost/graphs/undirected_graph.hpp>
 
 #include "demangle.hpp"
 
 using namespace std;
+using namespace boost;
 
-struct City { };
+typedef int City;
 struct Road { };
 
 void list_list();
 void vec_vec();
+void set_set();
 
 template <typename Graph>
 void print_types(const Graph&)
@@ -28,46 +31,113 @@
 template <typename Graph>
 void add_verts(Graph& g)
 {
- for(int i = 0; i < 10; ++i) {
- g.add_vertex();
+ cout << "*** Add Vertices" << endl;
+ cout << "*** " << demangle(typeid(Graph).name()) << endl;
+ for(int i = 0; i < 5; ++i) {
+ g.add_vertex(i);
     }
- cout << "num_verts: " << g.num_vertices() << std::endl;
+}
+
+template <typename Graph>
+void del_verts(Graph& g)
+{
+ // Just remove the first two vertices
+ typename Graph::vertex_descriptor u = *g.begin_vertices();
+ typename Graph::vertex_descriptor v = *next(g.begin_vertices());
+ g.remove_vertex(u);
+ g.remove_vertex(v);
 }
 
 template <typename Graph>
 void add_edges(Graph& g)
 {
- typename Graph::vertex_descriptor u = g.add_vertex();
- typename Graph::vertex_descriptor v = g.add_vertex();
+ cout << "*** Add Edges" << endl;
+ cout << "*** " << demangle(typeid(Graph).name()) << endl;
+ typename Graph::vertex_descriptor u = g.add_vertex(100);
+ typename Graph::vertex_descriptor v = g.add_vertex(101);
+ typename Graph::vertex_descriptor w = g.add_vertex(102);
+ g.add_edge(v, u);
+ g.add_edge(w, u);
+}
+
+template <typename Graph>
+void add_and_del_edges(Graph& g)
+{
+ cout << "*** Add/Delete Edges" << endl;
+ cout << "*** " << demangle(typeid(Graph).name()) << endl;
+ typename Graph::vertex_descriptor u = g.add_vertex(100);
+ typename Graph::vertex_descriptor v = g.add_vertex(101);
+ typename Graph::vertex_descriptor w = g.add_vertex(102);
+ typename Graph::edge_descriptor e1 = g.add_edge(v, u);
+ typename Graph::edge_descriptor e2 = g.add_edge(w, u);
+
+ g.remove_edge(e1);
+ g.remove_edge(e2);
+}
+
+template <typename Graph>
+void test_multi_edge(Graph& g)
+{
+ cout << "*** Add/Delete Multi-Edges" << endl;
+ cout << "*** " << demangle(typeid(Graph).name()) << endl;
+ typename Graph::vertex_descriptor u = g.add_vertex(200);
+ typename Graph::vertex_descriptor v = g.add_vertex(201);
+ g.add_edge(u, v);
+ g.add_edge(v, u);
     g.add_edge(u, v);
+ g.add_edge(v, u);
+ g.remove_edges(u, v);
+}
+
+template <typename Graph>
+void print_verts(Graph& g)
+{
+ typename Graph::vertex_range rng = g.vertices();
+ for( ; rng.first != rng.second; ++rng.first) {
+ typename Graph::vertex_descriptor v = *rng.first;
+ cout << "vert: " << g[v] << " w/degree == " << g.degree(v) << endl;
+ }
 }
 
 int main()
 {
+ vec_vec();
+ cout << endl << endl;
     list_list();
     cout << endl << endl;
- vec_vec();
+ set_set();
     cout << endl << endl;
 
     return 0;
 }
 
+void vec_vec()
+{
+ typedef undirected_graph<City, Road, vertex_vector, edge_vector> Graph;
+
+ Graph g;
+ add_verts(g);
+ add_edges(g);
+}
+
 void list_list()
 {
     typedef undirected_graph<City, Road, vertex_list, edge_list> Graph;
 
     Graph g;
- cout << demangle(typeid(Graph).name()) << endl;
     add_verts(g);
+ add_and_del_edges(g);
+ test_multi_edge(g);
 }
 
-void vec_vec()
+
+void set_set()
 {
- typedef undirected_graph<City, Road, vertex_vector, edge_vector> Graph;
+ typedef undirected_graph<City, Road, vertex_set<>, edge_set<> > Graph;
 
     Graph g;
- cout << demangle(typeid(Graph).name()) << endl;
     add_verts(g);
- add_edges(g);
+ add_and_del_edges(g);
+ test_multi_edge(g);
 }
 

Date view Thread view Subject view Author view

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