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

From: asutton_at_[hidden]
Date: 2008-07-08 12:50:27

Author: asutton
Date: 2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
New Revision: 47236
URL: http://svn.boost.org/trac/boost/changeset/47236

Log:
Started rewriting the undirected graph and its test suite.

Added:
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_types.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/boost/ordered_pair.hpp
      - copied unchanged from r47212, /sandbox/SOC/2008/graphs/trunk/boost/graphs/ordered_pair.hpp
   sandbox/SOC/2008/graphs/trunk/boost/unordered_pair.hpp
      - copied unchanged from r47212, /sandbox/SOC/2008/graphs/trunk/boost/graphs/unordered_pair.hpp
   sandbox/SOC/2008/graphs/trunk/libs/graphs/in_edge_traits.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/out_edge_traits.hpp   (contents, props changed)
Removed:
   sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_iterator.hpp
   sandbox/SOC/2008/graphs/trunk/boost/graphs/ordered_pair.hpp
   sandbox/SOC/2008/graphs/trunk/boost/graphs/unordered_pair.hpp
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/blob.hpp                      |     2                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp |    32 --                                      
   sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp          |    34 +--                                     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp           |    39 +--                                     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp        |    34 +--                                     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp            |    10                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp             |    10                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp          |     6                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp |    67 ++----                                  
   sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp     |    34 ++                                      
   sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp      |    34 ++-                                     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp   |    33 +++                                     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp           |    12 +                                       
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp            |    22 +                                       
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp         |    20 +                                       
   sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp      |     2                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp    |     2                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp    |   103 ++++------                              
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp   |   141 ++++++---------                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp  |    68 ++-----                                 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/utility.hpp            |    85 ++++++++                                
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp    |   372 +++------------------------------------ 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp        |     6                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp         |    12                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp         |    16                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp      |    11                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile                 |     4                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp             |   153 ++++++++++++----                        
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp          |     2                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp                  |    22 +-                                      
   30 files changed, 595 insertions(+), 793 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/boost/blob.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/blob.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/blob.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -94,7 +94,7 @@
 {
     using boost::hash_value;
     std::size_t seed = 0;
-    for(int i = 0; i < N; ++i) {
+    for(unsigned int i = 0; i < N; ++i) {
         boost::hash_combine(seed, x.mem[i]);
     }
     return seed;

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -5,24 +5,19 @@
 #include <iterator>
 
 /**
- * The adjacency iterator is an abstraction over incidence iterators (provided
- * by the incidence store). The adjacency iterator actually provides the same
- * functionality as the incidence iterator, but simply provides access to the
- * other vertices rather than the edges.
- *
- * @todo Depending on the underlying incidence iterator provided by the graph,
- * we could actually possibly make this a random access iterator rather than
- * just a bidirectional iterator. For now, we force it to be a bidi iterator.
+ * The adjacency iterator is an abstraction over incidence iterators. The
+ * adjacency iterator actually provides the same functionality as the incidence
+ * iterator, but simply provides access to the other vertices rather than the
+ * edges.
  */
 template <typename Iterator>
 class adjacency_iterator
 {
     typedef Iterator iterator;
     typedef typename Iterator::vertex_descriptor vertex_descriptor;
-public:
 
-    typedef std::bidirectional_iterator_tag iterator_category;
-    typedef std::size_t difference_type;
+    typedef typename iterator::iterator_category iterator_category;
+    typedef typename iterator::difference_type difference_type;
     typedef vertex_descriptor value_type;
     typedef vertex_descriptor reference;
     typedef vertex_descriptor pointer;
@@ -37,22 +32,13 @@
     { }
 
     inline adjacency_iterator& operator=(adjacency_iterator const& x)
-    {
-        _iter = x._iter;
-        return *this;
-    }
+    { _iter = x._iter; return *this; }
 
     inline adjacency_iterator& operator++()
-    {
-        ++_iter;
-        return *this;
-    }
+    { ++_iter; return *this; }
 
     inline adjacency_iterator& operator--()
-    {
-        --_iter;
-        return *this;
-    }
+    { --_iter; return *this; }
 
     inline bool operator==(adjacency_iterator const& x) const
     { return _iter == x._iter; }

Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_iterator.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
+++ (empty file)
@@ -1,112 +0,0 @@
-
-#ifndef EDGE_ITERATOR_HPP
-#define EDGE_ITERATOR_HPP
-
-#include <iterator>
-
-// Edge iteration sucks when there's no global edge store. Basically, we have
-// to build a compound iterator that walks over each vertex and over each
-// incident edge. Normally, not a big deal. However, we aren't allowed to
-// backtrack, which means we have to build some method of "marking" which
-// vertices we've already visited.
-//
-// This would be much easier if the vertex iterators were random because we
-// can order them and make that determination in constant time. However, this
-// is not the general case.
-
-namespace detail
-{
-    template <typename Graph, typename Tag>
-    class edge_iterator
-    {
-        typedef typename Graph::vertex_iterator vertex_iterator;
-        typedef typename Graph::incident_edge_iterator incidence_iterator;
-    public:
-
-        typedef int foo;
-    };
-
-    /**
-     * This edge iterator is actually the easiest to implement because the
-     * iterators can be ordered (i.e,. i \< j => *i < *j).
-     */
-    template <typename Graph>
-    class edge_iterator<Graph, std::random_access_iterator_tag>
-    {
-        typedef Graph graph_type;
-        typedef typename Graph::vertex_iterator vertex_iterator;
-        typedef typename Graph::incident_edge_iterator incidence_iterator;
-    public:
-        typedef std::forward_iterator_tag iterator_category;
-
-        typedef typename incidence_iterator::value_type value_type;
-        typedef value_type reference;
-        typedef value_type pointer;
-
-        edge_iterator()
-            : _graph(0)
-            , _vert()
-            , _inc()
-        { }
-
-        edge_iterator(Graph const* g)
-            : _graph(g)
-            , _vert(_graph->begin_vertices())
-            , _inc(next(_graph->begin_incident_edges(*_vert)))
-        { }
-
-        edge_iterator& operator++()
-        {
-            // If we're not at the last of the incident edges for the current
-            // vertex, then we move to the next.
-            if(_inc != _graph->end_incident_edges(*_vert)) {
-                _inc = next(_inc);
-            }
-            else {
-                ++_vert;
-            }
-            return *this;
-        }
-
-        // Dereferencing is easy. Just dereference the underlying incidence
-        // iterator.
-        reference operator*() const
-        { return *_inc; }
-
-        // Move the the next edge iterator.
-        incidence_iterator next(incidence_iterator f)
-        {
-        }
-
-    private:
-        graph_type const*   _graph;
-        vertex_iterator     _vert;
-        incidence_iterator  _inc;
-    };
-}
-
-/**
- * The basic edge iterator is responsible for implementing an iterator over
- * the edges in an undirected graph.
- *
- * We actually implement this type through its specialized base classes.
- */
-template <typename Graph>
-struct basic_edge_iterator
-    : detail::edge_iterator<Graph, typename Graph::vertex_iterator::iterator_category>
-{
-    typedef detail::edge_iterator<Graph, typename Graph::vertex_iterator::iterator_category> base_type;
-
-    basic_edge_iterator()
-        : base_type()
-    { }
-
-    basic_edge_iterator(Graph* g)
-        : base_type(g)
-    { }
-
-};
-
-
-#endif
-

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -2,10 +2,16 @@
 #ifndef EDGE_LIST_HPP
 #define EDGE_LIST_HPP
 
-#include "property_list.hpp"
-#include "incidence_list.hpp"
-// #include "out_list.hpp"
-// #include "in_list.hpp"
+#include <list>
+
+#include <boost/triple.hpp>
+#include <boost/descriptors.hpp>
+
+// Forward declarations
+template <typename, typename> class property_list;
+template <typename, typename> class incidence_list;
+template <typename, typename> class out_list;
+template <typename, typename> class in_list;
 
 // The edge list does two things. First, it indicates that edges will
 // be stored in an incidence list (as opposed to a vector or set).
@@ -49,23 +55,18 @@
         typedef incidence_list<incidence_pair, allocator > type;
     };
 
+
+
     // Descriptor types for directed graphs
     typedef typename descriptor_traits<first_dummy>::descriptor_type out_descriptor;
     typedef typename descriptor_traits<second_dummy>::descriptor_type in_descriptor;
 
-
-    /*
     // The out store metafunction generates the type of list used to store
     // out edges of a vertex in a directed graph.
-    template <typename VertexDesc, typename Props>
+    template <typename VertexDesc, typename EdgeProps>
     struct out_store
     {
-        // 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::list<int>::iterator)> dummy_type;
-        typedef triple<VertexDesc, Props, dummy_type> edge;
+        typedef triple<VertexDesc, EdgeProps, in_descriptor> edge;
         typedef FirstAlloc<edge> allocator;
         typedef out_list<edge, allocator> type;
     };
@@ -76,15 +77,10 @@
     template <typename VertexDesc>
     struct in_store
     {
-        // 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::list<int>::iterator)> dummy_type;
-        typedef std::pair<VertexDesc, dummy_type> edge;
+        typedef std::pair<VertexDesc, out_descriptor> edge;
         typedef SecondAlloc<edge> allocator;
         typedef in_list<edge, allocator> type;
     };
-    */
 };
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -5,10 +5,14 @@
 #include <list>
 #include <map>
 
-#include "property_list.hpp"
-#include "incidence_set.hpp"
-// #include "out_set.hpp"
-// #include "in_set.hpp"
+#include <boost/triple.hpp>
+#include <boost/descriptors.hpp>
+
+// Forward declarations
+template <typename, typename> class property_list;
+template <typename, typename, typename> class incidence_set;
+template <typename, typename, typename> class out_set;
+template <typename, typename, typename> class in_set;
 
 /**
  * The edge set metafunction defines the basic facets of set-based edge
@@ -25,17 +29,18 @@
     template <typename> class SecondAlloc = std::allocator>
 struct edge_set
 {
-    // A couple of dummy vectors used to build descriptors. This looks really
+    // Several dummy containers used to build descriptors. This looks really
     // weird since we're expecting a set type somewhere around here. However,
     // there isn't actually a real "set" used in these stores. The property
     // store only needs to be a list, and the incidence/in/out stores are
     // actually all maps (vertex to something).
     typedef std::map<int, int, Compare<int>, FirstAlloc<int>> first_dummy;
-    typedef std::list<int, SecondAlloc<int>> second_dummy;
+    typedef std::map<int, int, Compare<int>, SecondAlloc<int>> second_dummy;
+    typedef std::list<int, SecondAlloc<int>> prop_dummy;
 
     // Descriptor types for undirected graphs.
     typedef typename descriptor_traits<first_dummy>::descriptor_type incidence_descriptor;
-    typedef typename descriptor_traits<second_dummy>::descriptor_type property_descriptor;
+    typedef typename descriptor_traits<prop_dummy>::descriptor_type property_descriptor;
 
     // The property store metafunnction generates the global store type for
     // undirected graphs. The property list only needs to be a list, not a set.
@@ -58,23 +63,18 @@
         typedef incidence_set<value, compare, allocator> type;
     };
 
+
+
     // Descriptor types for directed graphs
     typedef typename descriptor_traits<first_dummy>::descriptor_type out_descriptor;
     typedef typename descriptor_traits<second_dummy>::descriptor_type in_descriptor;
 
-
-    /*
     // The out store metafunction generates the type of set used to store out
     // edges of a vertex in a directed graph.
-    template <typename VertexDesc, typename Props>
+    template <typename VertexDesc, typename EdgeProps>
     struct out_store
     {
-        // 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 typename hold<std::set<int>::iterator>::type dummy_type;
-        typedef triple<VertexDesc, Props, dummy_type> edge;
+        typedef triple<VertexDesc, EdgeProps, in_descriptor> edge;
         typedef Compare<VertexDesc> compare;
         typedef FirstAlloc<edge> allocator;
         typedef out_set<edge, compare, allocator> type;
@@ -86,16 +86,11 @@
     template <typename VertexDesc>
     struct in_store
     {
-        // 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 typename hold<typename std::set<int>::iterator>::type dummy_type;
-        typedef std::pair<VertexDesc, dummy_type> edge;
+        typedef std::pair<VertexDesc, out_descriptor> edge;
         typedef Compare<VertexDesc> compare;
         typedef SecondAlloc<edge> allocator;
         typedef in_set<edge, compare, allocator> type;
     };
-    */
 };
 
 #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-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -2,10 +2,14 @@
 #ifndef EDGE_VECTOR_HPP
 #define EDGE_VECTOR_HPP
 
-#include "property_vector.hpp"
-#include "incidence_vector.hpp"
-// #include "out_vector.hpp"
-// #include "in_vector.hpp"
+#include <boost/triple.hpp>
+#include <boost/descriptors.hpp>
+
+// Forward declarations
+template <typename, typename> class property_vector;
+template <typename, typename> class incidence_vector;
+template <typename, typename> class out_vector;
+template <typename, typename> class in_vector;
 
 // What's in an edge vector? Basically, an edge vector has to specify
 // the type of property storage and the type of incidence storage. What
@@ -65,23 +69,18 @@
         typedef incidence_vector<incidence_pair, incidence_allocator> type;
     };
 
-    // Descriptor types for directed graphs
+
+
+    // Descriptor types for directed graphs.
     typedef typename descriptor_traits<first_dummy>::descriptor_type out_descriptor;
     typedef typename descriptor_traits<second_dummy>::descriptor_type in_descriptor;
 
-
     // The out store metafunction generates the type of vector used to store
     // out edges of a vertex in a directed graph.
-    /*
-    template <typename VertexDesc, typename Props>
+    template <typename VertexDesc, typename EdgeProps>
     struct out_store
     {
-        // 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 typename hold<typename std::vector<int>::iterator>::type dummy_type;
-        typedef triple<VertexDesc, Props, dummy_type> edge;
+        typedef triple<VertexDesc, EdgeProps, in_descriptor> edge;
         typedef FirstAlloc<edge> allocator;
         typedef out_vector<edge, allocator> type;
     };
@@ -92,15 +91,10 @@
     template <typename VertexDesc>
     struct in_store
     {
-        // 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 typename hold<typename std::vector<int>::iterator>::type dummy_type;
-        typedef std::pair<VertexDesc, dummy_type> edge;
+        typedef std::pair<VertexDesc, out_descriptor> edge;
         typedef SecondAlloc<edge> allocator;
         typedef in_vector<edge, allocator> type;
     };
-    */
 };
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -37,18 +37,18 @@
      * Add the edge to list.
      * @complexity O(1)
      */
-    inline in_descriptor add(vertex_descriptor v)
+    insertion_result<in_descriptor> add(vertex_descriptor v, out_descriptor o)
     {
         ++_size;
-        iterator i = _edges.insert(_edges.end(), std::make_pair(v, out_descriptor()));
-        return make_descriptor(_edges, i);
+        iterator i = _edges.insert(_edges.end(), std::make_pair(v, o));
+        return make_result(make_descriptor(_edges, i));
     }
 
     /**
      * Find the edge whose source originates at the given vertex descriptor.
      * @complexity O(d)
      */
-    inline in_descriptor find(vertex_descriptor v) const
+    in_descriptor find(vertex_descriptor v) const
     {
         iterator i = std::find_if(_edges.begin(), _edges.end(), find_first(v));
         return make_descriptor(_edges, i);
@@ -58,7 +58,7 @@
      * Remove the edge referenced by the given iterator.
      * @complexity O(1)
      */
-    inline void remove(in_descriptor d)
+    void remove(in_descriptor d)
     {
         _edges.erase(make_iterator(_edges, d));
         --_size;

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -35,24 +35,24 @@
      * Try to add the given vertex to the result set.
      * @complexity O(lg(d))
      */
-    inline in_descriptor add(vertex_descriptor v)
+    insertion_result<in_descriptor> add(vertex_descriptor v, out_descriptor o)
     {
-        std::pair<iterator, bool> i = _edges.insert(std::make_pair(v, out_descriptor()));
-        return i.second ? make_descriptor(_edges, i.first) : in_descriptor();
+        std::pair<iterator, bool> i = _edges.insert(std::make_pair(v, o));
+        return make_result(_edges, i);
     }
 
     /**
      * Find the edge whose source originates at the given vertex descriptor.
      * @complexity O(lg(d))
      */
-    inline in_descriptor find(vertex_descriptor v) const
+    in_descriptor find(vertex_descriptor v) const
     { return make_descriptor(_edges, _edges.find(v)); }
 
     /**
      * Remove the edge with the given descriptor.
      * @complexity O(lg(d))
      */
-    inline void remove(in_descriptor d)
+    void remove(in_descriptor d)
     { _edges.erase(make_iterator(_edges, d)); }
 
     /** Remove all edges. */

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-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -37,10 +37,10 @@
      * Add the edge to the vector, returning an iterator to the added element.
      * @complexity O(1)
      */
-    inline in_descriptor add(vertex_descriptor e)
+    insertion_result<in_descriptor> add(vertex_descriptor v, out_descriptor o)
     {
-        iterator i = _edges.insert(_edges.end(), std::make_pair(e, out_descriptor()));
-        return make_descriptor(_edges, i);
+        iterator i = _edges.insert(_edges.end(), std::make_pair(v, o));
+        return make_result(make_descriptor(_edges, i));
     }
 
     /**

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -2,102 +2,81 @@
 #ifndef INCIDENCE_ITERATOR_HPP
 #define INCIDENCE_ITERATOR_HPP
 
-#include <boost/type_traits.hpp>
-
-#include "undirected_edge.hpp"
-
 /**
  * The incidence iterator is an abstraction over the incidence iterators of
  * a vertice's incidence store. Specifically when dereferenced, these iterators
  * will result in edge descriptors.
  */
-template <typename Iter>
+template <typename Iter, typename Edge>
 class incidence_iterator
 {
-    typedef Iter base_iterator;
-    typedef typename base_iterator::value_type base_value_type;
 public:
+    typedef Iter iterator;
+    typedef typename iterator::value_type base_value_type;
     typedef typename base_value_type::first_type vertex_descriptor;
     typedef typename base_value_type::second_type property_descriptor;
 
     // This is a little misleading. This iterator can be either bidi or random.
     // Clearly, we're going to be constraining members using some concept stuff
     // when it becomes available.
-    typedef typename base_iterator::iterator_category iterator_category;
+    typedef typename iterator::iterator_category iterator_category;
+    typedef typename iterator::difference_type difference_type;
 
-    // Because incidence sets are built on maps, the key type of an incidence
-    // iterator is given as const key - which causes edges to be instantiated
-    // over constant descriptors (which, perhaps, they should be). For now,
-    // just remove the const and get on with things.
-    typedef undirected_edge<
-            typename boost::remove_const<vertex_descriptor>::type,
-            property_descriptor
-        > value_type;
+    typedef Edge value_type;
     typedef value_type reference;
     typedef value_type pointer;
 
     inline incidence_iterator()
-        : _base(), _iter()
+        : base(), iter()
     { }
 
-    inline incidence_iterator(incidence_iterator const& x)
-        : _base(x._base), _iter(x._iter)
+    inline incidence_iterator(vertex_descriptor v, iterator const& x)
+        : base(v), iter(x)
     { }
 
-    inline incidence_iterator(vertex_descriptor v, base_iterator const& x)
-        : _base(v), _iter(x)
-    { }
 
-    /**
+      /**
      * Extended iterator functionality. Return the source vertex of the
      * iterator. This is the vertex for which the iterator was originally
      * created.
      */
     inline vertex_descriptor source() const
-    { return _base; }
+    { return base; }
 
     /**
-     * Extended iterator functionality. Return the opposite vertex of the
-     * edge indicated by the iterator. This is mostly provided for use by
-     * the adjacency iterator.
+     * Extended iterator functionality. Return the opposite vertex of the edge
+     * indicated by the iterator. This is mostly provided for use by the
+     * adjacency iterator.
      */
     inline vertex_descriptor opposite() const
-    { return _iter->first; }
-
-    /**
-     * Return true if the iterator is "valid" (not default constructed). The
-     * shortcut is to simply test the vertex descriptor.
-     */
-    inline bool valid() const
-    { return _base != vertex_descriptor(); }
+    { return iter->first; }
 
     inline incidence_iterator& operator++()
-    { ++_iter; return *this; }
+    { ++iter; return *this; }
 
     inline incidence_iterator operator++(int)
-    { incidence_iterator tmp(*this); ++_iter; return tmp; }
+    { incidence_iterator tmp(*this); ++iter; return tmp; }
 
     inline incidence_iterator& operator--()
-    { --_iter; return *this; }
+    { --iter; return *this; }
 
     inline incidence_iterator operator--(int)
-    { incidence_iterator tmp(*this); --_iter; return tmp; }
+    { incidence_iterator tmp(*this); --iter; return tmp; }
 
     // Incidence iterators are equivalent if they have the same source and are
     // reference the same incident edge.
     inline bool operator==(incidence_iterator const& x) const
-    { return (_base == x._base) && (_iter == x._iter); }
+    { return (base == x.base) && (iter == x.iter); }
 
     inline bool operator!=(incidence_iterator const& x) const
     { return !this->operator==(x); }
 
     // This can access invalid memory if the iterator is at the end.
     inline reference operator*() const
-    { return reference(_base, _iter->first, _iter->second); }
+    { return Edge(base, iter->first, iter->second); }
 
-private:
-    vertex_descriptor   _base;
-    base_iterator       _iter;
+    vertex_descriptor   base;
+    iterator            iter;
 };
 
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -33,22 +33,28 @@
         : _edges(), _size(0)
     { }
 
-    /**
-     * Add a vertex to the list.
+    /** @name Add Vertex
+     * Add a vertex to the list. The first version adds a stub that must be
+     * bound to a property descriptor in the second phase.
      * @complexity O(1)
      */
-    inline incidence_descriptor add(vertex_descriptor v, property_descriptor p)
+    //@{
+    inline insertion_result<incidence_descriptor> add(vertex_descriptor v)
+    { return add(v, property_descriptor()); }
+
+    insertion_result<incidence_descriptor> add(vertex_descriptor v, property_descriptor p)
     {
         ++_size;
         iterator i = _edges.insert(_edges.end(), make_pair(v, p));
-        return make_descriptor(_edges, i);
+        return make_result(make_descriptor(_edges, i));
     }
+    //@}
 
     /**
      * Find the given incidence pair in the vertex.
      * @complexity O(1)
      */
-    inline incidence_descriptor find(vertex_descriptor v) const
+    incidence_descriptor find(vertex_descriptor v) const
     {
         iterator i = std::find_if(_edges.begin(), _edges.end(), find_first(v));
         return make_descriptor(_edges, i);
@@ -58,14 +64,14 @@
      * Remove the given incidence pair in this vertex.
      * @complexity O(deg(v))
      */
-    inline void remove(incidence_descriptor d)
+    void remove(incidence_descriptor d)
     {
         _edges.erase(make_iterator(_edges, d));
         --_size;
     }
 
     /** Remove all edges from the vertex. */
-    inline void clear()
+    void clear()
     {
         _size = 0;
         _edges.clear();
@@ -88,6 +94,20 @@
     { return _edges.end(); }
     //@}
 
+    /** @name Property Access
+     * These functions provide a descriptor-based interface to the property
+     * descriptors contained within the edge record. Binding binds the property
+     * to an edge stub, and the properties function returns the bound property
+     * descriptor.
+     */
+    //@{
+    inline void bind(incidence_descriptor d, property_descriptor p)
+    { make_iterator(_edges, d)->second = p; }
+
+    inline property_descriptor properties(incidence_descriptor d) const
+    { return make_iterator(_edges, d)->second; }
+    //@}
+
 private:
     mutable store_type  _edges;
     size_type           _size;

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -47,39 +47,32 @@
      * @complexity O(lg(d))
      */
     //@{
-    inline incidence_descriptor add(vertex_descriptor v)
+    inline insertion_result<incidence_descriptor> add(vertex_descriptor v)
     { return add(v, property_descriptor()); }
 
-    inline incidence_descriptor add(vertex_descriptor v, property_descriptor p)
+    insertion_result<incidence_descriptor> add(vertex_descriptor v, property_descriptor p)
     {
         std::pair<iterator, bool> i = _edges.insert(make_pair(v, p));
-        return i.second ? make_descriptor(_edges, i.first) : incidence_descriptor();
+        return make_result(_edges, i);
     }
     //@}
 
     /**
-     * Bind the given property descriptor to this vertex. This is useful when
-     * the incidence pair is added before property is allocated.
-     */
-    inline void bind(incidence_descriptor d, property_descriptor p)
-    { make_iterator(_edges, d)->second = p; }
-
-    /**
      * Find the incident edge whose opposite end is v.
      * @complexity O(lg(d))
      */
-    inline incidence_descriptor find(vertex_descriptor v) const
+    incidence_descriptor find(vertex_descriptor v) const
     { return make_descriptor(_edges, _edges.find(v)); }
 
     /**
      * Remove the edge whose opposite end is v.
      * @complexity O(lg(d))
      */
-    inline void remove(incidence_descriptor d)
+    void remove(incidence_descriptor d)
     { _edges.erase(make_iterator(_edges, d)); }
 
     /** Remove all edges incident to this vertex. */
-    inline void clear()
+    void clear()
     { _edges.clear(); }
 
     /** Return the number of edges incident to this vertex. */
@@ -102,6 +95,21 @@
     { return _edges.end(); }
     //@}
 
+    /** @name Property Access
+     * These functions provide a descriptor-based interface to the property
+     * descriptors contained within the edge record. Binding binds the property
+     * to an edge stub, and the properties function returns the bound property
+     * descriptor.
+     */
+    //@{
+    inline void bind(incidence_descriptor d, property_descriptor p)
+    { make_iterator(_edges, d)->second = p; }
+
+    inline property_descriptor properties(incidence_descriptor d) const
+    { return make_iterator(_edges, d)->second; }
+    //@}
+
+
 private:
     mutable store_type _edges;
 };

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -6,6 +6,7 @@
 #include <algorithm>
 
 #include <boost/descriptors.hpp>
+#include <boost/graphs/utility.hpp>
 
 /**
  * The incidence vector stores incident "edges" of a vertex. In actuality,
@@ -34,15 +35,24 @@
         : _edges()
     { }
 
-    /** Add the incidence pair to the vector. */
-    incidence_descriptor add(vertex_descriptor v, property_descriptor p)
+    /** @name Add Edge
+     * Add the incidence pair to the vector. The first version is responsible
+     * for adding a "stub" that is completed later by binding a property
+     * descriptor into the edge.
+     */
+    //@{
+    inline insertion_result<incidence_descriptor> add(vertex_descriptor v)
+    { return add(v, property_descriptor()); }
+
+    insertion_result<incidence_descriptor> add(vertex_descriptor v, property_descriptor p)
     {
         iterator i = _edges.insert(_edges.end(), std::make_pair(v, p));
-        return make_descriptor(_edges, i);
+        return make_result(make_descriptor(_edges, i));
     }
+    //@}
 
     /** Find the edge with the given vertex. */
-    inline incidence_descriptor find(vertex_descriptor v) const
+    incidence_descriptor find(vertex_descriptor v) const
     {
         iterator i = std::find_if(_edges.begin(), _edges.end(), find_first(v));
         return make_descriptor(_edges, i);
@@ -65,6 +75,21 @@
     { return _edges.end(); }
     //@}
 
+    /** @name Property Access
+     * These functions provide a descriptor-based interface to the property
+     * descriptors contained within the edge record. Binding binds the property
+     * to an edge stub, and the properties function returns the bound property
+     * descriptor.
+     */
+    //@{
+    inline void bind(incidence_descriptor d, property_descriptor p)
+    { make_iterator(_edges, d)->second = p; }
+
+    inline property_descriptor properties(incidence_descriptor d) const
+    { return make_iterator(_edges, d)->second; }
+    //@}
+
+
 private:
     mutable store_type _edges;
 };

Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/ordered_pair.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/ordered_pair.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
+++ (empty file)
@@ -1,70 +0,0 @@
-
-#ifndef BOOST_GRAPH_UTILITY_ORDERED_PAIR_HPP
-#define BOOST_GRAPH_UTILITY_ORDERED_PAIR_HPP
-
-namespace boost {
-namespace graphs {
-
-/**
- * The ordered pair template is essentially a homogenous container of two
- * values. This is essentially the same as std::pair<T, T>, although this
- * class provides a slightly different interface.
- */
-template <typename T>
-class ordered_pair
-{
-public:
-    typedef T value_type;
-
-    ordered_pair();
-    ordered_pair(ordered_pair const& x);
-    ordered_pair(T const& f, T const& s);
-
-    T const& first() const;
-    T const& second() const;
-
-private:
-    std::pair<T, T> _pair;
-};
-
-template <typename T>
-ordered_pair<T>::ordered_pair()
-    : _pair()
-{ }
-
-template <typename T>
-ordered_pair<T>::ordered_pair(ordered_pair const& x)
-    : _pair(x._pair)
-{ }
-
-template <typename T>
-ordered_pair<T>::ordered_pair(T const& f, T const& s)
-    : _pair(f, s)
-{ }
-
-template <typename T>
-T const&
-ordered_pair<T>::first() const
-{ return _pair.first; }
-
-
-template <typename T>
-T const&
-ordered_pair<T>::second() const
-{ return _pair.second; }
-
-/**
- * Make an ordered pair over the two values.
- */
-template <typename T>
-ordered_pair<T>
-make_ordered_pair(T const& f, T const& s)
-{
-    ordered_pair<T> x(f, s);
-    return x;
-}
-
-} /* namespace graphs */
-} /* namespace boost */
-
-#endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -41,11 +41,11 @@
      * Add the edge to the list.
      * @complexity O(1)
      */
-    out_descriptor add(vertex_descriptor v, edge_properties const& ep)
+    insertion_result<out_descriptor> add(vertex_descriptor v, edge_properties const& ep)
     {
         ++_size;
         iterator i = _edges.insert(_edges.end(), make_triple(v, ep, in_descriptor()));
-        return make_descriptor(_edges, i);
+        return make_result(make_descriptor(_edges, i));
     }
 
     /**
@@ -94,6 +94,14 @@
     { return _edges.end(); }
     //@}
 
+    /** Bind the edge to the corresponding in edge descriptor. */
+    inline void bind(out_descriptor o, in_descriptor i)
+    { make_iterator(_edges, o)->third = i; }
+
+    /** Return the properties stored with this edge. */
+    inline edge_properties const& properties(out_descriptor o) const
+    { return make_iterator(_edges, o)->second; }
+
 private:
     mutable store_type  _edges;
     size_type           _size;

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -33,7 +33,7 @@
     typedef typename Edge::third_type in_descriptor;
 
     // Reconstruct the edge triple into a key/value type thing for the map.
-    typedef std::map< vertex_descriptor, std::pair<edge_properties, in_descriptor>, Compare, Alloc> store_type;
+    typedef std::map<vertex_descriptor, std::pair<edge_properties, in_descriptor>, Compare, Alloc> store_type;
     typedef typename store_type::iterator iterator;
     typedef typename store_type::size_type size_type;
 
@@ -44,19 +44,14 @@
         : _edges()
     { }
 
-    /** Allow the edge insertion? */
-    std::pair<iterator, bool> allow(vertex_descriptor v) const
-    { return std::make_pair(_edges.find(v), true); }
-
     /**
-     * Try to add the given edge to the set. If the edge already exists, return
-     * a null descriptor.
+     * Try to add the given edge to the set.
      * @complexity O(log(deg(v)))
      */
-    out_descriptor add(vertex_descriptor v, edge_properties const& ep)
+    insertion_result<out_descriptor> add(vertex_descriptor v, edge_properties const& ep)
     {
         std::pair<iterator, bool> i = _edges.insert(std::make_pair(v, std::make_pair(ep, in_descriptor())));
-        return i.second ? make_descriptor(_edges, i.first) : out_descriptor();
+        return make_result(_edges, i);
     }
 
     /**
@@ -94,6 +89,15 @@
     { return iterator(); }
     //@}
 
+    /** Bind the edge to the corresponding in edge descriptor. */
+    inline void bind(out_descriptor o, in_descriptor i)
+    { make_iterator(_edges, o)->second.second = i; }
+
+    /** Return the properties stored with this edge. */
+    inline edge_properties const& properties(out_descriptor o) const
+    { return make_iterator(_edges, o)->second.first; }
+
+
 private:
     mutable store_type _edges;
 };

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-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -7,6 +7,7 @@
 
 #include <boost/triple.hpp>
 #include <boost/descriptors.hpp>
+#include <boost/graphs/utility.hpp>
 
 /**
  * The in/out vector implements vector-based, edge storage for directed graphs.
@@ -36,20 +37,13 @@
     { }
 
     /**
-     * Allow the edge addition? Unless policy dictates otherwise, always allow
-     * the addition of the edge.
-     */
-    std::pair<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(vertex_descriptor v, edge_properties const& ep)
+    insertion_result<out_descriptor> add(vertex_descriptor v, edge_properties const& ep)
     {
         iterator i = _edges.insert(_edges.end(), make_triple(v, ep, in_descriptor()));
-        return make_descriptor(_edges, i);
+        return make_result(make_descriptor(_edges, i));
     }
 
     /** Find the edge with the given vertex. */
@@ -76,6 +70,14 @@
     { return _edges.end(); }
     //@}
 
+    /** Bind the edge to the corresponding in edge descriptor. */
+    inline void bind(out_descriptor o, in_descriptor i)
+    { make_iterator(_edges, o)->third = i; }
+
+    /** Return the properties stored with this edge. */
+    inline edge_properties const& properties(out_descriptor o) const
+    { return make_iterator(_edges, o)->second; }
+
 private:
     mutable store_type _edges;
 };

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -71,7 +71,7 @@
         --_size;
     }
 
-    // Property access.
+    /** Return the properties referenced by the given descriptor. */
     inline edge_properties& properties(property_descriptor d)
     { return make_iterator(_props, d)->first; }
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -67,7 +67,7 @@
 
     /** Return the properties referenced by the given descriptor. */
     inline edge_properties& properties(property_descriptor d)
-    { return d.value().first; }
+    { return make_iterator(_props, d)->first; }
 
     /** Return the number of properties in the store. */
     inline size_type size() const

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -4,7 +4,7 @@
 
 #include <iosfwd>
 
-#include "unordered_pair.hpp"
+#include <boost/unordered_pair.hpp>
 
 /**
  * This structure implements an unordered edge - sort of. Because the undirected
@@ -28,13 +28,13 @@
         : ends(u, v), prop(p)
     { }
 
-    /**
-     * Return the underlying value of the property that uniquely describes the
-     * edge. This is primarily used to support mapping applications for exterior
-     * edge properties.
-     */
-    inline typename property_descriptor::index_type get() const
-    { return prop.get(); }
+    inline undirected_edge(std::pair<vertex_descriptor, vertex_descriptor> const& e, property_descriptor p)
+        : ends(e.first, e.second), prop(p)
+    { }
+
+    inline undirected_edge(unordered_pair<vertex_descriptor, vertex_descriptor> const& e, property_descriptor p)
+        : ends(e), prop(p)
+    { }
 
     inline property_descriptor properties() const
     { return prop; }
@@ -48,34 +48,26 @@
     inline vertex_descriptor second() const
     { return ends.second(); }
 
+    inline vertex_descriptor opposite(vertex_descriptor v)
+    { return v == first() ? second() : first(); }
+
     /** Return true if the edge connects the two vertices. */
     inline bool connects(vertex_descriptor u, vertex_descriptor v) const
-    {
-        reorder(u, v);
-        return first() == u && second() == v;
-    }
+    { return make_unordered_pair(u, v) == ends; }
 
-    inline vertex_descriptor opposite(vertex_descriptor v)
-    { return v == first() ? second() : first(); }
 
-    edge_pair               ends;
-    property_descriptor     prop;
-};
+    inline bool operator==(undirected_edge const& x) const
+    { return (ends == x.ends) && (prop == x.prop); }
 
-template <typename V, typename P>
-inline bool
-operator==(undirected_edge<V,P> const& a, undirected_edge<V,P> const& b)
-{ return a.ends == b.ends && a.prop == b.prop; }
+    inline bool operator!=(undirected_edge const& x) const
+    { return !operator==(x); }
 
-template <typename V, typename P>
-inline bool
-operator!=(undirected_edge<V,P> const& a, undirected_edge<V,P> const& b)
-{ return !(a == b); }
+    inline bool operator<(undirected_edge const& x) const
+    { return std::make_pair(ends, prop) < std::make_pair(x.ends < x.prop); }
 
-template <typename V, typename P>
-inline bool
-operator<(undirected_edge<V,P> const& a, undirected_edge<V,P> const& b)
-{ return std::make_pair(a.ends, a.prop) < std::make_pair(b.ends < b.props); }
+    edge_pair               ends;
+    property_descriptor     prop;
+};
 
 template <typename V, typename P>
 std::ostream& operator<<(std::ostream& os, undirected_edge<V,P> const& e)
@@ -95,51 +87,42 @@
  * The undirected edge iterator simply wraps the iterator over the global edge
  * property store of undirected graphs.
  */
-template <typename Graph>
+template <typename Store, typename Edge>
 struct undirected_edge_iterator
 {
-    typedef typename Graph::property_store store_type;
-    typedef typename Graph::vertex_type vertex_type;
-    typedef typename Graph::property_descriptor property_descriptor;
-    typedef typename Graph::vertex_descriptor vertex_descriptor;
-
-    // This is an iterator directly into the global property store.
-    typedef typename store_type::iterator prop_iterator;
-
-    typedef std::forward_iterator_tag iterator_category;
-    typedef std::size_t size_type;
+    typedef typename Store::iterator iterator;
 
-    typedef typename Graph::edge_descriptor value_type;
+    typedef typename iterator::iterator_category iterator_category;
+    typedef typename iterator::difference_type difference_type;
+    typedef Edge value_type;
     typedef value_type reference;
     typedef value_type pointer;
 
-    undirected_edge_iterator(store_type const& store, prop_iterator i)
+    undirected_edge_iterator()
+        : store(0), iter()
+    { }
+
+    undirected_edge_iterator(Store& store, iterator i)
         : store(&store), iter(i)
     { }
 
     inline undirected_edge_iterator& operator++()
     { ++iter; return *this; }
 
+    inline undirected_edge_iterator& operator--()
+    { --iter; return *this; }
+
     inline reference operator*() const
-    {
-        // Grab the vertex descrip
-        vertex_descriptor u = iter->second.template get<vertex_descriptor>();
-        vertex_descriptor v = iter->third.template get<vertex_descriptor>();
-        return reference(u, v, store->describe(iter));
-    }
+    { return Edge(iter->second, iter->second); }
 
-    store_type const*   store;
-    prop_iterator       iter;
-};
+    inline bool operator==(undirected_edge_iterator const& x) const
+    { return iter == x.iter; }
+
+    inline bool operator!=(undirected_edge_iterator const& x) const
+    { return iter != x.iter; }
 
-template <typename Graph>
-inline bool
-operator==(undirected_edge_iterator<Graph> const& a, undirected_edge_iterator<Graph> const& b)
-{ return a.iter == b.iter; }
-
-template <typename Graph>
-inline bool
-operator!=(undirected_edge_iterator<Graph> const& a, undirected_edge_iterator<Graph> const& b)
-{ return !(a == b); }
+    Store*      store;
+    iterator    iter;
+};
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -2,20 +2,11 @@
 #ifndef UNDIRECTED_GRAPH_HPP
 #define UNDIRECTED_GRAPH_HPP
 
+#include <boost/assert.hpp>
 #include <boost/none.hpp>
 
-#include "undirected_vertex.hpp"
-#include "vertex_vector.hpp"
-#include "vertex_list.hpp"
-#include "vertex_set.hpp"
-#include "vertex_map.hpp"
-
-#include "undirected_edge.hpp"
-#include "edge_vector.hpp"
-#include "edge_list.hpp"
-#include "edge_set.hpp"
-
-#include "adjacency_iterator.hpp"
+#include <boost/graphs/undirected_types.hpp>
+#include <boost/graphs/adjacency_iterator.hpp>
 
 template <
     typename VertexProps,
@@ -24,6 +15,7 @@
     typename EdgeStore>
 class undirected_graph
 {
+    typedef undirected_types<VertexProps, EdgeProps, VertexStore, EdgeStore> types;
     typedef undirected_graph<VertexProps, EdgeProps, VertexStore, EdgeStore> this_type;
 public:
     typedef VertexProps vertex_properties;
@@ -31,53 +23,33 @@
     typedef VertexStore vertex_store_selector;
     typedef EdgeStore edge_store_selector;
 
-    typedef VertexStore::descriptor_type vertex_descriptor;
-
-    typedef typename EdgeStore::EdgeStore::template property_store<edge_properties, vertex_descriptor>::type property_store;
+    // Underlying stores
+    typedef typename types::property_store property_store;
+    typedef typename types::vertex_store vertex_store;
+    typedef typename types::vertex_key vertex_key;
+    typedef typename types::vertex_type vertex_type;
+
+    // Vertex/Property/Edge descriptors
+    typedef typename types::vertex_descriptor vertex_descriptor;
+    typedef typename types::edge_descriptor edge_descriptor;
+    typedef typename types::property_descriptor property_descriptor;
+    typedef typename types::incidence_descriptor incidence_descriptor;
+
+    // Iterators and ranges
+    typedef typename types::vertex_iterator vertex_iterator;
+    typedef typename types::vertex_range vertex_range;
+    typedef typename types::edge_iterator edge_iterator;
+    typedef typename types::edge_range edge_range;
+    typedef typename types::incident_edge_iterator incident_edge_iterator;
+    typedef typename types::incident_edge_range incident_edge_range;
+    typedef typename types::adjacent_vertex_iterator adjacent_vertex_iterator;
+    typedef typename types::adjacent_vertex_range adjacent_vertex_range;
+
+    // Sizes for vertices, edges, and degree.
+    typedef typename types::vertices_size_type vertices_size_type;
+    typedef typename types::edges_size_type edges_size_type;
+    typedef typename types::incident_edges_size_type incident_edges_size_type;
 
-    // Generate the property store type first. We can do this first because
-    // it's basically independant of everything else, but contributes to almost
-    // everything in the class by virtue of the property descriptor. Use this
-    // to generate the property descriptor...
-    typedef typename EdgeStore::template property_store<edge_properties>::type property_store;
-    typedef typename property_store::property_descriptor property_descriptor;
-    typedef typename property_store::size_type edges_size_type;
-
-    // Generate a bunch of descriptors. The vertex descriptor is fairly
-    // straightforward since, like the property store, its independant of almost
-    // everything. The property descriptor depends entirely upon the property
-    // store and the edge descriptor is actually fairly complicated.
-    // typedef typename VertexStore::descriptor_type vertex_descriptor;
-    typedef undirected_edge<vertex_descriptor, property_descriptor> edge_descriptor;
-
-    // Generate the incidence list. The incidence list for a single vertex
-    // contains a pair: the opposite edge and a property descriptor.
-    typedef typename EdgeStore::template incidence_store<vertex_descriptor, property_descriptor>::type incidence_store;
-
-    // Generate the vertex type over the given properties and the incidence
-    // store. Then, turn around and use that to generate the vertex store and its
-    // related types. Incident edge iterators are abstracted over the iterators
-    // of the vertex.
-    typedef undirected_vertex<vertex_properties, incidence_store> vertex_type;
-    typedef typename vertex_type::size_type incident_edges_size_type;
-    typedef undirected_edge_iterator<this_type> edge_iterator;
-    typedef std::pair<edge_iterator, edge_iterator> edge_range;
-    typedef incidence_iterator<typename vertex_type::iterator> incident_edge_iterator;
-    typedef std::pair<incident_edge_iterator, incident_edge_iterator> incident_edge_range;
-
-    typedef adjacency_iterator<incident_edge_iterator> adjacent_vertex_iterator;
-    typedef std::pair<adjacent_vertex_iterator, adjacent_vertex_iterator> adjacent_vertex_range;
-
-    // The vertex store and related properties can also be built on the vertex
-    // type.
-    typedef typename VertexStore::template store<vertex_type>::type vertex_store;
-    typedef typename vertex_store::size_type vertices_size_type;
-    typedef typename vertex_store::vertex_iterator vertex_iterator;
-    typedef typename vertex_store::vertex_range vertex_range;
-
-    // FIXME: This is a bit hacky, but without constrained members, we need a key
-    // type to enable mapped vertices.
-    typedef typename VertexStore::key_type vertex_key;
 
     // Constructors
     undirected_graph();
@@ -251,7 +223,6 @@
 typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
 undirected_graph<VP,EP,VS,ES>::add_vertex()
 {
-    // BOOST_STATIC_ASSERT(!LabeledUniqueVertices<this_type>);
     return _verts.add();
 }
 
@@ -371,39 +342,35 @@
                                         vertex_descriptor v,
                                         edge_properties const& ep)
 {
-    // To add the edge or not... 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.
+    // Get vertices for the descriptors
     reorder(u, v);
     vertex_type& src = _verts.vertex(u);
     vertex_type& tgt = _verts.vertex(v);
 
-    std::pair<typename vertex_type::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(ep);
-            src.connect(v, p);
-            tgt.connect(u, p);
-
-            // Bind the iterators back into the property store and return an
-            // edge descriptor.
-            _props.bind(p, u, v);
-            return edge_descriptor(u, v, p);
-        }
-        else {
-            return edge_descriptor(u, v, ins.first->second);
-        }
+    // Insert algorithm: Try to stub out the edge locally first. If it succeeds,
+    // then add the global property, and finally bind the incidence and property
+    // descitpros into their respective "slots". Note that this is actually
+    // faster than the
+    insertion_result<incidence_descriptor> first = src.connect(v);
+    if(first.succeeded()) {
+        // Stub the incident edge on the other vertex.
+        insertion_result<incidence_descriptor> second = tgt.connect(u);
+        BOOST_ASSERT(second.succeeded());
+
+        // Add the property and bind everything together.
+        property_descriptor p = _props.add(ep);
+        src.bind(first.value, p);
+        tgt.bind(second.value, p);
+        _props.bind(p, make_pair(u, v));
+        return edge_descriptor(u, v, p);
+    }
+    else if(first.retained()) {
+        property_descriptor p = src.edge_properties(first.value);
+        return edge_descriptor(u, v, p);
     }
     else {
-        // Can't add the edge?
+        return edge_descriptor();
     }
-
-    // This is a null iterator
-    return edge_descriptor();
 }
 
 /**
@@ -496,6 +463,7 @@
 void
 undirected_graph<VP,EP,VS,ES>::remove_edge(edge_descriptor e)
 {
+    /*
     // Grab descriptors out of the edge.
     property_descriptor p = e.properties();
     vertex_descriptor u = e.first();
@@ -510,6 +478,7 @@
     tgt.disconnect(u, p);
     src.disconnect(v, p);
     _props.remove(p);
+    */
 }
 
 /**
@@ -573,6 +542,7 @@
 undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor u,
                                             vertex_descriptor v)
 {
+    /*
     // Canonicalize the ordering of vertices first and the get the vertices.
     reorder(u, v);
     vertex_type& src = _verts.vertex(u);
@@ -595,6 +565,7 @@
             ++i;
         }
     }
+    */
 }
 
 /**

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_types.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_types.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -0,0 +1,74 @@
+
+#ifndef UNDIRECTED_TYPES_HPP
+#define UNDIRECTED_TYPES_HPP
+
+// Vertex stores
+#include <boost/graphs/vertex_vector.hpp>
+#include <boost/graphs/vertex_list.hpp>
+#include <boost/graphs/vertex_set.hpp>
+#include <boost/graphs/vertex_map.hpp>
+
+// Edge stores
+#include <boost/graphs/edge_vector.hpp>
+#include <boost/graphs/edge_list.hpp>
+#include <boost/graphs/edge_set.hpp>
+
+// Edges store components
+#include <boost/graphs/property_vector.hpp>
+#include <boost/graphs/property_list.hpp>
+#include <boost/graphs/incidence_vector.hpp>
+#include <boost/graphs/incidence_list.hpp>
+#include <boost/graphs/incidence_set.hpp>
+#include <boost/graphs/incidence_iterator.hpp>
+
+// Vertex and Edge components
+#include <boost/graphs/undirected_vertex.hpp>
+#include <boost/graphs/undirected_edge.hpp>
+
+// Adjacency components
+#include <boost/graphs/adjacency_iterator.hpp>
+
+using namespace std;
+
+/**
+ * This class is a giant metafunction that generates the types required to
+ * implement an undirected gaph.
+ */
+template <typename VertexProps, typename EdgeProps, typename VertexStore, typename EdgeStore>
+struct undirected_types
+{
+    // Generate descriptors.
+    typedef typename VertexStore::vertex_descriptor vertex_descriptor;
+    typedef typename EdgeStore::property_descriptor property_descriptor;
+    typedef typename EdgeStore::incidence_descriptor incidence_descriptor;
+
+    // Generate the property store and related types.
+    typedef typename EdgeStore::template property_store<EdgeProps, vertex_descriptor>::type property_store;
+    typedef typename property_store::size_type edges_size_type;
+
+    // Generate stuff related to edges
+    typedef undirected_edge<vertex_descriptor, property_descriptor> edge_descriptor;
+    typedef undirected_edge_iterator<property_store, edge_descriptor> edge_iterator;
+    typedef std::pair<edge_iterator, edge_iterator> edge_range;
+
+    // Generate the incidence store type.
+    typedef typename EdgeStore::template incidence_store<vertex_descriptor>::type incidence_store;
+    typedef typename incidence_store::size_type incident_edges_size_type;
+    typedef incidence_iterator<typename incidence_store::iterator, edge_descriptor> incident_edge_iterator;
+    typedef std::pair<incident_edge_iterator, incident_edge_iterator> incident_edge_range;
+
+    // Generate the vertex type and its store and key type.
+    typedef undirected_vertex<EdgeProps, incidence_store> vertex_type;
+    typedef typename VertexStore::template store<vertex_type>::type vertex_store;
+    typedef typename vertex_store::size_type vertices_size_type;
+    typedef typename vertex_store::vertex_iterator vertex_iterator;
+    typedef typename vertex_store::vertex_range vertex_range;
+    typedef typename VertexStore::key_type vertex_key;
+
+    // Generate the adjacency iterator
+    typedef adjacency_iterator<incident_edge_iterator> adjacent_vertex_iterator;
+    typedef std::pair<adjacent_vertex_iterator, adjacent_vertex_iterator> adjacent_vertex_range;
+
+};
+
+#endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -22,12 +22,13 @@
 template <typename VertexProps, typename IncStore>
 class undirected_vertex
 {
-    typedef IncStore incidence_store;
 public:
     typedef VertexProps vertex_properties;
+
+    typedef IncStore incidence_store;
+    typedef typename incidence_store::incidence_descriptor incidence_descriptor;
     typedef typename incidence_store::vertex_descriptor vertex_descriptor;
     typedef typename incidence_store::property_descriptor property_descriptor;
-
     typedef typename incidence_store::iterator iterator;
     typedef typename incidence_store::size_type size_type;
 
@@ -39,15 +40,28 @@
      * vertex. The allow() function determines whether or not the edge
      * connection is allowed and/or already existing.
      */
-    inline std::pair<iterator, bool> allow(vertex_descriptor) const;
-    inline iterator connect(vertex_descriptor, property_descriptor);
-    inline void disconnect(vertex_descriptor, property_descriptor);
-    inline iterator disconnect(iterator);
+    //@{
+    inline insertion_result<incidence_descriptor> connect(vertex_descriptor v)
+    { return _edges.add(v); }
+
+    inline void bind(incidence_descriptor i, property_descriptor p)
+    { _edges.bind(i, p); }
+
+    inline void disconnect(vertex_descriptor, property_descriptor)
+    { }
+
+    inline void disconnect(incidence_descriptor)
+    { }
+    //@}
 
     /** Find return an iterator the edge end with the given vertex. */
     inline iterator find(vertex_descriptor v) const
     { return _edges.find(v); }
 
+    /** Return the properties of the given incident edge. */
+    inline property_descriptor edge_properties(incidence_descriptor i) const
+    { return _edges.properties(i); }
+
 
     /** @name Property Accessors */
     //@{
@@ -56,6 +70,7 @@
 
     inline vertex_properties const& properties() const
     { return _props; }
+
     //@}
 
     /** @name Iterators */
@@ -99,46 +114,5 @@
     , _edges()
 { }
 
-/**
- * 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 undirected_vertex<VP,IS>::iterator, bool>
-undirected_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>
-typename undirected_vertex<VP,IS>::iterator
-undirected_vertex<VP,IS>::connect(vertex_descriptor v, property_descriptor p)
-{
-    return _edges.add(make_pair(v, p));
-}
-
-/**
- * Disconnect the incidedent edge given by the vertex v with edge properties p.
- */
-template <typename VP, typename IS>
-void
-undirected_vertex<VP,IS>::disconnect(vertex_descriptor v, property_descriptor p)
-{
-    _edges.remove(make_pair(v, p));
-}
-
-template <typename VP, typename IS>
-typename undirected_vertex<VP,IS>::iterator
-undirected_vertex<VP,IS>::disconnect(iterator i)
-{
-    return _edges.remove(i);
-}
 
 #endif

Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/unordered_pair.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/unordered_pair.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
+++ (empty file)
@@ -1,168 +0,0 @@
-
-#ifndef UNORDERED_PAIR_HPP
-#define UNORDERED_PAIR_HPP
-
-#include <functional>
-
-#include <boost/functional/hash.hpp>
-
-/**
- * The unordered pair template provides a homogenously typed 2-element
- * whose values are unordered. By unordered, we simply mean that two pairs
- * {x, y} and {y, x} are actually the same pair. The order of the objects
- * within the pair does not matter.
- *
- * Note that unordered pairs do not have mutators for the first and second
- * members. hese are not exposed since modifying only one key at a time can
- * cause problems. The better solution is to construct pairs on the fly and
- * copy them in their entirety.
- */
-template <typename T, typename Compare = std::less<T> >
-class unordered_pair
-{
-public:
-    typedef T value_type;
-    typedef Compare compare;
-
-    unordered_pair();
-    unordered_pair(unordered_pair const& x);
-    unordered_pair(Compare const& comp);
-    unordered_pair(T const& f, T const& s);
-    unordered_pair(T const& f, T const& s, Compare const& comp);
-
-    T const& first() const;
-    T const& second() const;
-    Compare comp() const;
-
-private:
-    void order();
-
-private:
-    std::pair<T, T> _pair;
-    Compare _comp;
-};
-
-template <typename T, typename C>
-unordered_pair<T,C>::unordered_pair()
-    : _pair()
-    , _comp()
-{ }
-
-template <typename T, typename C>
-unordered_pair<T,C>::unordered_pair(unordered_pair const& x)
-    : _pair(x._pair)
-    , _comp(x._comp)
-{ }
-
-template <typename T, typename C>
-unordered_pair<T,C>::unordered_pair(C const& comp)
-    : _pair()
-    , _comp(comp)
-{ }
-
-template <typename T, typename C>
-unordered_pair<T,C>::unordered_pair(T const& f, T const& s)
-    : _pair(f, s)
-    , _comp()
-{ order(); }
-
-
-template <typename T, typename C>
-unordered_pair<T,C>::unordered_pair(T const& f, T const& s, C const& comp)
-    : _pair(f, s)
-    , _comp(comp)
-{ order(); }
-
-template <typename T, typename C>
-T const&
-unordered_pair<T,C>::first() const
-{ return _pair.first; }
-
-template <typename T, typename C>
-T const&
-unordered_pair<T,C>::second() const
-{ return _pair.second; }
-
-/**
- * Return a copy of the comparator used by the unordered pair.
- */
-template <typename T, typename C>
-C
-unordered_pair<T,C>::comp() const
-{ return _comp; }
-
-template <typename T, typename C>
-void
-unordered_pair<T,C>::order()
-{
-    // If the elements are out of order, reorder them.
-    using std::swap;
-    if(_comp(_pair.second, _pair.first)) {
-        swap(_pair.first, _pair.second);
-    }
-}
-
-// Convenience functions and Operators
-
-template <typename T, typename C>
-inline bool
-operator==(unordered_pair<T,C> const& a, unordered_pair<T,C> const& b)
-{ return a.first() == b.first() && a.second() == b.second(); }
-
-template <typename T, typename C>
-inline bool
-operator!=(unordered_pair<T,C> const& a, unordered_pair<T,C> const& b)
-{ return !(a == b); }
-
-template <typename T, typename C>
-inline bool
-operator<(unordered_pair<T,C> const& a, unordered_pair<T,C> const& b)
-{ return std::make_pair(a.first(), a.second()) < std::make_pair(b.first(), b.second()); }
-
-template <typename T, typename C>
-inline bool
-operator>(unordered_pair<T,C> const& a, unordered_pair<T,C> const& b)
-{ return b < a; }
-
-template <typename T, typename C>
-inline bool
-operator<=(unordered_pair<T,C> const& a, unordered_pair<T,C> const& b)
-{ return !(b < a); }
-
-template <typename T, typename C>
-inline bool
-operator>=(unordered_pair<T,C> const& a, unordered_pair<T,C> const& b)
-{ return !(a < b); }
-
-/** Compute the hash value of the unordered pair. */
-template <typename T, typename C>
-inline std::size_t
-hash_value(unordered_pair<T,C> const& x)
-{
-    std::size_t seed = 0;
-    boost::hash_combine(seed, x.first());
-    boost::hash_combine(seed, x.second());
-    return seed;
-}
-
-/**
- * Make an ordered pair over the two values.
- */
-template <typename T>
-unordered_pair<T>
-make_unordered_pair(T const& f, T const& s)
-{ return unordered_pair<T>(f, s); }
-
-/**
- * A swap-like sort function that will "unorder" two objects.
- */
-template <typename T>
-void
-reorder(T& a, T& b)
-{
-    unordered_pair<T> p(a, b);
-    a = p.first();
-    b = p.second();
-}
-
-#endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/utility.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/utility.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/utility.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -4,12 +4,93 @@
 
 #include <boost/descriptors.hpp>
 
+/**
+ * @internal
+ * The insertion result structure encapsulates information about the results
+ * of an insertion. There are a number of possible results from insertsions.
+ * First, the result could succeed, returning a descriptor to the newly inserted
+ * element. The insertion could also fail because the element is already in the
+ * target container (e.g., sets and maps). Third, the insertion could fail
+ * because of some policy (e.g., no self loops or loose edges).
+ *
+ * The result type describes the result of the insertion operation. The
+ * insertion can a) insert a new object, b) retain a previous object, or c)
+ * do nothing becaue of a failure (mentioned above).
+ * 
+ * @param Desc The type of descriptor being returned.
+ * @todo Should the results be more specific?
+ */
+template <typename Desc>
+struct insertion_result
+{
+    typedef Desc descriptor_type;
+    enum result_type { insert, retain, none };
+
+    inline insertion_result()
+        : value(), type(none)
+    { }
+
+    inline insertion_result(descriptor_type d)
+        : value(d), type(insert)
+    { }
+
+    inline insertion_result(descriptor_type d, result_type t)
+        : value(d), type(t)
+    { }
+
+    // A little help for unique associative containers.
+    template <typename Container>
+    inline insertion_result(Container& c, std::pair<typename Container::iterator, bool> i)
+        : value(make_descriptor(c, i.first))
+        , type(i.second ? insert : (i.first  != c.end() ? retain : none))
+    { }
+
+    /** Return true if the insertion succeeded, inserting a new element. */
+    inline bool succeeded() const
+    { return type == insert; }
+
+    /**
+     * Returns true if the insertion retains a previous value, returning a
+     * descriptor to the existing object.
+     */
+    inline bool retained() const
+    { return type == retain; }
+
+    /**
+     * Returns true if the insertion failed due to an assertion or policy.
+     */
+    inline bool failed() const
+    { return type == none; }
+
+    descriptor_type value;
+    result_type     type;
+};
+
+// Helper functions for insertion results
+template <typename Desc>
+inline insertion_result<Desc> make_result()
+{ return insertion_result<Desc>(); }
+
+template <typename Desc>
+inline insertion_result<Desc> make_result(Desc d)
+{ return insertion_result<Desc>(d); }
+
+template <typename Desc>
+inline insertion_result<Desc>
+make_result(Desc d, typename insertion_result<Desc>::result_type t)
+{ return insertion_result<Desc>(d, t); }
+
+template <typename Cont>
+inline insertion_result<typename descriptor_traits<Cont>::descriptor_type>
+make_result(Cont& c, std::pair<typename Cont::iterator, bool> i)
+{ return insertion_result<typename descriptor_traits<Cont>::descriptor_type>(c, i); }
 
 /**
  * @internal
  * A forwarding comparator for proeprties objects that forwards the comparison
- * to the configured comparator. This type is used internally to forward comparisons of vertices
- * to the property comparison provided by the edge set parameter.
+ * to the configured comparator. This type is used internally to forward
+ * comparisons of vertices to the property comparison provided by the edge set
+ * parameter.
  * @param Vertex The type of vertex being compared
  * @param Compare An ordering over vertex properties.
  */

Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
+++ (empty file)
@@ -1,91 +0,0 @@
-
-#ifndef VERTEX_DESCRIPTOR_HPP
-#define VERTEX_DESCRIPTOR_HPP
-
-#include <iosfwd>
-
-#include <boost/functional/hash.hpp>
-
-namespace detail
-{
-    inline std::size_t invalid_value(std::size_t)
-    { return std::size_t(-1); }
-
-    void* invalid_value(void*)
-    { return 0; }
-}
-
-/**
- * The basic vertex descriptor is a wrapper around an opaque reference to a
- * vertex. This class is provided to get around overload problems for functions
- * taking properties or keys when the types of those objects are the same as
- * the underlying descriptor.
- */
-template <typename D>
-class basic_vertex_descriptor
-{
-public:
-    inline basic_vertex_descriptor()
-        : _d(detail::invalid_value(D()))
-    { }
-
-    inline basic_vertex_descriptor(basic_vertex_descriptor const& x)
-        : _d(x._d)
-    { }
-
-    inline basic_vertex_descriptor(D const& d)
-        : _d(d)
-    { }
-
-    // Assignment copy.
-    inline basic_vertex_descriptor& operator=(basic_vertex_descriptor const& d)
-    {
-        _d = d._d;
-        return *this;
-    }
-
-    // value-type assignment.
-    inline basic_vertex_descriptor& operator=(D d)
-    {
-        _d = d;
-        return *this;
-    }
-
-    /** Get the underlying descriptor value. */
-    inline D get() const
-    { return _d; }
-
-    /** Returns true if the descriptor is valid. */
-    inline bool valid() const
-    { return _d != detail::invalid_value(D()); }
-
-private:
-    D _d;
-};
-
-template <typename D>
-bool
-operator<(basic_vertex_descriptor<D> const& a, basic_vertex_descriptor<D> const& b)
-{ return a.get() < b.get(); }
-
-template <typename D>
-inline bool
-operator==(basic_vertex_descriptor<D> const& a, basic_vertex_descriptor<D> const& b)
-{ return a.get() == b.get(); }
-
-template <typename D>
-inline bool
-operator!=(basic_vertex_descriptor<D> const& a, basic_vertex_descriptor<D> const& b)
-{ return a.get() != b.get(); }
-
-template <typename D>
-std::ostream& operator<<(std::ostream& os, const basic_vertex_descriptor<D>& v)
-{ return os << v.get(); }
-
-/** Compute the hash value of the descriptor. */
-template <typename D>
-std::size_t hash_value(basic_vertex_descriptor<D> const& x)
-{ return boost::hash_value(x.get()); }
-
-#endif
-

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -2,27 +2,18 @@
 #ifndef VERTEX_ITERATOR_HPP
 #define VERTEX_ITERATOR_HPP
 
-// This file is a little gross. Basically, I'm cramming three different classes
-// and their implementations into it. This file contains:
-// 1. indexed_vertex_iterator
-// 2. simple_vertex_iterator
-// 3. mapped_vertex_iterator
-// Functions for these follow all the class definitions.
-// TODO Consider inlining all the functions for some degree of brevity.
+#include <boost/descriptors.hpp>
 
 /**
- * The indexed vertex iterator provides a vertex iterator for stores whose
- * descriptors cannot be pointers (i.e., vectors). By virtue of the fact that
- * Store is required to be a vector of something, this is a random access
- * iterator.
+ * A simple vertex iterator for any underlying store.
  */
-template <typename Store>
-class indexed_vertex_iterator
+template <typename Container>
+class basic_vertex_iterator
 {
-    typedef typename Store::const_iterator iterator;
 public:
-    typedef typename Store::value_type vertex_type;
-    typedef typename vertex_type::vertex_descriptor vertex_descriptor;
+    typedef typename Container::iterator iterator;
+    typedef typename Container::value_type vertex_type;
+    typedef typename descriptor_traits<Container>::descriptor_type vertex_descriptor;
 
     typedef typename iterator::iterator_category iterator_category;
     typedef typename iterator::difference_type difference_type;
@@ -30,339 +21,48 @@
     typedef vertex_descriptor reference;
     typedef vertex_descriptor pointer;
 
-    // Constructors
-    inline indexed_vertex_iterator();
-    inline indexed_vertex_iterator(indexed_vertex_iterator const& x);
-    inline indexed_vertex_iterator(Store const& s, iterator const& x);
+    inline basic_vertex_iterator()
+        : cont(0), iter()
+    { }
+
+    inline basic_vertex_iterator(Container& c, iterator x)
+        : cont(c), iter(x)
+    { }
 
     // Assignment and increment
-    inline indexed_vertex_iterator& operator=(indexed_vertex_iterator const& x);
-    inline indexed_vertex_iterator& operator+=(difference_type n);
-    inline indexed_vertex_iterator& operator-=(difference_type n);
-    inline indexed_vertex_iterator& operator++();
-    inline indexed_vertex_iterator& operator--();
-
-    inline indexed_vertex_iterator operator+(difference_type n) const;
-    inline indexed_vertex_iterator operator-(difference_type n) const;
-    inline difference_type operator-(indexed_vertex_iterator const& x) const;
+    inline basic_vertex_iterator& operator+=(difference_type n)
+    { iter += n; return *this; }
 
-    inline reference operator*();
+    inline basic_vertex_iterator& operator-=(difference_type n)
+    { iter -= n; return *this; }
 
-    inline bool operator==(indexed_vertex_iterator const& x) const;
-    inline bool operator!=(indexed_vertex_iterator const& x) const;
+    inline basic_vertex_iterator& operator++()
+    { ++iter; return *this; }
 
-private:
-    Store const* store;
-    iterator iter;
-};
-
-/**
- * The value vertex iterator provides a vertex iterator unique associative
- * containers and sequences that don't invalidate memory on insertions
- * (lists).
- */
-template <typename Store>
-class simple_vertex_iterator
-{
-    typedef typename Store::const_iterator iterator;
-public:
-    typedef typename Store::value_type vertex_type;
-    typedef typename vertex_type::vertex_descriptor vertex_descriptor;
-
-    typedef typename iterator::iterator_category iterator_category;
-    typedef typename iterator::difference_type difference_type;
-    typedef vertex_descriptor value_type;
-    typedef vertex_descriptor reference;
-    typedef vertex_descriptor pointer;
-
-    inline simple_vertex_iterator();
-    inline simple_vertex_iterator(simple_vertex_iterator const& x);
-    inline simple_vertex_iterator(iterator const& x);
-
-    inline simple_vertex_iterator& operator=(simple_vertex_iterator const& x);
-    inline simple_vertex_iterator& operator++();
-    inline simple_vertex_iterator& operator--();
-
-    inline reference operator*();
-
-    inline bool operator==(simple_vertex_iterator const& x) const;
-    inline bool operator!=(simple_vertex_iterator const& x) const;
+    inline basic_vertex_iterator& operator--()
+    { --iter; return *this; }
 
-private:
-    iterator iter;
-};
+    inline basic_vertex_iterator operator+(difference_type n) const
+    { return indexed_basic_vertex_iterator(cont, iter + n); }
 
+    inline basic_vertex_iterator operator-(difference_type n) const
+    { return indexed_basic_vertex_iterator(cont, iter -n); }
 
-/**
- * The mapped vertex iterator provides a vertex iterator pair associative
- * storage containers. This essintially wraps a store iterator, providing
- * the ability to dererence to descriptors. Because this iterator is taken
- * from pair associative structures, it is bidirectional but not random access.
- */
-template <typename Store>
-class mapped_vertex_iterator
-{
-    typedef typename Store::const_iterator iterator;
-public:
-    typedef typename Store::mapped_type vertex_type;
-    typedef typename vertex_type::vertex_descriptor vertex_descriptor;
-
-    typedef typename iterator::iterator_category iterator_category;
-    typedef typename iterator::difference_type difference_type;
-    typedef vertex_descriptor value_type;
-    typedef vertex_descriptor reference;
-    typedef vertex_descriptor pointer;
+    inline difference_type operator-(basic_vertex_iterator const& x) const
+    { return iter - x.iter; }
 
-    inline mapped_vertex_iterator();
-    inline mapped_vertex_iterator(mapped_vertex_iterator const& x);
-    inline mapped_vertex_iterator(iterator const& x);
-
-    inline mapped_vertex_iterator& operator=(mapped_vertex_iterator const& x);
-    inline mapped_vertex_iterator& operator++();
-    inline mapped_vertex_iterator& operator--();
+    inline reference operator*()
+    { return make_descriptor(*cont, iter); }
 
-    inline reference operator*();
+    inline bool operator==(basic_vertex_iterator const& x) const
+    { return iter == x.iter; }
 
-    inline bool operator==(mapped_vertex_iterator const& x) const;
-    inline bool operator!=(mapped_vertex_iterator const& x) const;
+    inline bool operator!=(basic_vertex_iterator const& x) const
+    { return iter != x.iter; }
 
 private:
-    iterator iter;
+    Container*  cont;
+    iterator    iter;
 };
 
-//
-// Indexed Vertex Iterator Functions
-//
-
-template <typename S>
-indexed_vertex_iterator<S>::indexed_vertex_iterator()
-    : store(0)
-    , iter()
-{ }
-
-template <typename S>
-indexed_vertex_iterator<S>::indexed_vertex_iterator(indexed_vertex_iterator const& x)
-    : store(x.store)
-    , iter(x.iter)
-{ }
-
-template <typename S>
-indexed_vertex_iterator<S>::indexed_vertex_iterator(S const& s, iterator const& x)
-    : store(&s)
-    , iter(x)
-{ }
-
-template <typename S>
-indexed_vertex_iterator<S>&
-indexed_vertex_iterator<S>::operator=(indexed_vertex_iterator const& x)
-{
-    iter = x.iter;
-    store = x.store;
-    return *this;
-}
-
-template <typename S>
-indexed_vertex_iterator<S>&
-indexed_vertex_iterator<S>::operator+=(difference_type n)
-{
-    iter += n;
-    return *this;
-}
-
-template <typename S>
-indexed_vertex_iterator<S>&
-indexed_vertex_iterator<S>::operator-=(difference_type n)
-{
-    iter -= n;
-    return *this;
-}
-
-template <typename S>
-indexed_vertex_iterator<S>&
-indexed_vertex_iterator<S>::operator++()
-{
-    ++iter;
-    return *this;
-}
-
-template <typename S>
-indexed_vertex_iterator<S>&
-indexed_vertex_iterator<S>::operator--()
-{
-    --iter;
-    return *this;
-}
-
-template <typename S>
-indexed_vertex_iterator<S>
-indexed_vertex_iterator<S>::operator+(difference_type n) const
-{
-    return iter + n;
-}
-
-template <typename S>
-indexed_vertex_iterator<S>
-indexed_vertex_iterator<S>::operator-(difference_type n) const
-{
-    return iter - n;
-}
-
-template <typename S>
-typename indexed_vertex_iterator<S>::difference_type
-indexed_vertex_iterator<S>::operator-(indexed_vertex_iterator const& x) const
-{
-    return iter - x.iter;
-}
-
-template <typename S>
-typename indexed_vertex_iterator<S>::reference
-indexed_vertex_iterator<S>::operator*()
-{
-    // The returned descriptor is simply the distance from the beginning of
-    // the underlying store to the end.
-    return std::distance(store->begin(), iter);
-}
-
-template <typename S>
-bool
-indexed_vertex_iterator<S>::operator==(indexed_vertex_iterator const& x) const
-{
-     return (store == x.store) && (iter == x.iter);
-}
-
-template <typename S>
-bool
-indexed_vertex_iterator<S>::operator!=(indexed_vertex_iterator const& x) const
-{
-    return (store == x.store) && (iter != x.iter);
-}
-
-
-//
-// Simple Vertex Iterator Functions
-//
-
-template <typename S>
-simple_vertex_iterator<S>::simple_vertex_iterator()
-    : iter()
-{ }
-
-template <typename S>
-simple_vertex_iterator<S>::simple_vertex_iterator(simple_vertex_iterator const& x)
-    : iter(x.iter)
-{ }
-
-template <typename S>
-simple_vertex_iterator<S>::simple_vertex_iterator(iterator const& x)
-    : iter(x)
-{ }
-
-template <typename S>
-simple_vertex_iterator<S>&
-simple_vertex_iterator<S>::operator=(simple_vertex_iterator const& x)
-{
-    iter = x.iter;
-    return *this;
-}
-
-template <typename S>
-simple_vertex_iterator<S>&
-simple_vertex_iterator<S>::operator++()
-{
-    ++iter;
-    return *this;
-}
-
-template <typename S>
-simple_vertex_iterator<S>&
-simple_vertex_iterator<S>::operator--()
-{
-    --iter;
-    return *this;
-}
-
-template <typename S>
-typename simple_vertex_iterator<S>::reference
-simple_vertex_iterator<S>::operator*()
-{
-    return &const_cast<vertex_type&>(*iter);
-}
-
-template <typename S>
-bool
-simple_vertex_iterator<S>::operator==(simple_vertex_iterator const& x) const
-{
-    return iter == x.iter;
-}
-
-template <typename S>
-bool
-simple_vertex_iterator<S>::operator!=(simple_vertex_iterator const& x) const
-{
-    return iter != x.iter;
-}
-
-//
-// Mapped Vertex Iterator Functions
-
-template <typename S>
-mapped_vertex_iterator<S>::mapped_vertex_iterator()
-    : iter()
-{ }
-
-template <typename S>
-mapped_vertex_iterator<S>::mapped_vertex_iterator(mapped_vertex_iterator const& x)
-    : iter(x.iter)
-{ }
-
-template <typename S>
-mapped_vertex_iterator<S>::mapped_vertex_iterator(iterator const& x)
-    : iter(x)
-{ }
-
-template <typename S>
-mapped_vertex_iterator<S>&
-mapped_vertex_iterator<S>::operator=(mapped_vertex_iterator const& x)
-{
-    iter = x.iter;
-    return *this;
-}
-
-template <typename S>
-mapped_vertex_iterator<S>&
-mapped_vertex_iterator<S>::operator++()
-{
-    ++iter;
-    return *this;
-}
-
-template <typename S>
-mapped_vertex_iterator<S>&
-mapped_vertex_iterator<S>::operator--()
-{
-    --iter;
-    return *this;
-}
-
-template <typename S>
-typename mapped_vertex_iterator<S>::reference
-mapped_vertex_iterator<S>::operator*()
-{
-    return &const_cast<vertex_type&>(iter->second);
-}
-
-template <typename S>
-bool
-mapped_vertex_iterator<S>::operator==(mapped_vertex_iterator const& x) const
-{
-    return iter == x.iter;
-}
-
-template <typename S>
-bool
-mapped_vertex_iterator<S>::operator!=(mapped_vertex_iterator const& x) const
-{
-    return iter != x.iter;
-}
-
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -7,7 +7,7 @@
 #include <boost/none.hpp>
 #include <boost/descriptors.hpp>
 
-#include "vertex_iterator.hpp"
+#include <boost/graphs/vertex_iterator.hpp>
 
 // Forward declarations
 template <typename, typename> class vertices_list;
@@ -21,7 +21,7 @@
     typedef unused key_type;
 
     typedef std::list<int, Alloc<int>> dummy;
-    typedef typename descriptor_traits<dummy>::descriptor_type descriptor_type;
+    typedef typename descriptor_traits<dummy>::descriptor_type vertex_descriptor;
 
     template <typename Vertex>
     struct store
@@ -50,7 +50,7 @@
 
     typedef typename descriptor_traits<store_type>::descriptor_type vertex_descriptor;
 
-    typedef simple_vertex_iterator<store_type> vertex_iterator;
+    typedef basic_vertex_iterator<store_type> vertex_iterator;
     typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
 
     // Constructors

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -6,7 +6,7 @@
 
 #include <boost/descriptors.hpp>
 
-#include "vertex_iterator.hpp"
+#include <boost/graphs/vertex_iterator.hpp>
 
 // Forward declarations
 template <typename, typename, typename, typename> class vertices_map;
@@ -37,14 +37,14 @@
     typedef Key key_type;
 
     typedef std::map<Key, int, Compare<Key>, Alloc<std::pair<Key, int>>> dummy;
-    typedef typename descriptor_traits<dummy>::descriptor_type descriptor_type;
+    typedef typename descriptor_traits<dummy>::descriptor_type vertex_descriptor;
 
     template <typename Vertex>
     struct store
     {
-        typedef vertices_map<
-            Vertex, Key, Compare<Key>, Alloc<std::pair<Key, Vertex>>
-        > type;
+        typedef Alloc<std::pair<Key, Vertex>> allocator;
+        typedef Compare<Key> compare;
+        typedef vertices_map<Vertex, Key, compare, allocator> type;
     };
 };
 
@@ -73,7 +73,7 @@
 
     typedef typename descriptor_traits<store_type>::descriptor_type vertex_descriptor;
 
-    typedef simple_vertex_iterator<store_type> vertex_iterator;
+    typedef basic_vertex_iterator<store_type> vertex_iterator;
     typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
 
     inline vertices_map()

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -6,9 +6,9 @@
 
 #include <boost/none.hpp>
 #include <boost/descriptors.hpp>
-#include <boost/graphs/utility.hpp>
 
-#include "vertex_iterator.hpp"
+#include <boost/graphs/utility.hpp>
+#include <boost/graphs/vertex_iterator.hpp>
 
 // Forward declarations
 template <typename, typename, typename> class vertices_set;
@@ -36,17 +36,15 @@
     typedef unused key_type;
 
     typedef std::set<int, Compare<int>, Alloc<int>> dummy;
-    typedef typename descriptor_traits<dummy>::descriptor_type descriptor_type;
+    typedef typename descriptor_traits<dummy>::descriptor_type vertex_descriptor;
 
     // This metafunction generates the underlying vertex store implementation.
     template <typename Vertex>
     struct store
     {
-        typedef vertices_set<
-                Vertex,
-                property_comparator<Compare<typename Vertex::vertex_properties>>,
-                Alloc<Vertex>
-            > type;
+        typedef Alloc<Vertex> allocator;
+        typedef property_comparator<Compare<typename Vertex::vertex_properties>> compare;
+        typedef vertices_set<Vertex, compare, allocator> type;
     };
 };
 
@@ -73,7 +71,7 @@
 
     typedef typename descriptor_traits<store_type>::descriptor_type vertex_descriptor;
 
-    typedef simple_vertex_iterator<store_type> vertex_iterator;
+    typedef basic_vertex_iterator<store_type> vertex_iterator;
     typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
 
     inline vertices_set()

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -7,9 +7,9 @@
 
 #include <boost/none.hpp>
 #include <boost/descriptors.hpp>
-#include <boost/graphs/utility.hpp>
 
-#include "vertex_iterator.hpp"
+#include <boost/graphs/utility.hpp>
+#include <boost/graphs/vertex_iterator.hpp>
 
 // Forward declarations
 template <typename, typename> struct vertices_vector;
@@ -30,7 +30,7 @@
     typedef unused key_type;
 
     typedef std::vector<int, Alloc<int>> dummy;
-    typedef typename descriptor_traits<dummy>::descriptor_type descriptor_type;
+    typedef typename descriptor_traits<dummy>::descriptor_type vertex_descriptor;
 
     // The store metafunction generates the type used to store vertices in
     // either a directed or undirected graph. This metafunction takes the
@@ -38,7 +38,8 @@
     template <typename Vertex>
     struct store
     {
-        typedef vertices_vector<Vertex, Alloc<Vertex>> type;
+        typedef Alloc<Vertex> allocator;
+        typedef vertices_vector<Vertex, allocator> type;
     };
 };
 
@@ -66,7 +67,7 @@
 
     typedef typename descriptor_traits<store_type>::descriptor_type vertex_descriptor;
 
-    typedef indexed_vertex_iterator<store_type> vertex_iterator;
+    typedef basic_vertex_iterator<store_type> vertex_iterator;
     typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
 
     // Constructors

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-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -8,7 +8,7 @@
     : requirements <toolset>gcc-4.4
     ;
 
-# exe un : un.cpp : <include>../../ <include>/usr/local/include ;
+
 # 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 ;
@@ -22,3 +22,5 @@
 exe test_outs : test_outs.cpp : <include>../../ ;
 exe test_ins : test_ins.cpp : <include>../../ ;
 exe test_es : test_es.cpp : <include>../../ ;
+
+exe un : un.cpp : <include>../../ ;

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/in_edge_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/in_edge_traits.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -0,0 +1,31 @@
+
+#ifndef IN_EDGE_TRAITS_HPP
+#define IN_EDGE_TRAITS_HPP
+
+struct in_vector_tag : sequence_tag, unstable_remove_tag { };
+struct in_list_tag : sequence_tag, stable_mutators_tag { };
+struct in_set_tag : associative_container_tag, stable_mutators_tag { };
+
+template <typename Ins>
+struct in_edge_traits
+{ typedef typename Ins::category cateogry; };
+
+template <typename Ins>
+typename in_edge_traits<Ins>::category
+in_edge_category(Ins const&)
+{ return typename in_edge_traits<Ins>::category(); }
+
+
+template <typename Edge, typename Alloc>
+struct in_edge_traits<in_vector<Edge, Alloc>>
+{ typedef in_vector_tag category; };
+
+template <typename Edge, typename Alloc>
+struct in_edge_traits<in_list<Edge, Alloc>>
+{ typedef in_list_tag category; };
+
+template <typename Edge, typename Comp, typename Alloc>
+struct in_edge_traits<in_set<Edge, Comp, Alloc>>
+{ typedef in_set_tag category; };
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/out_edge_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/out_edge_traits.hpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -0,0 +1,31 @@
+
+#ifndef OUT_EDGE_TRAITS_HPP
+#define OUT_EDGE_TRAITS_HPP
+
+struct out_vector_tag : sequence_tag, unstable_remove_tag { };
+struct out_list_tag : sequence_tag, stable_mutators_tag { };
+struct out_set_tag : associative_container_tag, stable_mutators_tag { };
+
+template <typename Outs>
+struct out_edge_traits
+{ typedef typename Outs::category cateogry; };
+
+template <typename Outs>
+typename out_edge_traits<Outs>::category
+out_edge_category(Outs const&)
+{ return typename out_edge_traits<Outs>::category(); }
+
+
+template <typename Edge, typename Alloc>
+struct out_edge_traits<out_vector<Edge, Alloc>>
+{ typedef out_vector_tag category; };
+
+template <typename Edge, typename Alloc>
+struct out_edge_traits<out_list<Edge, Alloc>>
+{ typedef out_list_tag category; };
+
+template <typename Edge, typename Comp, typename Alloc>
+struct out_edge_traits<out_set<Edge, Comp, Alloc>>
+{ typedef out_set_tag category; };
+
+#endif

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -2,13 +2,28 @@
 #include <iostream>
 
 #include <boost/next_prior.hpp>
+
 #include <boost/graphs/edge_vector.hpp>
 #include <boost/graphs/edge_list.hpp>
 #include <boost/graphs/edge_set.hpp>
 
+#include <boost/graphs/property_vector.hpp>
+#include <boost/graphs/property_list.hpp>
+#include <boost/graphs/incidence_vector.hpp>
+#include <boost/graphs/incidence_list.hpp>
+#include <boost/graphs/incidence_set.hpp>
+#include <boost/graphs/out_vector.hpp>
+#include <boost/graphs/out_list.hpp>
+#include <boost/graphs/out_set.hpp>
+#include <boost/graphs/in_vector.hpp>
+#include <boost/graphs/in_list.hpp>
+#include <boost/graphs/in_set.hpp>
+
 #include "typestr.hpp"
 #include "properties_traits.hpp"
 #include "incidence_traits.hpp"
+#include "out_edge_traits.hpp"
+#include "in_edge_traits.hpp"
 
 using namespace std;
 using namespace boost;
@@ -21,77 +36,115 @@
 typedef int EdgeProps;
 typedef index_descriptor<size_t> VertexDesc;
 
+// Add an edge with the given properties to the implicit vertex.
 template <typename Props, typename Incs, typename Vertex, typename Edge>
-void add_edge(Props& props, Incs& incs, Vertex v, Edge const& ep, associative_container_tag)
+void undirected_add_edge(Props& props, Incs& incs, Vertex v, Edge const& ep)
 {
     typedef typename Props::property_descriptor PropDesc;
     typedef typename Incs::incidence_descriptor IncDesc;
+    typedef insertion_result<IncDesc> Result;
 
+    size_t m = props.size();
+    size_t n = incs.size();
+
+    // Our global vertex.
     Vertex u = VertexDesc(0);
 
-    // This is a little different protocol. First, try to insert the edge into
-    // the incidence list, but lave the property slot "empty".
-    IncDesc i = incs.add(v);
-    if(incs.valid(i)) {
+    // Insert algorithm: Try to stub out the edge locally first. If it succeeds,
+    // then add the global property, and finally bind the incidence and property
+    // descitpros into their respective "slots". Note that this is actually
+    // faster than the 
+    Result r = incs.add(v);
+    if(r.succeeded()) {
         PropDesc p = props.add(ep);
-        incs.bind(i, p);
+        incs.bind(r.value, p);
         props.bind(p, make_pair(u, v));
-        cout << "  * added: " << u << ", " << v << endl;
+
+        BOOST_ASSERT(props.size() == m + 1);
+        BOOST_ASSERT(incs.size() == n + 1);
+        cout << "  * added " << u << "," << v << " -> " << props.properties(p) << endl;
+    }
+    else if(r.retained()) {
+        PropDesc p = incs.properties(r.value);
+        cout << "  * exists " << u << "," << v << " -> " << props.properties(p) << endl;
     }
     else {
-        cout << "  * did not add: " << u << ", " << v << endl;
+        cout << "  * failed " << u << "," << v << endl;
     }
 }
 
-// These are basically multigraphs (i.e., multiple edges allowed).
-template <typename Props, typename Incs, typename Vertex, typename Edge>
-void add_edge(Props& props, Incs& incs, Vertex v, Edge const& ep, sequence_tag)
+template <typename Outs, typename Ins>
+void directed_add_edge(Outs& outs, Ins& ins, VertexDesc v, EdgeProps const& ep)
 {
-    typedef typename Props::property_descriptor PropDesc;
-    typedef typename Incs::incidence_descriptor IncDesc;
-
-    Vertex u = VertexDesc(0);
-
-    // Pretty simple... add the vertex and create the incident pair, and then
-    // bind both the implicit (0) vertex and v to the property.
-    size_t m = props.size(), n = incs.size();
-    PropDesc p = props.add(ep);
-    IncDesc i = incs.add(v, p);
-    props.bind(p, make_pair(u, v));
-
-    cout << "  * added: " << u << ", " << v << endl;
-    BOOST_ASSERT(props.size() == m + 1);
-    BOOST_ASSERT(incs.size() == n + 1);
-}
-
-// Add an edge with the given properties to the implicit vertex.
-template <typename Props, typename Incs, typename Vertex, typename Edge>
-void add_edge(Props& props, Incs& incs, Vertex v, Edge const& ep)
-{
-    add_edge(props, incs, v, ep, incidence_category(incs));
+    typedef typename Outs::out_descriptor OutDesc;
+    typedef typename Ins::in_descriptor InDesc;
+    typedef insertion_result<OutDesc> Result;
+
+    size_t m = outs.size();
+
+    // Here, we're adding edge (u,v). Note that outs is implicitly a member of
+    // u and ins is a member of v.
+    VertexDesc u(0);
+
+    // Try to add the edge to the out list. If it succeeds then reciprocate the
+    // insertion for the in edge set and bind them together.
+    Result o = outs.add(v, ep);
+    if(o.succeeded()) {
+        Result i = ins.add(v, o.value);
+        outs.bind(o.value, i.value);
+
+        BOOST_ASSERT(outs.size() == m + 1);
+        BOOST_ASSERT(ins.size() == 1);
+        cout << "  * added " << u << "," << v << " -> " << outs.properties(o.value) << endl;
+    }
+    else if(o.retained()) {
+        cout << "  * exists " << u << "," << v << " -> " << outs.properties(o.value) << endl;
+    }
 }
 
 // Test the addition of edges as if we were adding them to an implicit vertex 0.
 template <typename Props, typename Incs>
-void add_edges(Props& props, Incs& incs)
+void undirected_add_edges(Props& props, Incs& incs)
 {
     BOOST_ASSERT(props.empty());
     BOOST_ASSERT(incs.empty());
 
+    // Add a bunch of implicit connections.
     size_t const N = 5;
     for(size_t i = 0; i < N; ++i) {
-        add_edge(props, incs, VertexDesc(i + 1), i * i);
+        undirected_add_edge(props, incs, VertexDesc(i + 1), 2 * (i + 1));
     }
+    BOOST_ASSERT(props.size() == N);
+    BOOST_ASSERT(incs.size() == N);
 
     // Just for good measure, add antoher that duplicates the first.
-    add_edge(props, incs, VertexDesc(1), 1);
+    undirected_add_edge(props, incs, VertexDesc(2), 1);
+}
+
+template <typename Outs, typename Ins>
+void directed_add_edges(Outs& outs, Ins&)
+{
+    BOOST_ASSERT(outs.empty());
+
+    // This is a little odd. The in edge set is actually specific to different
+    // vertices, so construct new, empty sets on the fly.
+
+    size_t const N = 5;
+    for(size_t i = 0; i < N; ++i) {
+        Ins ins;
+        directed_add_edge(outs, ins, VertexDesc(i + 1), 2 * (i + 1));
+    }
+
+    // Just for good measure, add antoher that duplicates the first.
+    Ins ins;
+    directed_add_edge(outs, ins, VertexDesc(2), 1);
 }
 
 template <typename EdgeStore>
 void
 undirected()
 {
-    cout << "--- " << typestr<EdgeStore>() << " ---" << endl;
+    cout << "--- undirected " << typestr<EdgeStore>() << " ---" << endl;
 
     // Instantiate data structures related to the storage of edges and their
     // properties.
@@ -104,7 +157,27 @@
     cout << "  * " << typestr(properties_category(props)) << endl;
     cout << "  * " << typestr(incidence_category(incs)) << endl;
 
-    add_edges(props, incs);
+    undirected_add_edges(props, incs);
+}
+
+template <typename EdgeStore>
+void
+directed()
+{
+    cout << "--- directed " << typestr<EdgeStore>() << " ---" << endl;
+
+    // Instantiate data structures related to the storage of edges and their
+    // properties.
+    typedef typename EdgeStore::template out_store<VertexDesc, EdgeProps>::type OutStore;
+    typedef typename EdgeStore::template in_store<VertexDesc>::type InStore;
+
+    OutStore outs;
+    InStore ins;
+
+    cout << "  * " << typestr(out_edge_category(outs)) << endl;
+    cout << "  * " << typestr(in_edge_category(ins)) << endl;
+
+    directed_add_edges(outs, ins);
 }
 
 int main()
@@ -113,5 +186,9 @@
     undirected<edge_list<>>();
     undirected<edge_set<>>();
 
+    directed<edge_vector<>>();
+    directed<edge_list<>>();
+    directed<edge_set<>>();
+
    return 0;
 }
\ No newline at end of file

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp	2008-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -63,7 +63,7 @@
 void test()
 {
     typedef typename Verts::template store<Vertex>::type Store;
-    typedef typename Verts::descriptor_type Descriptor;
+    typedef typename Verts::vertex_descriptor Descriptor;
 
     Store verts;
     cout << "--- " << typestr(verts) << " ---" << endl;

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-07-08 12:50:24 EDT (Tue, 08 Jul 2008)
@@ -1,13 +1,11 @@
 
 #include <iostream>
-#include <set>
 
 #include <boost/assert.hpp>
 #include <boost/utility.hpp>
 #include <boost/graphs/undirected_graph.hpp>
-#include <boost/graphs/traits.hpp>
 
-#include "demangle.hpp"
+#include "typestr.hpp"
 
 using namespace std;
 using namespace boost;
@@ -22,12 +20,12 @@
 template <typename Graph>
 void print_types(const Graph&)
 {
-    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;
-    cout << demangle(typeid(typename Graph::incidence_store).name()) << endl;
+    // cout << typestr<typename Graph::property_descriptor>() << endl;
+    cout << "  * " << typestr<typename Graph::vertex_descriptor>() << endl;
+    cout << "  * " << typestr<typename Graph::edge_descriptor>() << endl;
+    // cout << typestr<typename Graph::property_store>() << endl;
+    // cout << typestr<typename Graph::vertex_store>() << endl;
+    // cout << typestr<typename Graph::incidence_store>() << endl;
 }
 
 template <typename Graph>
@@ -224,10 +222,10 @@
 {
     cout << "---- vec/vec ----" << endl;
     typedef undirected_graph<City, Road, vertex_vector<>, edge_vector<> > Graph;
-    // test_add_vertices<Graph>();
-    // test_add_edges<Graph>();
+    test_add_vertices<Graph>();
+    test_add_edges<Graph>();
     // test_add_multi_edges<Graph>();
-    test_incidence_iterator<Graph>();
+    // test_incidence_iterator<Graph>();
     // test_adjacency_iterator<Graph>();
 }