[Boost-commit] svn:boost r46625 - in sandbox/SOC/2008/graphs/trunk: boost/graphs libs/graphs

From: asutton_at_[hidden]
Date: 2008-06-23 09:44:11

Author: asutton
Date: 2008-06-23 09:44:09 EDT (Mon, 23 Jun 2008)
New Revision: 46625
URL: http://svn.boost.org/trac/boost/changeset/46625

Log:
Started rewriting the directed edge set code to support the notion of "other"
edges (the corresponding in/out edge). This is the only way to support fast
removals for non-vector stores since not having this requires searches on
the in set.

Added the placeholder class (probably wants a rename) that abstracts the
convertabiltiy of arbitrary types over their underlying memory.

Added:
   sandbox/SOC/2008/graphs/trunk/boost/graphs/placeholder.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp   |    30 ++--                                    
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp  |    49 +++++-                                  
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp |    25 +-                                      
   sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp     |    26 ++-                                     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp       |    18 +                                       
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp      |    47 +++---                                  
   sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile              |     1                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp               |   268 +++++++++++++++++++++++++++++++++++++-- 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp               |   166 +++++++++++++++++++++++                 
   9 files changed, 533 insertions(+), 97 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp	2008-06-23 09:44:09 EDT (Mon, 23 Jun 2008)
@@ -2,29 +2,31 @@
 #ifndef DIRECTED_EDGE_HPP
 #define DIRECTED_EDGE_HPP
 
+#include <boost/tuple/tuple.hpp>
+
 /**
  * A directed edge represents an edge in a directed graph. A directed edge is
- * uniquely identified by its source and target verties and edge property.
+ * uniquely identified by its source and target vertices and edge property.
  *
  * @param VertexDesc A vertex descriptor
  * @param OutDesc An out edge descriptor.
  */
-template <typename VertexDesc, typename OutDesc>
+template <typename OutTuple>
 class directed_edge
 {
 public:
-    typedef VertexDesc vertex_descriptor;
-    typedef OutDesc out_descriptor;
-    typedef typename out_descriptor::edge_properties edge_properties;
+    typedef OutTuple out_tuple;
+    typedef typename boost::tuples::element<0, OutTuple>::type vertex_descriptor;
+    typedef typename boost::tuples::element<1, OutTuple>::type edge_properties;
 
     /** @name Constructors */
     //@{
     inline directed_edge()
         : _src()
-        , _out()
+        , _out(0)
     { }
 
-    inline directed_edge(vertex_descriptor v, OutDesc o)
+    inline directed_edge(vertex_descriptor v, OutTuple const* o)
         : _src(v)
         , _out(o)
     { }
@@ -36,21 +38,17 @@
 
     /** Return the target of the edge. */
     inline vertex_descriptor target() const
-    { return _out.target(); }
-
-    /** Return the out edge descriptor. */
-    inline out_descriptor out_edge() const
-    { return _out; }
+    { return boost::get<0>(*_out); }
 
     /** @name Property Accessors
      * Return the properties associated with the edge.
      */
     //@{
     inline edge_properties& properties()
-    { return _out.properties(); }
+    { return boost::get<1>(*_out); }
 
     inline edge_properties const& properties() const
-    { return _out.properties(); }
+    { return boost::get<1>(*_out); }
     //@}
 
     /** @name Operators */
@@ -66,8 +64,8 @@
     //@}
 
 private:
-    VertexDesc  _src;
-    OutDesc     _out;
+    vertex_descriptor   _src;
+    OutTuple const*     _out;
 };
 
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp	2008-06-23 09:44:09 EDT (Mon, 23 Jun 2008)
@@ -18,6 +18,18 @@
 // Note that directed graphs maintain an independent edge count since the actual
 // count would basically require a search.
 
+// Apparently directed graphs can be challenging - especially when you're
+// talking about in and out edges. Let's start with the basics - out edges. Each
+// out edge of a vertex references a target vertex descriptor and the properties
+// of that edge. However, there is an additional in edge that needs to be
+// accounted for (in another vertex no less). We could augment each out edge
+// with an iterator to its corresponding in edge.
+//
+// Each in edge is similarly defined. Minimally, this could contain only the
+// source vertex and a reference to the properties that define that edge. In
+// order to provide quick access to it "other half", it needs a reference to
+// the out edge (which could be implemented as an iterator of some kind).
+
 #include "none.hpp"
 
 #include "directed_vertex.hpp"
@@ -58,11 +70,10 @@
     // edge stores for the graph. Get the out edge descriptor type from the out
     // store.
     typedef typename EdgeStore::template out_store<vertex_descriptor, edge_properties>::type out_edge_store;
-    typedef typename out_edge_store::out_descriptor out_descriptor;
-    typedef typename EdgeStore::template in_store<vertex_descriptor, out_descriptor>::type in_edge_store;
+    typedef typename EdgeStore::template in_store<vertex_descriptor>::type in_edge_store;
 
     // We can now generate the edge descriptor.
-    typedef directed_edge<vertex_descriptor, out_descriptor> edge_descriptor;
+    typedef directed_edge<typename out_edge_store::out_tuple> edge_descriptor;
 
     // Generate the vertex type over the vertex properties, and in/out stores.
     // We can also pull size
@@ -392,28 +403,42 @@
                                       vertex_descriptor v,
                                       edge_properties const& ep)
 {
+    typedef typename out_edge_store::out_tuple out_tuple;
+    typedef typename in_edge_store::in_pair in_pair;
+    typedef typename vertex_type::out_iterator out_iterator;
+    typedef typename vertex_type::in_iterator in_iterator;
+
     vertex_type &src = _verts.vertex(u);
     vertex_type &tgt = _verts.vertex(v);
 
     // Do we add the edge or not?
-    std::pair<out_descriptor, bool> ins = src.allow(v);
+    std::pair<out_iterator, bool> ins = src.allow(v);
     if(ins.second) {
         // The addition is allowed... Was there already an edge there? If not,
         // connect u to v (and vice-versa) with the given properties. Otherwise,
         // just return the existing edge.
         edge_descriptor e;
-        // Yuck. Is there no better way to this (i.e., provide some kind of
-        // switch for validity?).
-        if(ins.first.iter == src.end_out()) {
-            out_descriptor o = src.connect_target(v, ep);
-            tgt.connect_source(u, o);
-            e = edge_descriptor(u, o);
+
+        // If the returned iterator is past the end, then we have to create and
+        // connect the edge.
+        if(ins.first == src.end_out()) {
+            // Insert the edge stubs, getting iterators to each stub.
+            out_iterator i = src.connect_target(v, ep);
+            in_iterator j = tgt.connect_source(u);
+
+            // Biconnect the stubs. This relies heavily on the fact that these
+            // placeholders aren't squashing the underlying memory.
+            out_tuple& x = const_cast<out_tuple&>(*i);
+            in_pair& y = const_cast<in_pair&>(*j);
+            boost::get<2>(x).put(i);
+            y.second.put(j);
+            e = edge_descriptor(u, &*i);
         }
         else {
-            e = edge_descriptor(u, ins.first);
+            e = edge_descriptor(u, &*ins.first);
         }
 
-        // Remember that we're allocating the edge.
+        // Increment the edge count.
         ++_edges;
         return e;
     }

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp	2008-06-23 09:44:09 EDT (Mon, 23 Jun 2008)
@@ -17,7 +17,6 @@
     typedef typename out_store::vertex_descriptor vertex_descriptor;
 
     typedef typename OutStore::edge_properties edge_properties;
-    typedef typename OutStore::out_descriptor out_descriptor;
 
     typedef typename out_store::const_iterator out_iterator;
     typedef typename out_store::size_type out_size_type;
@@ -44,13 +43,13 @@
     //@}
 
 
-    std::pair<out_descriptor, bool> allow(vertex_descriptor);
+    std::pair<out_iterator, bool> allow(vertex_descriptor) const;
 
-    out_descriptor connect_target(vertex_descriptor, edge_properties const&);
-    void connect_source(vertex_descriptor, out_descriptor);
+    out_iterator connect_target(vertex_descriptor, edge_properties const&);
+    in_iterator connect_source(vertex_descriptor);
 
-    void disconnect_target(out_descriptor);
-    void disconnect_source(vertex_descriptor);
+    // void disconnect_target(out_descriptor);
+    // void disconnect_source(vertex_descriptor);
 
     /** @name Property Accessors */
     //@{
@@ -120,8 +119,8 @@
  * be added anyways.
  */
 template <typename V, typename O, typename I>
-std::pair<typename directed_vertex<V,O,I>::out_descriptor, bool>
-directed_vertex<V,O,I>::allow(vertex_descriptor v)
+std::pair<typename directed_vertex<V,O,I>::out_iterator, bool>
+directed_vertex<V,O,I>::allow(vertex_descriptor v) const
 {
     return _out.allow(v);
 }
@@ -131,7 +130,7 @@
  * edge descriptor for the new edge.
  */
 template <typename V, typename O, typename I>
-typename directed_vertex<V,O,I>::out_descriptor
+typename directed_vertex<V,O,I>::out_iterator
 directed_vertex<V,O,I>::connect_target(vertex_descriptor v, edge_properties const& ep)
 {
     return _out.add(std::make_pair(v, ep));
@@ -144,12 +143,13 @@
  * don't actually have a descriptor for this vertex.
  */
 template <typename V, typename O, typename I>
-void
-directed_vertex<V,O,I>::connect_source(vertex_descriptor v, out_descriptor o)
+typename directed_vertex<V,O,I>::in_iterator
+directed_vertex<V,O,I>::connect_source(vertex_descriptor v)
 {
-    return _in.add(std::make_pair(v, o));
+    return _in.add(v);
 }
 
+#if 0
 /**
  * Disconnect this vertex from its target, removing the outgoing edge.
  */
@@ -169,5 +169,6 @@
 {
     _in.remove(v);
 }
+#endif
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp	2008-06-23 09:44:09 EDT (Mon, 23 Jun 2008)
@@ -2,6 +2,9 @@
 #ifndef EDGE_VECTOR_HPP
 #define EDGE_VECTOR_HPP
 
+#include <boost/tuple/tuple.hpp>
+
+#include "placeholder.hpp"
 #include "property_vector.hpp"
 #include "incidence_vector.hpp"
 #include "out_vector.hpp"
@@ -61,20 +64,29 @@
     template <typename VertexDesc, typename Props>
     struct out_store
     {
-        typedef std::pair<VertexDesc, Props> out_pair;
-        typedef FirstAlloc<out_pair> out_allocator;
-        typedef out_vector<out_pair, out_allocator> type;
+        // Define a dummy type that eventually be used to store iterators to
+        // in edge iterators. The actual out edge type is a tuple of target
+        // vertex, edge properties, and in edge iterator (placeheld). The in
+        // edge type is the source vertex and the out edge iterator (placeheld).
+        typedef placeholder<sizeof(typename std::vector<int>::iterator)> dummy_type;
+        typedef boost::tuple<VertexDesc, Props, dummy_type> edge;
+        typedef FirstAlloc<edge> allocator;
+        typedef out_vector<edge, allocator> type;
     };
 
     // The in store metafunction generates the type of vector used to store
     // incoming edges of directed graph. In edges are represented by the
     // referencing vertex and an out edge descriptor.
-    template <typename VertexDesc, typename OutDesc>
+    template <typename VertexDesc>
     struct in_store
     {
-        typedef std::pair<VertexDesc, OutDesc> in_pair;
-        typedef SecondAlloc<in_pair> in_allocator;
-        typedef in_vector<in_pair, in_allocator> type;
+        // Define a dummy type that will ultimately act as a placeholder for
+        // an iterator into the out edge vector. Use that to define the in edge
+        // pair.
+        typedef placeholder<sizeof(typename std::vector<int>::iterator)> dummy_type;
+        typedef std::pair<VertexDesc, dummy_type> edge;
+        typedef SecondAlloc<edge> allocator;
+        typedef in_vector<edge, allocator> type;
     };
 };
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp	2008-06-23 09:44:09 EDT (Mon, 23 Jun 2008)
@@ -18,8 +18,10 @@
 public:
     typedef Edge in_pair;
     typedef typename Edge::first_type vertex_descriptor;
-    typedef typename Edge::second_type edge_descriptor;
-
+private:
+    typedef typename Edge::second_type out_edge_place;
+public:
+    typedef typename store_type::iterator iterator;
     typedef typename store_type::const_iterator const_iterator;
     typedef typename store_type::size_type size_type;
 
@@ -27,9 +29,15 @@
         : _edges()
     { }
 
-    /** Add the edge to the vector. */
-    void add(in_pair e)
-    { _edges.push_back(e); }
+    /**
+     * Add the edge to the vector, returning an iterator to the added element.
+     * @complexity O(1)
+     */
+    const_iterator add(vertex_descriptor e)
+    {
+        _edges.push_back(std::make_pair(e, out_edge_place()));
+        return boost::prior(_edges.end());
+    }
 
     /** Get the number of incoming edges (in degree). */
     size_type size() const

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp	2008-06-23 09:44:09 EDT (Mon, 23 Jun 2008)
@@ -4,20 +4,17 @@
 
 #include <vector>
 
+#include <boost/tuple/tuple.hpp>
+
+#include "placeholder.hpp"
 #include "out_descriptor.hpp"
 
 /**
- * The out vector implements vector-based, out-edge storage for directed graphs.
- * out-edges are uniquely identified by their target vertex and property
- * descriptor. As an out-edge store, this type stores an edge property with the
- * target vertex descriptor. Vector-based stores support fast inserts, slow
- * finds, and do not allow remove operations.
- *
- * The edge is required to be a pair containing a vertex descriptor and a edge
- * property (not descriptor). This type defines the out_descriptor - an opaque
- * reference to a target/property pair.
+ * The in/out vector implements vector-based, edge storage for directed graphs.
+ * Each out edge is capable of referencing its corresponding in edge in another
+ * vertex and vice-versa.
  *
- * @param Edge A pair describing a vertex descriptor and the edge properties.
+ * @param Edge A tuple describing the out edge type.
  * @param Alloc The allocator for edge pairs.
  */
 template <typename Edge, typename Alloc>
@@ -25,31 +22,36 @@
 {
     typedef std::vector<Edge, Alloc> store_type;
 public:
-    typedef Edge out_pair;
-    typedef typename Edge::first_type vertex_descriptor;
-    typedef typename Edge::second_type edge_properties;
-
+    typedef Edge out_tuple;
+    typedef typename boost::tuples::element<0, Edge>::type vertex_descriptor;
+    typedef typename boost::tuples::element<1, Edge>::type edge_properties;
+private:
+    typedef typename boost::tuples::element<2, Edge>::type in_edge_place;
+public:
+    typedef std::pair<vertex_descriptor, edge_properties> out_pair;
+    typedef typename store_type::iterator iterator;
     typedef typename store_type::const_iterator const_iterator;
     typedef typename store_type::size_type size_type;
 
-    typedef basic_out_descriptor<const_iterator> out_descriptor;
-
     inline out_vector()
         : _edges()
     { }
 
-    /** Allow the addition? */
-    std::pair<out_descriptor, bool> allow(vertex_descriptor v)
+    /**
+     * Allow the edge addition? Unless policy dictates otherwise, always allow
+     * the addition of the edge.
+     */
+    std::pair<const_iterator, bool> allow(vertex_descriptor v) const
     { return std::make_pair(_edges.end(), true); }
 
     /**
      * Add the edge to the vector.
      * @complexity O(1)
      */
-    out_descriptor add(out_pair e)
+    const_iterator add(out_pair e)
     {
-        _edges.push_back(e);
-        return out_descriptor(boost::prior(_edges.end()));
+        _edges.push_back(out_tuple(e.first, e.second, in_edge_place()));
+        return boost::prior(_edges.end());
     }
 
     /** Get the number of outgoing edges. */
@@ -63,8 +65,7 @@
 
     inline const_iterator end() const
     { return _edges.end(); }
-
-    //@{
+    //@}
 
 private:
     store_type _edges;

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/placeholder.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/placeholder.hpp	2008-06-23 09:44:09 EDT (Mon, 23 Jun 2008)
@@ -0,0 +1,50 @@
+
+#ifndef PLACEHOLDER_HPP
+#define PLACEHOLDER_HPP
+
+#include <algorithm>
+
+#include <boost/static_assert.hpp>
+
+/**
+ * The placeholder type is used to allocate a small buffer of memory that can
+ * be reinterpreted as a type of the same size. This is used solely as a means
+ * of deferring the immediate need for the type of an object if you can guess
+ * its size.
+ *
+ * If you're going to write something hacky, you may as well try to make it a
+ * little bit pretty.
+ */
+template <int N>
+struct placeholder
+{
+    inline placeholder()
+        : mem()
+    { std::fill(mem, mem + N, 0); }
+
+    template <typename T>
+    inline placeholder(const T& x)
+        : mem()
+    { put(x); }
+
+    /** Put the value of x into the placeholder. */
+    template <typename T>
+    inline void put(T const& x)
+    {
+        BOOST_STATIC_ASSERT(sizeof(T) == N);
+        char const* p = reinterpret_cast<char const*>(&x);
+        copy(p, p + N, mem);
+    }
+
+    /** Get the value of the placeholder and return it as an object of type T. */
+    template <typename T>
+    inline T get() const
+    {
+        BOOST_STATIC_ASSERT(sizeof(T) == N);
+        return *reinterpret_cast<T*>(mem);
+    }
+
+    mutable char mem[N];
+};
+
+#endif

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile	2008-06-23 09:44:09 EDT (Mon, 23 Jun 2008)
@@ -3,3 +3,4 @@
 exe di : di.cpp : <include>../../ <include>/usr/local/include ;
 exe set : set.cpp : <include>../../ <include>/usr/local/include ;
 exe map : map.cpp : <include>../../ <include>/usr/local/include ;
+exe test : test.cpp : <include>../../ <include>/usr/local/include ;

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp	2008-06-23 09:44:09 EDT (Mon, 23 Jun 2008)
@@ -1,35 +1,271 @@
 
 #include <iostream>
+#include <set>
 
+#include <boost/assert.hpp>
+#include <boost/utility.hpp>
 #include <boost/graphs/directed_graph.hpp>
+#include <boost/graphs/traits.hpp>
 
-#include "test.hpp"
+#include "demangle.hpp"
 
 using namespace std;
 using namespace boost;
 
+typedef int City;
+typedef int Road;
 
-int main()
+void list_list();
+void vec_vec();
+void set_set();
+
+template <typename Graph>
+void print_types(const Graph&)
 {
-    typedef directed_graph<int, int, vertex_vector, edge_vector> Graph;
-    typedef Graph::vertex_descriptor Vertex;
-    typedef Graph::edge_descriptor Edge;
+    cout << demangle(typeid(typename Graph::property_descriptor).name()) << endl;
+    cout << demangle(typeid(typename Graph::vertex_descriptor).name()) << endl;
+    cout << demangle(typeid(typename Graph::edge_descriptor).name()) << endl;
+    cout << demangle(typeid(typename Graph::property_store).name()) << endl;
+    cout << demangle(typeid(typename Graph::vertex_store).name()) << endl;
+}
 
+template <typename Graph>
+void test_add_vertices()
+{
     Graph g;
-    Vertex u = g.add_vertex(1);
-    Vertex v = g.add_vertex(2);
-    Vertex w = g.add_vertex(3);
+    list<typename Graph::vertex_descriptor> V;
+    for(int i = 0; i < 5; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+}
 
-    Edge e1 = g.add_edge(u, v, 1);
-    Edge e2 = g.add_edge(w, v, 2);
+template <typename Graph>
+void test_add_remove_vertices()
+{
+    Graph g;
+    list<typename Graph::vertex_descriptor> V;
+    for(int i = 0; i < 5; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    BOOST_ASSERT(g.num_vertices() == 5);
+    while(!V.empty()) {
+        g.remove_vertex(V.front());
+        V.pop_front();
+    }
+    BOOST_ASSERT(g.num_vertices() == 0);
+}
 
-    cout << "d_out(u): " << g.out_degree(u) << endl;
-    cout << "d_in(u): " << g.in_degree(u) << endl;
-    cout << "d(u): " << g.degree(u) << endl;
+template <typename Graph>
+void test_add_edges()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+    BOOST_ASSERT(g.degree(V[0]) == 2);
+    BOOST_ASSERT(g.out_degree(V[0]) == 1);
+    BOOST_ASSERT(g.in_degree(V[0]) == 1);
+}
 
-    cout << "d_out(v): " << g.out_degree(v) << endl;
-    cout << "d_in(v): " << g.in_degree(v) << endl;
-    cout << "d(v): " << g.degree(v) << endl;
+template <typename Graph>
+void test_add_remove_edges()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    E.push_back(g.add_edge(V[0], V[1]));
+    E.push_back(g.add_edge(V[1], V[2]));
+    E.push_back(g.add_edge(V[2], V[0]));
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+    BOOST_ASSERT(g.degree(V[0]) == 2);
+    BOOST_ASSERT(g.out_degree(V[0]) == 1);
+    BOOST_ASSERT(g.in_degree(V[0]) == 1);
+
+    g.remove_edge(E.front());
+    BOOST_ASSERT(g.degree(V[1]) == 1);
+    BOOST_ASSERT(g.out_degree(V[0]) == 0);
+    BOOST_ASSERT(g.in_degree(V[0]) == 1);
+    E.pop_front();
+
+    g.remove_edge(E.front());
+    BOOST_ASSERT(g.degree(V[1]) == 0);
+    E.pop_front();
+}
+
+template <typename Graph>
+void test_disconnect_vertex()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+
+    g.disconnect_vertex(V[1]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.degree(V[1]) == 0);
+    BOOST_ASSERT(g.degree(V[0]) == 1);
+    BOOST_ASSERT(g.degree(V[2]) == 1);
+}
+
+// This is a little different than above. We remove a vertex from the triangle,
+// which implicitly disconnects it.
+template <typename Graph>
+void test_implicit_disconnect_vertex()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+
+    g.remove_vertex(V[1]);
+    BOOST_ASSERT(g.num_vertices() == 2);
+    BOOST_ASSERT(g.degree(V[0]) == 1);
+    BOOST_ASSERT(g.degree(V[2]) == 1);
+}
+
+template <typename Graph>
+void test_add_multi_edges()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    g.add_edge(u, v);
+    g.add_edge(v, u);
+    g.add_edge(u, v);
+    g.add_edge(v, u);
+
+    BOOST_ASSERT(g.num_vertices() == 2);
+    if(allows_parallel_edges(g)) {
+        BOOST_ASSERT(g.num_edges() == 1);
+    }
+    else {
+        BOOST_ASSERT(g.num_edges() == 4);
+    }
+}
+
+template <typename Graph>
+void test_remove_multi_edges()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    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);
+    BOOST_ASSERT(g.num_edges() == 0);
+}
+
+template <typename Graph>
+void test_incidence_iterator()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    g.add_edge(u, v, 1);
+    g.add_edge(v, u, 2);
+    g.add_edge(u, v, 3);
+    g.add_edge(v, u, 4);
+
+    typename Graph::incident_edge_range x = g.incident_edges(v);
+    for( ; x.first != x.second; ++x.first) {
+        // cout << "test: " << g[*x.first] << endl;
+    }
+}
+
+template <typename Graph>
+void test_adjacency_iterator()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    g.add_edge(u, v, 1);
+    g.add_edge(v, u, 2);
+    g.add_edge(u, v, 3);
+    g.add_edge(v, u, 4);
+
+    typename Graph::adjacent_vertex_range x = g.adjacent_vertices(v);
+    for( ; x.first != x.second; ++x.first) {
+        // cout << "test: " << g[*x.first] << endl;
+    }
+}
+
+int main()
+{
+    vec_vec();
+    list_list();
+    set_set();
 
     return 0;
 }
+
+void vec_vec()
+{
+    cout << "---- vec/vec ----" << endl;
+    typedef directed_graph<City, Road, vertex_vector, edge_vector> Graph;
+    test_add_vertices<Graph>();
+    test_add_edges<Graph>();
+    // test_add_multi_edges<Graph>();
+    // test_incidence_iterator<Graph>();
+    // test_adjacency_iterator<Graph>();
+}
+
+void list_list()
+{
+    /*
+    cout << "---- list/list ----" << endl;
+    typedef directed_graph<City, Road, vertex_list, edge_list> Graph;
+    test_add_remove_vertices<Graph>();
+    test_add_remove_edges<Graph>();
+    // test_disconnect_vertex<Graph>();
+    // test_implicit_disconnect_vertex<Graph>();
+    test_add_multi_edges<Graph>();
+    // test_remove_multi_edges<Graph>();
+    // test_incidence_iterator<Graph>();
+    // test_adjacency_iterator<Graph>();
+    */
+}
+
+
+void set_set()
+{
+    /*
+    cout << "---- set/set ----" << endl;
+    typedef directed_graph<City, Road, vertex_set<>, edge_set<> > Graph;
+    test_add_remove_vertices<Graph>();
+    // test_add_remove_edges<Graph>();
+    // test_disconnect_vertex<Graph>();
+    // test_implicit_disconnect_vertex<Graph>();
+    test_add_multi_edges<Graph>();
+    // test_remove_multi_edges<Graph>();
+    // test_incidence_iterator<Graph>();
+    // test_adjacency_iterator<Graph>();
+    */
+}
+

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp	2008-06-23 09:44:09 EDT (Mon, 23 Jun 2008)
@@ -0,0 +1,44 @@
+
+#include <iostream>
+#include <string>
+#include <list>
+
+#include <boost/next_prior.hpp>
+#include <boost/graphs/placeholder.hpp>
+
+using namespace std;
+using namespace boost;
+
+struct Vertex
+{
+    Vertex(string n, int w)
+        : name(n), weight(w)
+    { }
+
+    string name;
+    int weight;
+};
+
+inline ostream& operator<<(ostream& os, Vertex const& v)
+{ return os << v.name << " " << v.weight; }
+
+int main()
+{
+    typedef list<Vertex> List;
+    typedef List::iterator Iterator;
+
+    typedef list<int>::iterator Dummy;
+    typedef placeholder<sizeof(Dummy)> Reference;
+
+    List verts;
+    verts.push_back(Vertex("a", 1));
+    verts.push_back(Vertex("b", 2));
+
+    Reference x(verts.begin());
+    Reference y(prior(verts.end()));
+
+    cout << *x.get<Iterator>() << endl;
+    cout << *y.get<Iterator>() << endl;
+
+    return 0;
+}

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp	2008-06-23 09:44:09 EDT (Mon, 23 Jun 2008)
@@ -5,6 +5,7 @@
 #include <boost/assert.hpp>
 #include <boost/utility.hpp>
 #include <boost/graphs/undirected_graph.hpp>
+#include <boost/graphs/traits.hpp>
 
 #include "demangle.hpp"
 
@@ -56,7 +57,7 @@
 }
 
 template <typename Graph>
-void test_make_simple_triangle()
+void test_add_edges()
 {
     Graph g;
     vector<typename Graph::vertex_descriptor> V;
@@ -70,6 +71,143 @@
     BOOST_ASSERT(g.num_edges() == 3);
 }
 
+template <typename Graph>
+void test_add_remove_edges()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    E.push_back(g.add_edge(V[0], V[1]));
+    E.push_back(g.add_edge(V[1], V[2]));
+    E.push_back(g.add_edge(V[2], V[0]));
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+
+    g.remove_edge(E.front());
+    BOOST_ASSERT(g.degree(V[1]) == 1);
+    E.pop_front();
+
+    g.remove_edge(E.front());
+    BOOST_ASSERT(g.degree(V[1]) == 0);
+    E.pop_front();
+}
+
+template <typename Graph>
+void test_disconnect_vertex()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+
+    g.disconnect_vertex(V[1]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.degree(V[1]) == 0);
+    BOOST_ASSERT(g.degree(V[0]) == 1);
+    BOOST_ASSERT(g.degree(V[2]) == 1);
+}
+
+// This is a little different than above. We remove a vertex from the triangle,
+// which implicitly disconnects it.
+template <typename Graph>
+void test_implicit_disconnect_vertex()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+
+    g.remove_vertex(V[1]);
+    BOOST_ASSERT(g.num_vertices() == 2);
+    BOOST_ASSERT(g.degree(V[0]) == 1);
+    BOOST_ASSERT(g.degree(V[2]) == 1);
+}
+
+template <typename Graph>
+void test_add_multi_edges()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    g.add_edge(u, v);
+    g.add_edge(v, u);
+    g.add_edge(u, v);
+    g.add_edge(v, u);
+
+    BOOST_ASSERT(g.num_vertices() == 2);
+    if(allows_parallel_edges(g)) {
+        BOOST_ASSERT(g.num_edges() == 1);
+    }
+    else {
+        BOOST_ASSERT(g.num_edges() == 4);
+    }
+}
+
+template <typename Graph>
+void test_remove_multi_edges()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    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);
+    BOOST_ASSERT(g.num_edges() == 0);
+}
+
+template <typename Graph>
+void test_incidence_iterator()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    g.add_edge(u, v, 1);
+    g.add_edge(v, u, 2);
+    g.add_edge(u, v, 3);
+    g.add_edge(v, u, 4);
+
+    typename Graph::incident_edge_range x = g.incident_edges(v);
+    for( ; x.first != x.second; ++x.first) {
+        // cout << "test: " << g[*x.first] << endl;
+    }
+}
+
+template <typename Graph>
+void test_adjacency_iterator()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    g.add_edge(u, v, 1);
+    g.add_edge(v, u, 2);
+    g.add_edge(u, v, 3);
+    g.add_edge(v, u, 4);
+
+    typename Graph::adjacent_vertex_range x = g.adjacent_vertices(v);
+    for( ; x.first != x.second; ++x.first) {
+        // cout << "test: " << g[*x.first] << endl;
+    }
+}
 
 int main()
 {
@@ -82,25 +220,41 @@
 
 void vec_vec()
 {
+    cout << "---- vec/vec ----" << endl;
     typedef undirected_graph<City, Road, vertex_vector, edge_vector> Graph;
     test_add_vertices<Graph>();
-    test_make_simple_triangle<Graph>();
+    test_add_edges<Graph>();
+    test_add_multi_edges<Graph>();
+    test_incidence_iterator<Graph>();
+    test_adjacency_iterator<Graph>();
 }
 
 void list_list()
 {
+    cout << "---- list/list ----" << endl;
     typedef undirected_graph<City, Road, vertex_list, edge_list> Graph;
-
-    Graph g;
     test_add_remove_vertices<Graph>();
-    test_make_simple_triangle<Graph>();
+    test_add_remove_edges<Graph>();
+    test_disconnect_vertex<Graph>();
+    test_implicit_disconnect_vertex<Graph>();
+    test_add_multi_edges<Graph>();
+    test_remove_multi_edges<Graph>();
+    test_incidence_iterator<Graph>();
+    test_adjacency_iterator<Graph>();
 }
 
 
 void set_set()
 {
+    cout << "---- set/set ----" << endl;
     typedef undirected_graph<City, Road, vertex_set<>, edge_set<> > Graph;
     test_add_remove_vertices<Graph>();
-    test_make_simple_triangle<Graph>();
+    test_add_remove_edges<Graph>();
+    test_disconnect_vertex<Graph>();
+    test_implicit_disconnect_vertex<Graph>();
+    test_add_multi_edges<Graph>();
+    test_remove_multi_edges<Graph>();
+    test_incidence_iterator<Graph>();
+    test_adjacency_iterator<Graph>();
 }