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);
}