[Boost-commit] svn:boost r45901 - in sandbox/SOC/2008/graphs/boost/graphs: . adjacency_list adjacency_list/es adjacency_list/ves adjacency_list/vs adjacency_matrix incidence_list incidence_matrix property_map utility

From: asutton_at_[hidden]
Date: 2008-05-29 08:54:57

Author: asutton
Date: 2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
New Revision: 45901
URL: http://svn.boost.org/trac/boost/changeset/45901

Log:
Initial commit of lots of graph code.

Added:
   sandbox/SOC/2008/graphs/boost/graphs/
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/adjacency_list.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/descriptor.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/edge.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_list.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_multiset.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_set.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_vector.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/indexed_edge_iterator.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/value_edge_iterator.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/graphs.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/policy.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/storage.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/storage_traits.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/types.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/undirected.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vertex.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/ves/
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/ves/vertex_edge_list.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/ves/vertex_edge_set.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/ves/vertex_edge_store.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/ves/vertex_edge_vector.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/indexed_vertex_iterator.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/mapped_vertex_iterator.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/value_vertex_iterator.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_list.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_map.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_multimap.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_multiset.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_set.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_vector.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_matrix/
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_matrix/adjacency_matrix.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/breadth_first_search.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/incidence_list/
   sandbox/SOC/2008/graphs/boost/graphs/incidence_list/incidence_list.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/incidence_matrix/
   sandbox/SOC/2008/graphs/boost/graphs/incidence_matrix/incidence_matrix.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/properties.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/property_map/
   sandbox/SOC/2008/graphs/boost/graphs/property_map/bundled_properties.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/property_map/hashed_properties.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/property_map/indexed_properties.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/property_map/simple_properties.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/utility/
   sandbox/SOC/2008/graphs/boost/graphs/utility.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/utility/ordered_pair.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/boost/graphs/utility/unordered_pair.hpp   (contents, props changed)

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,7 @@
+
+#ifndef BOOST_GRAPH_ADJACENCY_LIST_SUITE_HPP
+#define BOOST_GRAPH_ADJACENCY_LIST_SUITE_HPP
+
+#include <boost/graphs/adjacency_list/adjacency_list.hpp>
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/adjacency_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/adjacency_list.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,412 @@
+
+#ifndef BOOST_GRAPH_ADJACENCY_LIST_HPP
+#define BOOST_GRAPH_ADJACENCY_LIST_HPP
+
+#include <boost/assert.hpp>
+
+#include <boost/graphs/utility.hpp>
+#include <boost/graphs/adjacency_list/types.hpp>
+#include <boost/graphs/adjacency_list/storage.hpp>
+#include <boost/graphs/adjacency_list/policy.hpp>
+
+// I think that if we concept-ize the internals of the adjacency list, then
+// we can filter the external interface. This would be a great place to use
+// constrained members.
+//
+// requires AssociativeStore<vertex_store> pair<...> insert_vertex();
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * The adjacency_list template is the basic implementation of an adjacency
+ * list graph structure. The adjacency list stores sets of both vertices and
+ * edges, with each vertex being associated with a set of incident edges.
+ *
+ * The adjacency list actually inherits most of its storage facilities from
+ * the vertex and edge storage types. These classes expose public interfaces
+ * for specific forms of vertex and edge management.
+ */
+template <
+    template <typename, typename, typename, typename, template <typename> class > class Type,
+    typename VertexProps = none,
+    typename EdgeProps = none,
+    template <typename> class VertexStore = vertex_vector,
+    template <typename> class EdgeStore = edge_vector,
+    template <typename> class VertexEdgeStore = vertex_edge_list,
+    template <typename> class AllowEdgePolicy = allow_loops_policy
+>
+class adjacency_list
+    : public VertexStore<
+            typename Type< // Instantiate the type over dummy stores
+                    VertexProps,
+                    EdgeProps,
+                    VertexStore<none>,
+                    EdgeStore<none>,
+                    VertexEdgeStore
+                >::vertex_type
+        >
+    , public EdgeStore<
+            typename Type< // Instantiate the type over dummy stores
+                    VertexProps,
+                    EdgeProps,
+                    VertexStore<none>,
+                    EdgeStore<none>,
+                    VertexEdgeStore
+                >::edge_type
+        >
+{
+    typedef Type<
+            VertexProps, EdgeProps, VertexStore<none>, EdgeStore<none>, VertexEdgeStore
+        > graph_type;
+
+public:
+    typedef VertexStore<typename graph_type::vertex_type> vertex_store;
+    typedef EdgeStore<typename graph_type::edge_type> edge_store;
+
+    typedef typename vertex_store::vertex_type vertex_type;
+    typedef typename vertex_store::vertex_descriptor vertex_descriptor;
+    typedef typename vertex_type::properties_type vertex_properties;
+
+    typedef typename edge_store::edge_type edge_type;
+    typedef typename edge_store::edge_descriptor edge_descriptor;
+    typedef typename edge_type::properties_type edge_properties;
+
+    adjacency_list();
+
+    // Add edge
+    // requires HasAdd<vertex_store>
+    edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v);
+    edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v, edge_properties const& ep);
+
+    // requires HasAdd<vertex_store> && UniqueComparableVertex<vertex_type>
+    edge_descriptor add_edge(vertex_properties const& u, vertex_properties const& v);
+    edge_descriptor add_edge(vertex_properties const& u, vertex_properties const& v, edge_properties const& ep);
+
+    // requires HasAdd<vertex_store> && UniqueMappedVertex<vertex_type> &&
+    //          SameType<Key, typename vertex_store::key_type>
+    template <typename Key> edge_descriptor add_edge(Key const& u, Key const& v);
+    template <typename Key> edge_descriptor add_edge(Key const& u, Key const& v, edge_properties const& ep);
+
+
+    // Insert edge (do we need these functions? - descriptors are evaluable).
+    // requires HasInsert<vertex_store>
+    std::pair<edge_descriptor, bool> insert_edge(vertex_descriptor u, vertex_descriptor v);
+    std::pair<edge_descriptor, bool> insert_edge(vertex_descriptor u, vertex_descriptor v, edge_properties const& ep);
+
+    // Vertex disconnect
+    // Requires HasRemove<edge_store> && ???
+    void disconnect_vertex(vertex_descriptor v);
+
+    // Vertex removal
+    // requires HasRemove<vertex_store>
+    void remove_vertex(vertex_descriptor v);
+
+    // Edge removal
+    // requires HasRemove<edge_store>
+    void remove_edge(edge_descriptor e);
+    void remove_edge(vertex_descriptor u, vertex_descriptor v);
+
+
+    // Descriptor accessor. Use these functions to get descriptors...
+    vertex_descriptor descriptor(vertex_type const& v) const;
+    edge_descriptor descriptor(edge_type const& e) const;
+
+    // Edge and vertex accessors
+    vertex_properties& properties(vertex_descriptor v);
+    vertex_properties const& properties(vertex_descriptor v) const;
+    edge_properties& properties(edge_descriptor e);
+    edge_properties const& properties(edge_descriptor e) const;
+
+};
+
+// Functions
+
+#define BOOST_GRAPH_ADJLIST_PARAMS \
+    template <typename, typename, typename, typename, template <typename> class> class T, \
+    typename VP, \
+    typename EP, \
+    template <typename> class VS, \
+    template <typename> class ES, \
+    template <typename> class VES, \
+    template <typename> class AEP
+
+/**
+ * Add a vertex to the graph with no or default properties.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::adjacency_list()
+    : vertex_store()
+    , edge_store()
+{ }
+
+/**
+ * Add a vertex to the graph with no or default properties.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::edge_descriptor
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::add_edge(
+        vertex_descriptor u,
+        vertex_descriptor v)
+{
+    return add_edge(u, v, edge_properties());
+}
+
+/**
+ * Add a vertex to the graph with the given properties. The edge will not be
+ * added (no action taken) if the endpoints form a loop.
+ *
+ * @todo What if the user intentially passes null vertices? We should add a
+ * loose or unconnected edge... but how does one actually manage these things?
+ * For now, operate on the assumption that the vertices are valid.
+ *
+ * @todo Similar to above, how do we want to handle loops. It's currently built
+ * as a simple boolean value that either allows the addition or not.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::edge_descriptor
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::add_edge(
+        vertex_descriptor u,
+        vertex_descriptor v,
+        edge_properties const& ep)
+{
+    typedef adjacency_list<T,VP,EP,VS,ES,VES,AEP> this_type;
+
+    edge_descriptor e;
+    if(AEP<this_type>::allow(u, v, ep)) {
+        e = edge_store::add_edge(u, v, ep);
+
+        this->vertex(u).connect_to(e);
+        this->vertex(v).connect_from(e);
+    }
+
+    return e;
+}
+
+/**
+ * Add an edge that connects the two vertices identified by the given
+ * properties.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::edge_descriptor
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::add_edge(
+        vertex_properties const& up,
+        vertex_properties const& vp)
+{
+    return add_edge(up, vp, edge_properties());
+}
+
+/**
+ * Add an edge that connects the two vertices identified by the given vertex
+ * properties, such that it will contain the have edge properties.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::edge_descriptor
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::add_edge(
+        vertex_properties const& up,
+        vertex_properties const& vp,
+        edge_properties const& ep)
+{
+    // Start by finding the vertices according to their properties.
+    vertex_descriptor u = find_vertex(up);
+    vertex_descriptor v = find_vertex(vp);
+    BOOST_ASSERT(u.is_valid() && v.is_valid());
+    return add_edge(u, v, ep);
+}
+
+/**
+ * Add an edge that connects the two vertices identified by their keys.
+ *
+ * @todo Without constrained members, instantiating this function can result in
+ * ambigous member functions with the vertex property add_edge() functions if
+ * the key type is the same as the vertex properties. We can probably also get
+ * rid of the Key template parameter and simply reference the maps key type
+ * here.
+ *
+ * @todo You have to explicitly give the key parameter here because of the
+ * other add_vertex() functions.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+template <typename Key>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::edge_descriptor
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::add_edge(
+        Key const& up,
+        Key const& vp)
+{
+    return add_edge<Key>(up, vp, edge_properties());
+}
+
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+template <typename Key>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::edge_descriptor
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::add_edge(
+        Key const& up,
+        Key const& vp,
+        edge_properties const& ep)
+{
+    // Start by finding the vertices according to their properties.
+    vertex_descriptor u = find_vertex(up);
+    vertex_descriptor v = find_vertex(vp);
+    BOOST_ASSERT(u.is_valid() && v.is_valid());
+    return add_edge(u, v, ep);
+}
+
+
+/**
+ * Add an edge that connects the given properties.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+std::pair<typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::edge_descriptor, bool>
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::insert_edge(
+        vertex_descriptor u,
+        vertex_descriptor v)
+{
+    return insert_edge(u, v, edge_properties());
+}
+
+/**
+ * Connect the vertex u to v and set the corresponding edge properties to ep.
+ * Return a pair containing an edge descriptor and a boolean value that
+ * indicates whether or not the edge was added. Note that if the graph does
+ * not allow self loops or loose edges, the edge descriptor will be null.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+std::pair<typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::edge_descriptor, bool>
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::insert_edge(
+        vertex_descriptor u,
+        vertex_descriptor v,
+        edge_properties const& ep)
+{
+    typedef adjacency_list<T,VP,EP,VS,ES,VES,AEP> this_type;
+
+    std::pair<edge_descriptor, bool> ret(edge_descriptor(), false);
+    if(AEP<this_type>::allow(u, v, ep)) {
+        ret = edge_store::insert_edge(u, v, ep);
+        if(ret.second) {
+            this->vertex(u).connect_to(ret.first);
+            this->vertex(v).connect_from(ret.first);
+        }
+    }
+}
+
+/**
+ * Disconnect this vertex from all others (remove all incident edges). This
+ * is typically a precursor operation for vertex removal to ensure that no
+ * dangling edges are left.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+void
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::disconnect_vertex(vertex_descriptor v)
+{
+    BOOST_ASSERT(v.is_valid());
+
+    // Optimal implementation depends on the vertex structure.
+    disconnect(*this, this->vertex(v), typename graph_type::tag());
+}
+
+/**
+ * Remove the given vertex from the graph. Note that this does not disconnect
+ * edges from the vertex before removing it. Removing a vertex connected to
+ * the graph can result in dangling edges.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+void
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::remove_vertex(vertex_descriptor v)
+{
+}
+
+/**
+ * Remove the given edge from the graph.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+void
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::remove_edge(edge_descriptor e)
+{
+    vertex_descriptor u = this->edge(e).source();
+    vertex_descriptor v = this->edge(e).target();
+    BOOST_ASSERT(u.is_valid() && v.is_valid());
+
+    this->vertex(u).disconnect_to(e);
+    this->vertex(v).disconnect_from(e);
+    edge_store::remove_edge(e);
+}
+
+/**
+ * Remove all edges connecting vertices u and v from the graph.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+void
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::remove_edge(
+        vertex_descriptor u,
+        vertex_descriptor v)
+{
+    // I suppose it would be a good idea to ensure that the local edges of
+    // u and v are actually removed also.
+    edge_store::remove_edge(u, v);
+}
+
+/**
+ * Get a descriptor for the given vertex.
+ *
+ * This may seem like a strange function, but there's currently no simple way
+ * to transform between the two types.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::vertex_descriptor
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::descriptor(vertex_type const& v) const
+{
+    typedef typename vertex_store::vertex_type stored_type;
+    return vertex_store::descriptor(static_cast<stored_type const&>(v));
+}
+
+/**
+ * Get vertex properties for the given vertex descriptor.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::vertex_properties&
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::properties(vertex_descriptor v)
+{
+    return vertex_store::properties(v);
+}
+
+/**
+ * Get vertex properties for the given vertex descriptor.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::vertex_properties const&
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::properties(vertex_descriptor v) const
+{
+    return vertex_store::properties(v);
+}
+
+/**
+ * Get edge properties for the given edge descriptor.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::edge_properties&
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::properties(edge_descriptor e)
+{
+    return edge_store::properties(e);
+}
+
+/**
+ * Get edge properties for the given edge descriptor.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::edge_properties const&
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::properties(edge_descriptor e) const
+{
+    return edge_store::properties(e);
+}
+
+#undef BOOST_GRAPH_ADJLIST_PARAMS
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+// Include a number common graph types.
+#include <boost/graphs/adjacency_list/graphs.hpp>
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/descriptor.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/descriptor.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,147 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_DESCRIPTOR_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_DESCRIPTOR_HPP
+
+#include <boost/functional/hash.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+// Important notes about descriptors
+//
+// A descriptor is basically an opaque reference to an object. It's kind of
+// like an iterator that can't be moved or dereferenced. It's kind of like a
+// flyweight, but you can't implicitly cast it as the shared object. In short,
+// you can't use descriptors without their graph. In general, we'd like the
+// descriptor types to be as trivial as possible. One of the most important
+// facts about descriptors is that, by themselves, they have absolutely no
+// semantics. They cannot be used (in general) be used to access the vertices
+// or edges that they represent.
+//
+// The most important thing to understand about descriptors is that they attempt
+// to model the most "consistent" reference into a storage mechanism. By the
+// term "consistent", we mean a means of accessing elements that allow us to
+// actually build a graph without invalidating memory or iterators. For example,
+// we can't use pointers as descriptors into vectors since vectors occasionally
+// reallocate all their memory (oops), but indices work just fine.
+//
+// Descriptors must be completely independent of the actual type of vertices
+// and edges. Two problems arise if we don't do this. First, we end up with
+// weird cyclic type dependencies that can probably be unrolled using some
+// funky lazy template evaluation, but that's generally beyond me. Second,
+// this would
+
+// Build trivial wrappers around the underlying descriptor types. This allows
+// us to differentiate descriptors based on these types rather than their
+// simple descriptor types.
+
+
+// Convenience functions for building a default descriptor depending on the
+// underlying descriptor type.
+inline std::size_t default_descriptor(std::size_t)
+{ return std::size_t(-1); }
+
+inline void* default_descriptor(void*)
+{ return 0; }
+
+template <typename D>
+struct descriptor
+{
+    inline descriptor()
+        : desc(default_descriptor(D()))
+    { }
+
+    inline descriptor(D d)
+        : desc(d)
+    { }
+
+    // Assignment copy.
+    inline descriptor& operator=(descriptor const& d)
+    {
+        desc = d.desc;
+        return *this;
+    }
+
+    // value-type assignment.
+    inline descriptor& operator=(D d)
+    {
+        desc = d;
+        return *this;
+    }
+
+    // Just to make the access a little prettier.
+    inline D get() const
+    { return desc; }
+
+    // Provides an implicit cast to bool. Returns true if the descriptor
+    // is not the same as its default value.
+    inline bool is_valid() const
+    { return desc != descriptor().desc; }
+
+    inline bool operator<(descriptor const& d) const
+    { return desc < d.desc; }
+
+    inline bool operator==(descriptor const& d) const
+    { return desc == d.desc; }
+
+    inline bool operator!=(descriptor const& d) const
+    { return desc != d.desc; }
+
+    D desc;
+};
+
+// Hash value specializatins for the descriptor types.
+template <typename D>
+inline std::size_t hash_value(descriptor<D> const& d)
+{
+    return hash_value(d.get());
+}
+
+// Apparently, there's not a built-in hash for void ptrs.
+template <>
+inline std::size_t hash_value(descriptor<void*> const& d)
+{
+    return reinterpret_cast<std::size_t>(d.get());
+}
+
+/**
+ * Wraps a vertex descriptor. Valid template argument are either size_t or
+ * void*.
+ */
+template <typename D>
+struct vertex_desc
+    : public descriptor<D>
+{
+    inline vertex_desc()
+        : descriptor<D>()
+    { }
+
+    inline vertex_desc(D d)
+        : descriptor<D>(d)
+    { }
+};
+
+/**
+ * Wraps an edge descriptor. Valid template arguments are either size_t or
+ * void*.
+ */
+template <typename D>
+struct edge_desc
+    : public descriptor<D>
+{
+    inline edge_desc()
+        : descriptor<D>()
+    { }
+
+    inline edge_desc(D d)
+        : descriptor<D>(d)
+    { }
+};
+
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/edge.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/edge.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,64 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_EDGE_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_EDGE_HPP
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * The edge template is the base class of different edge types for adjacency
+ * lists. It essentially provides common functionality for associating
+ * user-defined properties with edge structures.
+ */
+template <typename EdgeProps>
+class edge
+{
+public:
+    typedef EdgeProps properties_type;
+
+    edge();
+    edge(properties_type const& ep);
+
+    // Property accessors...
+    properties_type* operator->();
+    properties_type& operator*();
+    properties_type const& operator*() const;
+
+private:
+    properties_type _props;
+};
+
+// Functions
+
+template <typename EP>
+edge<EP>::edge()
+    : _props()
+{ }
+
+template <typename EP>
+edge<EP>::edge(properties_type const& ep)
+    : _props(ep)
+{ }
+
+template <typename VP>
+typename edge<VP>::properties_type*
+edge<VP>::operator->()
+{ return &_props; }
+
+template <typename VP>
+typename edge<VP>::properties_type&
+edge<VP>::operator*()
+{ return _props; }
+
+template <typename VP>
+typename edge<VP>::properties_type const&
+edge<VP>::operator*() const
+{ return _props; }
+
+} /* namespace adjacency_lists */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif
+

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_list.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,289 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_EDGE_LIST_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_EDGE_LIST_HPP
+
+#include <list>
+
+#include <boost/graphs/adjacency_list/es/value_edge_iterator.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+namespace detail {
+    // Extend the notion of an edge for the edge set. Here, each edge also
+    // stores an iterator to itself in the store. A little incestuous, but
+    // it enables constant-time removals.
+    template <typename Edge, template <typename> class Alloc>
+    class basic_edge_list_node
+        : public Edge
+    {
+        typedef basic_edge_list_node<Edge, Alloc> this_type;
+    public:
+        typedef typename Edge::vertex_descriptor vertex_descriptor;
+        typedef typename Edge::properties_type properties_type;
+
+        typedef typename std::list<
+                this_type, Alloc<this_type>
+            >::iterator iterator;
+
+        inline basic_edge_list_node(vertex_descriptor u,
+                                    vertex_descriptor v,
+                                    properties_type const& p)
+            : Edge(u, v, p)
+            , iter()
+        { }
+
+        iterator iter;
+    };
+
+} /* namespace detail */
+
+/**
+ * The edge list can be used to implement multigraphs with removable edges.
+ * It's insert and remove functions are constant time functions, but accessing
+ * the number of edges is a linear time operation.
+ */
+template <
+        typename Edge,
+        template <typename> class Alloc
+    >
+class basic_edge_list
+{
+public:
+    typedef detail::basic_edge_list_node<Edge, Alloc> edge_type;
+    typedef typename edge_type::descriptor_type edge_descriptor;
+    typedef typename edge_type::vertex_descriptor vertex_descriptor;
+    typedef typename edge_type::properties_type edge_properties;
+
+    typedef std::list<edge_type, Alloc<edge_type> > edge_store;
+    typedef value_edge_iterator<edge_store> edge_iterator;
+    typedef typename edge_store::size_type edges_size_type;
+
+    // FIXME:
+    typedef hashed_property_map_tag edge_property_map_category;
+
+    basic_edge_list();
+
+    // Add edge
+    edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v);
+    edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v, edge_properties const& ep);
+
+    // Remove edge
+    void remove_edge(edge_descriptor e);
+    void remove_edge(vertex_descriptor u, vertex_descriptor v);
+
+    // Number of edges
+    edges_size_type num_edges() const;
+
+    // Edge iterator accessors.
+    std::pair<edge_iterator, edge_iterator> edges() const;
+    edge_iterator begin_edges() const;
+    edge_iterator end_edges() const;
+
+    // Edge and edge property accessors.
+    edge_type& edge(edge_descriptor e);
+    edge_type const& edge(edge_descriptor e) const;
+    edge_descriptor descriptor(edge_type const& e) const;
+
+    // Property accessors
+    edge_properties& properties(edge_descriptor e);
+    edge_properties const& properties(edge_descriptor e) const;
+
+private:
+    edge_store _edges;
+};
+
+/**
+ * The default specialization uses the standard less comparator and the
+ * standard allocator.
+ */
+template <typename Edge>
+struct edge_list : basic_edge_list<Edge, std::allocator> { };
+
+// Functions
+
+#define BOOST_GRAPH_EL_PARAMS \
+    typename E, template <typename> class A
+
+template <BOOST_GRAPH_EL_PARAMS>
+basic_edge_list<E,A>::basic_edge_list()
+    : _edges()
+{ }
+
+/**
+ * Add an edge to the set with no or default properties. If the edge already
+ * exists in the set, no action is taken. Return a descruptor for the added
+ * or existing edge.
+ */
+template <BOOST_GRAPH_EL_PARAMS>
+typename basic_edge_list<E,A>::edge_descriptor
+basic_edge_list<E,A>::add_edge(vertex_descriptor u, vertex_descriptor v)
+{
+    return add(u, v, edge_properties());
+}
+
+/**
+ * Add an edge to the set with the given properties. If the edge already exists,
+ * then no action is taken. Return a descriptor for the added or existing edge.
+ */
+template <BOOST_GRAPH_EL_PARAMS>
+typename basic_edge_list<E,A>::edge_descriptor
+basic_edge_list<E,A>::add_edge(vertex_descriptor u,
+                               vertex_descriptor v,
+                               edge_properties const& ep)
+{
+    typename edge_store::iterator i =
+            _edges.insert(_edges.end(), edge_type(u, v, ep));
+    i->iter = i;
+    return &(*i);
+}
+
+/**
+ * Remove the given edge from the edge set.
+ *
+ * @complexity O(|E|)
+ */
+template <BOOST_GRAPH_EL_PARAMS>
+void
+basic_edge_list<E,A>::remove_edge(edge_descriptor e)
+{
+    // Basically, iterate over the edge list until we find the descriptor
+    // e, then erase it. Note that descriptors are unique so there's really
+    // only one such e.
+    typename edge_store::iterator i = _edges.begin(), end = _edges.end();
+    for( ; i != end; ++i) {
+        if(descriptor(*i) == e) {
+            _edges.erase(i);
+            break;
+        }
+    }
+}
+
+/**
+ * Remove all edges connecting the vertices u and v from the set.
+ *
+ * @complexity O(|E|)
+ */
+template <BOOST_GRAPH_EL_PARAMS>
+void
+basic_edge_list<E,A>::remove_edge(vertex_descriptor u, vertex_descriptor v)
+{
+    // Create a temporary edge over u and v. This will sort the vertices as
+    // needed before actually inserting it.
+    edge_type tmp(u, v, edge_properties());
+
+    // Iterate over the edges and erase those connecting u and v.
+    typename edge_store::iterator i = _edges.begin(), end = _edges.end();
+    for( ; i != end; ) {
+        if(*i == tmp) {
+            i = _edges.erase(i);
+        }
+        else {
+            ++i;
+        }
+    }
+}
+
+
+/**
+ * Get the number of edges in the edge set.
+ */
+template <BOOST_GRAPH_EL_PARAMS>
+typename basic_edge_list<E,A>::edges_size_type
+basic_edge_list<E,A>::num_edges() const
+{
+    return _edges.size();
+}
+
+/**
+ * Get an iterator range for the edge set.
+ */
+template <BOOST_GRAPH_EL_PARAMS>
+std::pair<
+    typename basic_edge_list<E,A>::edge_iterator,
+    typename basic_edge_list<E,A>::edge_iterator
+>
+basic_edge_list<E,A>::edges() const
+{
+    return std::make_pair(begin_edges(), end_edges());
+}
+
+/**
+ * Get an iterator to the first edge in the set.
+ */
+template <BOOST_GRAPH_EL_PARAMS>
+typename basic_edge_list<E,A>::edge_iterator
+basic_edge_list<E,A>::begin_edges() const
+{
+    return _edges.begin();
+}
+
+/**
+ * Get an iterator past the end of the edge set.
+ */
+template <BOOST_GRAPH_EL_PARAMS>
+typename basic_edge_list<E,A>::edge_iterator
+basic_edge_list<E,A>::end_edges() const
+{
+    return _edges.end();
+}
+
+/**
+ * Get access to the given edge.
+ */
+template <BOOST_GRAPH_EL_PARAMS>
+typename basic_edge_list<E,A>::edge_type&
+basic_edge_list<E,A>::edge(edge_descriptor e)
+{
+    return *static_cast<edge_type*>(e.desc);
+}
+
+/**
+ * Get access to the given edge.
+ */
+template <BOOST_GRAPH_EL_PARAMS>
+typename basic_edge_list<E,A>::edge_type const&
+basic_edge_list<E,A>::edge(edge_descriptor e) const
+{
+    return *static_cast<edge_type*>(e.desc);
+}
+
+/**
+ * Get a descriptor for the given edge.
+ */
+template <BOOST_GRAPH_EL_PARAMS>
+typename basic_edge_list<E,A>::edge_descriptor
+basic_edge_list<E,A>::descriptor(edge_type const& e) const
+{
+    return &const_cast<edge_type&>(e);
+}
+
+
+/**
+ * Access the properties of the given edge.
+ */
+template <BOOST_GRAPH_EL_PARAMS>
+typename basic_edge_list<E,A>::edge_properties&
+basic_edge_list<E,A>::properties(edge_descriptor e)
+{
+    return *edge(e);
+}
+
+/**
+ * Access the properties of the given edge.
+ */
+template <BOOST_GRAPH_EL_PARAMS>
+typename basic_edge_list<E,A>::edge_properties const&
+basic_edge_list<E,A>::properties(edge_descriptor e) const
+{
+    return *edge(e);
+}
+
+#undef BOOST_GRAPH_EL_PARAMS
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_multiset.hpp
==============================================================================

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_set.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_set.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,270 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_EDGE_SET_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_EDGE_SET_HPP
+
+#include <set>
+
+#include <boost/graphs/adjacency_list/es/value_edge_iterator.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+namespace detail {
+    // Extend the notion of an edge for the edge set. Here, each edge also
+    // stores an iterator to itself in the store. A little incestuous, but
+    // it enables constant-time removals.
+    template <
+            typename Edge,
+            template <typename> class Compare,
+            template <typename> class Alloc
+        >
+    class basic_edge_set_node
+        : public Edge
+    {
+        typedef basic_edge_set_node<Edge, Compare, Alloc> this_type;
+    public:
+        typedef typename Edge::vertex_descriptor vertex_descriptor;
+        typedef typename Edge::properties_type properties_type;
+
+        typedef typename std::set<
+                this_type, Compare<this_type>, Alloc<this_type>
+            >::iterator iterator;
+
+        inline basic_edge_set_node(vertex_descriptor u,
+                                   vertex_descriptor v,
+                                   properties_type const& ep)
+            : Edge(ep)
+            , iter()
+        { }
+
+        iterator iter;
+    };
+
+} /* namespace detail */
+
+/**
+ * The edge set is basically used to implement simple graphs by not adding
+ * duplicate (parallel) edges to the graph. This class considers edges to
+ * be parallel if they have the same edge descriptors (i.e., the edges are
+ * equivalent).
+ *
+ * Note that this underlying store also supports edge removals.
+ */
+template <
+        typename Edge,
+        template <typename> class Compare,
+        template <typename> class Alloc
+    >
+class basic_edge_set
+{
+public:
+    typedef detail::basic_edge_set_node<Edge, Compare, Alloc> edge_type;
+    typedef typename edge_type::descriptor_type edge_descriptor;
+    typedef typename edge_type::properties_type edge_properties;
+
+    typedef typename edge_type::vertex_descriptor vertex_descriptor;
+
+    typedef std::set<edge_type, Compare<edge_type>, Alloc<edge_type> > edge_store;
+    typedef value_edge_iterator<edge_store> edge_iterator;
+    typedef typename edge_store::size_type edges_size_type;
+
+    // FIXME:
+    typedef hashed_property_map_tag edge_property_map_category;
+
+    basic_edge_set();
+
+    // Add edge
+    edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v);
+    edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v, edge_properties const& ep);
+
+    // Insert edge
+    std::pair<edge_descriptor, bool> insert_edge(vertex_descriptor u, vertex_descriptor v);
+    std::pair<edge_descriptor, bool> insert_edge(vertex_descriptor u, vertex_descriptor v, edge_properties const& ep);
+
+    // Number of edges
+    edges_size_type num_edges() const;
+
+    // Edge iterator accessors.
+    std::pair<edge_iterator, edge_iterator> edges() const;
+    edge_iterator begin_edges() const;
+    edge_iterator end_edges() const;
+
+    // Edge accessors
+    edge_type& edge(edge_descriptor e);
+    edge_type const& edge(edge_descriptor e) const;
+    edge_properties& properties(edge_descriptor e);
+    edge_properties const& properties(edge_descriptor e) const;
+
+private:
+    edge_store _edges;
+};
+
+/**
+ * The default specialization uses the standard less comparator and the
+ * standard allocator.
+ */
+template <typename Edge>
+struct edge_set : basic_edge_set<Edge, std::less, std::allocator> { };
+
+// Functions
+
+#define BOOST_GRAPH_ES_PARAMS \
+    typename E, template <typename> class C, template <typename> class A
+
+template <BOOST_GRAPH_ES_PARAMS>
+basic_edge_set<E,C,A>::basic_edge_set()
+    : _edges()
+{ }
+
+/**
+ * Add an edge to the set with no or default properties. If the edge already
+ * exists in the set, no action is taken. Return a descruptor for the added
+ * or existing edge.
+ */
+template <BOOST_GRAPH_ES_PARAMS>
+typename basic_edge_set<E,C,A>::edge_descriptor
+basic_edge_set<E,C,A>::add_edge(vertex_descriptor u, vertex_descriptor v)
+{
+    return insert_edge(u, v).first;
+}
+
+/**
+ * Add an edge to the set with the given properties. If the edge already exists,
+ * then no action is taken. Return a descriptor for the added or existing edge.
+ */
+template <BOOST_GRAPH_ES_PARAMS>
+typename basic_edge_set<E,C,A>::edge_descriptor
+basic_edge_set<E,C,A>::add_edge(vertex_descriptor u,
+                              vertex_descriptor v,
+                              edge_properties const& ep)
+{
+    return insert_edge(u, v, ep).first;
+}
+
+/**
+ *
+ */
+template <BOOST_GRAPH_ES_PARAMS>
+std::pair<typename basic_edge_set<E,C,A>::edge_descriptor, bool>
+basic_edge_set<E,C,A>::insert_edge(vertex_descriptor u, vertex_descriptor v)
+{
+    return insert_edge(u, v, edge_properties());
+}
+
+
+/**
+ * Add an edge with the given properties to the edge store.
+ */
+template <BOOST_GRAPH_ES_PARAMS>
+std::pair<typename basic_edge_set<E,C,A>::edge_descriptor, bool>
+basic_edge_set<E,C,A>::insert_edge(vertex_descriptor u,
+                                 vertex_descriptor v,
+                                 edge_properties const& ep)
+{
+    std::pair<edge_descriptor, bool> ret;
+    std::pair<typename edge_store::iterator, bool> ins =
+            _edges.insert(edge_type(u, v, ep));
+    if(ins.second) {
+        // Not very pretty...
+        edge_type& e = const_cast<edge_type&>(*(ins.first));
+        e.iter = ins.first;
+        ret.first = &e;
+    }
+    else {
+        ret.first = &const_cast<edge_type&>(*ins.first);
+    }
+    ret.second = ins.second;
+    return ret;
+}
+
+/**
+ * Get the number of edges in the edge set.
+ */
+template <BOOST_GRAPH_ES_PARAMS>
+typename basic_edge_set<E,C,A>::edges_size_type
+basic_edge_set<E,C,A>::num_edges() const
+{
+    return _edges.size();
+}
+
+/**
+ * Get an iterator range for the edge set.
+ */
+template <BOOST_GRAPH_ES_PARAMS>
+std::pair<
+    typename basic_edge_set<E,C,A>::edge_iterator,
+    typename basic_edge_set<E,C,A>::edge_iterator
+>
+basic_edge_set<E,C,A>::edges() const
+{
+    return std::make_pair(begin_edges(), end_edges());
+}
+
+/**
+ * Get an iterator to the first edge in the set.
+ */
+template <BOOST_GRAPH_ES_PARAMS>
+typename basic_edge_set<E,C,A>::edge_iterator
+basic_edge_set<E,C,A>::begin_edges() const
+{
+    return _edges.begin();
+}
+
+/**
+ * Get an iterator past the end of the edge set.
+ */
+template <BOOST_GRAPH_ES_PARAMS>
+typename basic_edge_set<E,C,A>::edge_iterator
+basic_edge_set<E,C,A>::end_edges() const
+{
+    return _edges.end();
+}
+
+/**
+ * Get access to the given edge.
+ */
+template <BOOST_GRAPH_ES_PARAMS>
+typename basic_edge_set<E,C,A>::edge_type&
+basic_edge_set<E,C,A>::edge(edge_descriptor e)
+{
+    return *static_cast<edge_type*>(e.desc);
+}
+
+/**
+ * Get access to the given edge.
+ */
+template <BOOST_GRAPH_ES_PARAMS>
+typename basic_edge_set<E,C,A>::edge_type const&
+basic_edge_set<E,C,A>::edge(edge_descriptor e) const
+{
+    return *static_cast<edge_type*>(e.desc);
+}
+
+/**
+ * Access the properties of the given edge.
+ */
+template <BOOST_GRAPH_ES_PARAMS>
+typename basic_edge_set<E,C,A>::edge_properties&
+basic_edge_set<E,C,A>::properties(edge_descriptor e)
+{
+    return *edge(e);
+}
+
+/**
+ * Access the properties of the given edge.
+ */
+template <BOOST_GRAPH_ES_PARAMS>
+typename basic_edge_set<E,C,A>::edge_properties const&
+basic_edge_set<E,C,A>::properties(edge_descriptor e) const
+{
+    return *edge(e);
+}
+
+#undef BOOST_GRAPH_ES_PARAMS
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_vector.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,171 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_EDGE_VECTOR_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_EDGE_VECTOR_HPP
+
+#include <vector>
+
+#include <boost/graphs/adjacency_list/es/indexed_edge_iterator.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * The edge vector implements a trivial multiset of edges for a graph (i.e., a
+ * multigraph). Note that the underlying store does not permit the removal of
+ * edges from the graph.
+ */
+template <typename Edge, template <typename> class Alloc>
+class basic_edge_vector
+{
+public:
+    typedef Edge edge_type;
+    typedef typename edge_type::descriptor_type edge_descriptor;
+    typedef typename edge_type::vertex_descriptor vertex_descriptor;
+    typedef typename edge_type::properties_type edge_properties;
+
+    typedef std::vector<edge_type, Alloc<edge_type> > edge_store;
+    typedef indexed_edge_iterator<edge_store> edge_iterator;
+    typedef typename edge_store::size_type edges_size_type;
+
+    // FIXME:
+    typedef indexed_property_map_tag edge_property_map_category;
+
+    basic_edge_vector();
+
+    // Add edge
+    edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v);
+    edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v, edge_properties const& ep);
+
+    // Number of edges.
+    edges_size_type num_edges() const;
+
+    // Edge iterator access.
+    std::pair<edge_iterator, edge_iterator> edges() const;
+    edge_iterator begin_edges() const;
+    edge_iterator end_edges() const;
+
+private:
+    edge_store _edges;
+};
+
+/**
+ * Specialize storage traits for all types of edge vectors to use indexed
+ * descriptors rather than memory descriptors.
+ *
+ * @todo This don't work.
+ */
+template <typename Edge, template <typename> class Alloc>
+struct storage_traits< basic_edge_vector<Edge, Alloc> >
+{
+    typedef std::size_t descriptor_type;
+};
+
+/**
+ * The default specialization uses the standard allocator.
+ */
+template <typename Edge>
+struct edge_vector : basic_edge_vector<Edge, std::allocator> { };
+
+/**
+ * Specialize the storage traits for the default specialization. We wouldn't
+ * have to do this if partial specializations over template template parameters
+ * worked the way I thought they did.
+ */
+template <typename Edge>
+struct storage_traits< edge_vector<Edge> >
+{
+    typedef std::size_t descriptor_type;
+};
+
+// Functions
+
+template <typename E, template <typename> class A>
+basic_edge_vector<E,A>::basic_edge_vector()
+    : _edges()
+{ }
+
+/**
+ * Add an edge to the store with no or default properties. Note that adding
+ * an edge using this method does not manage the endpoints of each vertex.
+ * Basically, this class is not much more than a simple edge list.
+ *
+ * Adding an edge does not invalidate any descriptors.
+ *
+ * @complexity O(1) amortized
+ */
+template <typename E, template <typename> class A>
+typename basic_edge_vector<E,A>::edge_descriptor
+basic_edge_vector<E,A>::add_edge(vertex_descriptor u, vertex_descriptor v)
+{
+    return add_edge(u, v, edge_properties());
+}
+
+/**
+ * Add an edge to the store with the given properties. Note that adding an edge
+ * to a graph using this method does not manage the endpoints of each vertex.
+ * Basically, this class is not much more than a simple edge list.
+ *
+ * Adding an edge does not invalidate any descriptors.
+ *
+ * @complexity O(1) amortized
+ */
+template <typename E, template <typename> class A>
+typename basic_edge_vector<E,A>::edge_descriptor
+basic_edge_vector<E,A>::add_edge(vertex_descriptor u,
+                                 vertex_descriptor v,
+                                 edge_properties const& ep)
+{
+    // Add the edge object. Its descriptor is its index.
+    std::cout << "here?" << std::endl;
+    _edges.push_back(edge_type(u, v, ep));
+    return _edges.size() - 1;
+}
+
+/**
+ * Get the number of edges.
+ *
+ * @complexity O(1)
+ */
+template <typename E, template <typename> class A>
+typename basic_edge_vector<E,A>::edges_size_type
+basic_edge_vector<E,A>::num_edges() const
+{
+    return _edges.size();
+}
+
+/**
+ * Get an iterator range over the edges in the edge set.
+ */
+template <typename E, template <typename> class A>
+std::pair<
+    typename basic_edge_vector<E,A>::edge_iterator,
+    typename basic_edge_vector<E,A>::edge_iterator
+>
+basic_edge_vector<E,A>::edges() const
+{
+    return make_pair(begin_edges(), end_edges());
+}
+
+/**
+ * Get an iterator to the first edge.
+ */
+template <typename E, template <typename> class A>
+typename basic_edge_vector<E,A>::edge_iterator
+basic_edge_vector<E,A>::begin_edges() const
+{
+    return edge_iterator(_edges, _edges.begin());
+}
+
+template <typename E, template <typename> class A>
+typename basic_edge_vector<E,A>::edge_iterator
+basic_edge_vector<E,A>::end_edges() const
+{
+    return edge_iterator(_edges, _edges.end());
+}
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/indexed_edge_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/indexed_edge_iterator.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,67 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_INDEXED_EDGE_ITERATOR_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_INDEXED_EDGE_ITERATOR_HPP
+
+#include <algorithm>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * The indexed edge iterator provides an edge iterator for stores whose
+ * descriptors cannot be pointers (i.e., vectors).
+ */
+template <typename Store>
+class indexed_edge_iterator
+{
+    typedef typename Store::const_iterator iterator;
+public:
+    typedef typename Store::value_type edge_type;
+    typedef typename edge_type::descriptor_type edge_descriptor;
+
+    typedef edge_descriptor value_type;
+    typedef edge_descriptor reference;
+    typedef edge_descriptor pointer;
+
+    indexed_edge_iterator()
+        : store(0)
+        , iter()
+    { }
+
+    indexed_edge_iterator(indexed_edge_iterator const& x)
+        : store(x.store)
+        , iter(x.iter)
+    { }
+
+    indexed_edge_iterator(Store const& s, iterator const& x)
+        : store(&s)
+        , iter(x)
+    { }
+
+    indexed_edge_iterator& operator++()
+    {
+        ++iter;
+        return *this;
+    }
+
+    // The returned descriptor is simply the distance from the beginning of
+    // the underlying store to the end.
+    reference operator*()
+    { return std::distance(store->begin(), iter); }
+
+    bool operator==(indexed_edge_iterator const& x) const
+    { return (store == x.store) && (iter == x.iter); }
+
+    bool operator!=(indexed_edge_iterator const& x) const
+    { return (store == x.store) && (iter != x.iter); }
+
+    Store const* store;
+    iterator iter;
+};
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/value_edge_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/value_edge_iterator.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,60 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VALUE_EDGE_ITERATOR_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_VALUE_EDGE_ITERATOR_HPP
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * The value edge iterator provides a edge iterator unique associative
+ * containers and sequences that don't invalidate memory on insertions
+ * (lists).
+ */
+template <typename Store>
+class value_edge_iterator
+{
+    typedef typename Store::const_iterator iterator;
+public:
+    typedef typename Store::value_type edge_type;
+    typedef typename edge_type::descriptor_type edge_descriptor;
+
+    typedef edge_descriptor value_type;
+    typedef edge_descriptor reference;
+    typedef edge_descriptor pointer;
+
+    value_edge_iterator()
+        : iter()
+    { }
+
+    value_edge_iterator(value_edge_iterator const& x)
+        : iter(x.iter)
+    { }
+
+    value_edge_iterator(iterator const& x)
+        : iter(x)
+    { }
+
+    value_edge_iterator& operator++()
+    {
+        ++iter;
+        return *this;
+    }
+
+    reference operator*()
+    { return &const_cast<edge_type&>(*iter); }
+
+    bool operator==(value_edge_iterator const& x) const
+    { return iter == x.iter; }
+
+    bool operator!=(value_edge_iterator const& x) const
+    { return iter != x.iter; }
+
+    iterator iter;
+};
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/graphs.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/graphs.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,78 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_GRAPHS_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_GRAPHS_HPP
+
+// Common graph types provide cleaner interfaces to the basic adjacency list
+// type. This is done by providing a number of default template arguments and
+// rearranging the parameters to better suit the graph.
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * A simple graph is undirected, does not allow parallel edges or loops and
+ * has anonymous vertices.
+ *
+ * Changing the vertex store to a set will allow vertices to be inserted
+ * according to uniqueness, but will slow down the construction of the graph.
+ * However, searches for specific will be significantly faster.
+ *
+ * The default preference tends towards better mutability. Changing the vertex
+ * store from a list to a vertex will yield better performance, but vertices
+ * cannot be removed.
+ */
+template <
+    typename VertexProps = none,
+    typename EdgeProps = none,
+    template <typename> class VertexStore = vertex_list,
+    template <typename> class EdgeStore = edge_set,
+    template <typename> class VertexEdgeStore = vertex_edge_list
+>
+struct graph
+    : adjacency_list<
+        undirected,
+        VertexProps,
+        EdgeProps,
+        VertexStore,
+        EdgeStore,
+        VertexEdgeStore,
+        no_loops_policy>
+{ };
+
+/**
+ * A multigraph is undirected, allows parallel edges and loops, and has
+ * anonymous vertices.
+ *
+ * Changing the vertex store to a set will allow vertices to be inserted
+ * according to uniqueness, but will slow down the construction of the graph.
+ * However, searches for specific will be significantly faster.
+ *
+ * The default preference tends towards better mutability. Changing the vertex
+ * and edge stores will yield better performance, but removals will not be
+ * allowed.
+ */
+template <
+    typename VertexProps = none,
+    typename EdgeProps = none,
+    template <typename> class VertexStore = vertex_list,
+    template <typename> class EdgeStore = edge_list,
+    template <typename> class VertexEdgeStore = vertex_edge_list
+>
+struct multigraph
+    : adjacency_list<
+        undirected,
+        VertexProps,
+        EdgeProps,
+        VertexStore,
+        EdgeStore,
+        VertexEdgeStore,
+        allow_loops_policy>
+{ };
+
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/policy.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/policy.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,56 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_POLICY_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_POLICY_HPP
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * Given valid vertex descriptors u and v, this policy will allow the addition
+ * of loops (i.e., u == v).
+ */
+template <typename Graph>
+struct allow_loops_policy
+{
+    static const bool allows_loose = false;
+    static const bool allows_loops = true;
+
+    typedef typename Graph::vertex_descriptor vertex;
+    typedef typename Graph::edge_descriptor edge;
+    typedef typename Graph::edge_properties properties;
+
+    static bool allow(vertex u, vertex v, properties const& ep)
+    {
+        BOOST_ASSERT(u.is_valid() && v.is_valid());
+        return true;
+    }
+};
+
+/**
+ * Given valid vertex descriptors u and v, this policy will not allow the
+ * addition of loops.
+ */
+template <typename Graph>
+struct no_loops_policy
+{
+    static const bool allows_loose = false;
+    static const bool allows_loops = false;
+
+    typedef typename Graph::vertex_descriptor vertex;
+    typedef typename Graph::edge_descriptor edge;
+    typedef typename Graph::edge_properties properties;
+
+    static bool allow(vertex u, vertex v, properties const& ep)
+    {
+        BOOST_ASSERT(u.is_valid() && v.is_valid());
+        return u != v;
+    }
+};
+
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/storage.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/storage.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,37 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_STORAGE_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_STORAGE_HPP
+
+#include <boost/graphs/adjacency_list/storage_traits.hpp>
+
+
+// Vertex storage types
+// We can store vertices in almost anything conceivable. These are the default
+// options for storing. Note that we could expand this set to also include
+// multi stores and hash stores as well. The differences aren't so great. In
+// fact, we could put just about anything here as long as we can bind it to
+// a couple of common interfaces.
+#include <boost/graphs/adjacency_list/vs/vertex_vector.hpp>
+#include <boost/graphs/adjacency_list/vs/vertex_list.hpp>
+#include <boost/graphs/adjacency_list/vs/vertex_set.hpp>
+#include <boost/graphs/adjacency_list/vs/vertex_map.hpp>
+
+// Edge storage types
+// Fortunately, there are really only two types of edge storage, sets and
+// multisets. Note, however, that these can be implemented in a couple of
+// different ways (e.g., vector or list as a multiset).
+#include <boost/graphs/adjacency_list/es/edge_vector.hpp>
+#include <boost/graphs/adjacency_list/es/edge_list.hpp>
+#include <boost/graphs/adjacency_list/es/edge_set.hpp>
+#include <boost/graphs/adjacency_list/es/edge_multiset.hpp>
+
+// Vertex edge storage types
+// The vertex edge storage types define the actual adjacency list component
+// of each vertex. Like above, there aren't actually too many types of vertex
+// edge storage since, for example, mapped containers don't make a lot of sense.
+// However, vectors, lists, and sets (both single and multi) work just fine.
+#include <boost/graphs/adjacency_list/ves/vertex_edge_vector.hpp>
+#include <boost/graphs/adjacency_list/ves/vertex_edge_list.hpp>
+#include <boost/graphs/adjacency_list/ves/vertex_edge_set.hpp>
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/storage_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/storage_traits.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,38 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_STORAGE_TRAITS_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_STORAGE_TRAITS_HPP
+
+#include <boost/graphs/adjacency_list/descriptor.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * This is primarilly used to decouple graph-related types from the underlying
+ * storage implementations. The default option is to simply use a void pointer
+ * as an opaque reference to objects in graphs. Clearly, pointers aren't the
+ * most useful opaque references for all types since memory can come and go
+ * as storage memory is reallocated (e.g., vector).
+ *
+ * @todo Obviously, this will become a concept in the not-so distant future.
+ */
+template <typename Store>
+struct storage_traits
+{
+    typedef void* descriptor_type;
+};
+
+// Quick note on unordered_* containers...
+// Apparently, insertions don't invalidate iterators (i.e., allocated memory)
+// so we can use pointers for those stores also. This is probably due to the
+// use of lists as the bucket structure of the underlying hash tables.
+// I hope...
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+
+#endif
+

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/types.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/types.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,39 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_TYPES_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_TYPES_HPP
+
+// These are "types" of graphs that pretty much define the basic structural
+// management features for adjacency lists. Because the actual interface of
+// the data structure depends primarily on the directedness of its edges,
+// all of the basic components are defined within these types. In fact, we
+// might think of all of these as different versions of the same graph.
+
+// Creating new types of graphs really just means copying and modifying one
+// of the existing graph types. It might be a lot of work, but it should
+// actually pay off if you really need to do something new.
+
+
+// Notes..
+// One of the "hard" things to think about is the generalization of outgoing
+// or incident edges between undirected and directed graphs. This distinction
+// is important since we can usually treat the two types of graphs in a similar
+// manner. Getting the edges of an undirected vertex means getting all incident
+// edges. Getting the edges of a directed vertex means getting the outgoing
+// edges. For generic algorithms, there needs to be a concept "default edge
+// type" concept that provides either the incident or out edges of the vertex.
+//
+// It might just be easy enough to build an "incident" edge type and accessor
+// for directed vertices that simply returns or something like that.
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+} /* adj_list */
+} /* graphs */
+} /* boost */
+
+
+#include <boost/graphs/adjacency_list/undirected.hpp>
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/undirected.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/undirected.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,429 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_HPP
+
+#include <list>
+
+#include <boost/graphs/utility/unordered_pair.hpp>
+#include <boost/graphs/adjacency_list/vertex.hpp>
+#include <boost/graphs/adjacency_list/edge.hpp>
+#include <boost/graphs/adjacency_list/storage_traits.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+// Implementation of undirected adjacency lists.
+
+// Forward declarations
+template <typename VP, typename EP, typename V, typename E, template <typename> class VES> struct undirected_vertex;
+template <typename VP, typename EP, typename V, typename E> struct undirected_edge;
+
+// Unfortunately, I have to hack out a little tag dispatch here... This will
+// go away with the concepts.
+struct undirected_tag { };
+
+/**
+ * The undirected template is essentially responsible for generating the types
+ * of verties and edges. Note that the definition of these types also depends,
+ * to some degree, on the underlying storage mechanisms. Specifically, these
+ * stores contribute information about the specific types of descriptors
+ * employed by the adjacency list type.
+ *
+ * @todo Unfortunately, we are actually instantiating these types over dummy
+ * stores in order to access their storage traits - basically deciding whether
+ * the descriptor will be an integer or a void ptr. There doesn't really seem
+ * to be any other way to do this since we're actually passing the stores as
+ * template template parameters - which have no type. Perhaps the new language
+ * will offer better solutions.
+ */
+template <
+        typename VertexProps,
+        typename EdgeProps,
+        typename VertexStore,
+        typename EdgeStore,
+        template <typename> class VertexEdgeStore
+    >
+struct undirected
+{
+    typedef undirected_tag tag;
+
+    typedef vertex_desc<
+            typename storage_traits<VertexStore>::descriptor_type
+        > vertex_descriptor;
+
+    typedef edge_desc<
+            typename storage_traits<EdgeStore>::descriptor_type
+        > edge_descriptor;
+
+    typedef undirected_vertex<
+            VertexProps, EdgeProps, vertex_descriptor, edge_descriptor, VertexEdgeStore
+        > vertex_type;
+
+    typedef undirected_edge<
+            VertexProps, EdgeProps, vertex_descriptor, edge_descriptor
+        > edge_type;
+};
+
+/**
+ * An undirected vertex tracks the incident edges of the given vertex. Note
+ * that the edges actually being stored are pointers to edges in the graph's
+ * edge list. The reason for this is so we don't duplicate the properties
+ * of each edge.
+ *
+ * @todo What happens if I store incident edges as a pair... The edge and the
+ * opposite end. That might be kind of interesting.
+ */
+template <
+        typename VertexProps,
+        typename EdgeProps,
+        typename VertexDesc,
+        typename EdgeDesc,
+        template <typename> class VertexEdgeStore
+    >
+class undirected_vertex
+    : public vertex<VertexProps>
+{
+public:
+    typedef VertexDesc descriptor_type;
+    typedef EdgeDesc edge_descriptor;
+    typedef typename vertex<VertexProps>::properties_type properties_type;
+private:
+    typedef VertexEdgeStore<edge_descriptor> vertex_edge_store;
+public:
+    // Edge iterator types
+    typedef typename vertex_edge_store::const_iterator incident_edge_iterator;
+    typedef typename vertex_edge_store::size_type degree_type;
+
+    undirected_vertex();
+    undirected_vertex(VertexProps const& vp);
+
+    // Connection interface.
+    void connect_to(edge_descriptor e);
+    void connect_from(edge_descriptor e);
+
+    // Disconnection interface.
+    void disconnect_to(edge_descriptor e);
+    void disconnect_from(edge_descriptor e);
+    void disconnect_all();
+
+    std::pair<incident_edge_iterator, incident_edge_iterator> incident_edges() const;
+    incident_edge_iterator begin_incident_edges() const;
+    incident_edge_iterator end_incident_edges() const;
+
+    degree_type degree() const;
+
+private:
+    vertex_edge_store _edges;
+};
+
+/**
+ * An undirected edge is an unordered pair of pointers to its endpoints. Note
+ * that because the unordered pair is instantiated over pointers, these are
+ * trivially ordered by their addresses. There is no other way available to
+ * order the vertices (i.e., by custom comparison).
+ *
+ * Note that the edge does allow construction over null endpoints, but that
+ * isn't really recommended since we don't offer any real mutators for the
+ * endpoints. For constructors that do take vertex descriptors, we might also
+ * point out that the ordering is not guaranteed after construction.
+ */
+template <
+        typename VertexProps,
+        typename EdgeProps,
+        typename VertexDesc,
+        typename EdgeDesc
+    >
+class undirected_edge
+    : public edge<EdgeProps>
+{
+public:
+    typedef EdgeDesc descriptor_type;
+    typedef typename edge<EdgeProps>::properties_type properties_type;
+
+    // This seems a little funky, but it turns out that some edge stores can
+    // leverage vertex properties for add/insert functions.
+    typedef VertexDesc vertex_descriptor;
+
+    undirected_edge();
+    undirected_edge(properties_type const& ep);
+    undirected_edge(vertex_descriptor u, vertex_descriptor v);
+    undirected_edge(vertex_descriptor u, vertex_descriptor v, properties_type const& ep);
+
+    unordered_pair<vertex_descriptor> const& ends() const;
+
+    vertex_descriptor source() const;
+    vertex_descriptor target() const;
+    vertex_descriptor opposite(vertex_descriptor v) const;
+
+private:
+    unordered_pair<vertex_descriptor> _ends;
+};
+
+// Vertex Functions
+
+#define BOOST_GRAPH_UV_PARAMS \
+    typename VP, typename EP, typename V, typename E, template <typename> class VES
+
+template <BOOST_GRAPH_UV_PARAMS>
+undirected_vertex<VP,EP,V,E,VES>::undirected_vertex()
+    : vertex<VP>()
+    , _edges()
+{ }
+
+template <BOOST_GRAPH_UV_PARAMS>
+undirected_vertex<VP,EP,V,E,VES>::undirected_vertex(VP const& vp)
+        : vertex<VP>(vp)
+        , _edges()
+    { }
+
+/**
+ * Connect this vertex to the vertex at the opposite end of this edge. Note
+ * that this vertex is neither truly the source nor target of the edge. This
+ * does not guarantee that source(e) == this.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+void
+undirected_vertex<VP,EP,V,E,VES>::connect_to(edge_descriptor e)
+{
+    _edges.add(e);
+}
+
+/**
+ * Connect this vertex to the vertex at the opposite end of the edge. Note that
+ * this does not guarantee that the target(e) == this.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+void
+undirected_vertex<VP,EP,V,E,VES>::connect_from(edge_descriptor e)
+{
+    _edges.add(e);
+}
+
+/**
+ * Locally remove the given edge that connects this vertex to another endpoint.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+void
+undirected_vertex<VP,EP,V,E,VES>::disconnect_to(edge_descriptor e)
+{
+    _edges.remove(e);
+}
+
+/**
+ * Locally remove the given edge that connects this vertex to another endpoint.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+void
+undirected_vertex<VP,EP,V,E,VES>::disconnect_from(edge_descriptor e)
+{
+    _edges.remove(e);
+}
+
+/**
+ * Locally disconnect of all the incident edges from this vertex. Note that
+ * this is really only used by the disconnect algorithm.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+void
+undirected_vertex<VP,EP,V,E,VES>::disconnect_all()
+{
+    _edges.clear();
+}
+
+/**
+ * Get an iterator range over the incident edges of this vertex.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+std::pair<
+        typename undirected_vertex<VP,EP,V,E,VES>::incident_edge_iterator,
+        typename undirected_vertex<VP,EP,V,E,VES>::incident_edge_iterator
+    >
+undirected_vertex<VP,EP,V,E,VES>::incident_edges() const
+{
+    return std::make_pair(_edges.begin(), _edges.end());
+}
+
+/**
+ * Get an iterator to the first incident edge.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+typename undirected_vertex<VP,EP,V,E,VES>::incident_edge_iterator
+undirected_vertex<VP,EP,V,E,VES>::begin_incident_edges() const
+{
+    return _edges.begin();
+}
+
+/**
+ * Get an iterator pas the end of the incident edges.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+typename undirected_vertex<VP,EP,V,E,VES>::incident_edge_iterator
+undirected_vertex<VP,EP,V,E,VES>::end_incident_edges() const
+{
+    return _edges.end();
+}
+
+/**
+ * Return the degree of this vertex. The degree of the vertex is the number
+ * of incident edges.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+typename undirected_vertex<VP,EP,V,E,VES>::degree_type
+undirected_vertex<VP,EP,V,E,VES>::degree() const
+{
+    return _edges.size();
+}
+
+/**
+ * Disconnect the given vertex from the given graph. This is not part of the
+ * public interface to this function.
+ *
+ * @todo This is actually kind of a generic algorithm.
+ */
+template <typename Graph>
+void
+disconnect(Graph& g, typename Graph::vertex_type& u, undirected_tag)
+{
+    // Undirected - iterate over each of the incident edges I and get the
+    // opposite vertex w. Remove all edges from the adjacent vertex that
+    // connect to v. Remove all edges I from E.
+
+    typedef typename Graph::vertex_type vertex;
+    typedef typename vertex::descriptor_type vertex_descriptor;
+
+    typedef typename Graph::edge_type edge;
+    typedef typename edge::descriptor_type edge_descriptor;
+    // typedef typename Graph::edge_store edge_store;
+
+    typedef typename vertex::incident_edge_iterator incidence_iterator;
+
+    // Get a descriptor for this vertex.
+    vertex_descriptor ud = g.descriptor(u);
+
+    incidence_iterator
+            i = u.begin_incident_edges(),
+            end = u.end_incident_edges();
+    for( ; i != end; ++i) {
+        // Get the vertex at the opposite end of the current edge.
+        edge_descriptor ed = *i;
+        edge& e = g.edge(ed);
+        vertex& v = g.vertex(e.opposite(ud));
+
+        // Remove the edge containing this vertex from v.
+        v.disconnect_from(ed);
+
+        // Remove this edge from the graph's edge set. Note that this is
+        // basically just discards the edge from the edge set without actually
+        // trying to disconnect it from the edges.
+        g.template Graph::edge_store::remove_edge(ed);
+    }
+    u.disconnect_all();
+}
+
+#undef BOOST_GRAPH_UV_PARAMS
+
+// Edge Functions
+
+#define BOOST_GRAPH_UE_PARAMS \
+    typename VP, typename EP, typename V, typename E
+
+template <BOOST_GRAPH_UE_PARAMS>
+undirected_edge<VP,EP,V,E>::undirected_edge()
+    : edge<EP>()
+    , _ends()
+{ }
+
+template <BOOST_GRAPH_UE_PARAMS>
+undirected_edge<VP,EP,V,E>::undirected_edge(properties_type const& ep)
+    : edge<EP>(ep)
+    , _ends()
+{ }
+
+template <BOOST_GRAPH_UE_PARAMS>
+undirected_edge<VP,EP,V,E>::undirected_edge(vertex_descriptor u, vertex_descriptor v)
+    : edge<EP>()
+    , _ends(u, v)
+{ }
+
+template <BOOST_GRAPH_UE_PARAMS>
+undirected_edge<VP,EP,V,E>::undirected_edge(vertex_descriptor u,
+                                            vertex_descriptor v,
+                                            properties_type const& ep)
+    : edge<EP>(ep)
+    , _ends(u, v)
+{ }
+
+/**
+ * Return the endpoints of the edge.
+ */
+template <BOOST_GRAPH_UE_PARAMS>
+unordered_pair<typename undirected_edge<VP,EP,V,E>::vertex_descriptor> const&
+undirected_edge<VP,EP,V,E>::ends() const
+{ return _ends; }
+
+/**
+ * Return the source of this edge. The source of an undirected edge is not
+ * necessarily the same as the way it is connected.
+ */
+template <BOOST_GRAPH_UE_PARAMS>
+typename undirected_edge<VP,EP,V,E>::vertex_descriptor
+undirected_edge<VP,EP,V,E>::source() const
+{ return _ends.first(); }
+
+/**
+ * Return the target of this edge. The source of an undirected edge is not
+ * necessarily the same as the way it is connected.
+ */
+template <BOOST_GRAPH_UE_PARAMS>
+typename undirected_edge<VP,EP,V,E>::vertex_descriptor
+undirected_edge<VP,EP,V,E>::target() const
+{ return _ends.second(); }
+
+/**
+ * Return the vertex opposite the given vertex on this edge.
+ */
+template <BOOST_GRAPH_UE_PARAMS>
+typename undirected_edge<VP,EP,V,E>::vertex_descriptor
+undirected_edge<VP,EP,V,E>::opposite(vertex_descriptor u) const
+{
+    return u == _ends.first()  ? _ends.second() : _ends.first();
+}
+
+// Operators
+
+// @todo I don't know that I like this. It might be better to build these
+// operators as functors and then typedef them into the edge type rather than
+// simply make these the default operators for the edges.
+
+/**
+ * Edges can be ordered by their end points. This is a lexicographical
+ * comparison of the vertex descriptors in the ends of the edge.
+ */
+template <BOOST_GRAPH_UE_PARAMS>
+bool
+operator<(undirected_edge<VP,EP,V,E> const& a,
+          undirected_edge<VP,EP,V,E> const& b)
+{
+    return a.ends() < b.ends();
+}
+
+/**
+ * Edges are also equality comparable by their end points. Note that this does
+ * /not/ compare the properties of vertices.
+ */
+template <BOOST_GRAPH_UE_PARAMS>
+bool
+operator==(undirected_edge<VP,EP,V,E> const& a,
+           undirected_edge<VP,EP,V,E> const& b)
+{
+    return a.ends() == b.ends();
+}
+
+#undef BOOST_GRAPH_UE_PARAMS
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vertex.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vertex.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,76 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_HPP
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * The vertex template is the base class of all vertices in the adjacency
+ * list suite. This basically provides facilities for storing the vertex
+ * properties.
+ */
+template <typename VertexProps>
+struct vertex
+{
+    typedef VertexProps properties_type;
+
+    vertex();
+    vertex(properties_type const& vp);
+
+    // Property accessors...
+    properties_type* operator->();
+    properties_type& operator*();
+    properties_type const& operator*() const;
+
+private:
+    properties_type _props;
+};
+
+template <typename VP>
+vertex<VP>::vertex()
+    : _props()
+{ }
+
+template <typename VP>
+vertex<VP>::vertex(properties_type const& vp)
+    : _props(vp)
+{ }
+
+template <typename VP>
+typename vertex<VP>::properties_type*
+vertex<VP>::operator->()
+{ return &_props; }
+
+template <typename VP>
+typename vertex<VP>::properties_type&
+vertex<VP>::operator*()
+{ return _props; }
+
+template <typename VP>
+typename vertex<VP>::properties_type const&
+vertex<VP>::operator*() const
+{ return _props; }
+
+// Operator overloads
+
+/**
+ * By default, vertices are ordered by comparing their properties. Note that
+ * this is only instantiated if it's used so you don't have to provide an
+ * ordering over vertex properties if you're not using it.
+ */
+template <typename VP>
+bool operator<(vertex<VP> const& u, vertex<VP> const& v)
+{ return *u < *v; }
+
+template <typename VP>
+bool operator>(vertex<VP> const& u, vertex<VP> const& v)
+{ return *v < *u; }
+
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/ves/vertex_edge_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/ves/vertex_edge_list.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,98 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_LIST_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_LIST_HPP
+
+#include <list>
+#include <algorithm>
+
+#include <boost/graphs/adjacency_list/ves/vertex_edge_store.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * The vertex edge list provides list-based storage for edges connected to
+ * vertices. This type supports insertions in constant time, and find and
+ * remove in linear w.r.t. to degree of the vertex.
+ *
+ * Vertex edge lists work well with both simple and multigraphs, arguably
+ * offering near-optimal performance in the average case.
+ */
+template <typename Edge>
+class vertex_edge_list
+    : public vertex_edge_store< std::list<Edge> >
+{
+    typedef vertex_edge_store< std::list<Edge> > base_type;
+public:
+    typedef Edge edge_descriptor;
+    typedef typename base_type::iterator iterator;
+    typedef typename base_type::const_iterator const_iterator;
+    typedef typename base_type::size_type size_type;
+
+    // Constructors
+    vertex_edge_list();
+
+    // Add/Find/Remove interface.
+    void add(edge_descriptor e);
+    iterator find(edge_descriptor e);
+    const_iterator find(edge_descriptor e) const;
+    void remove(edge_descriptor e);
+    void clear();
+    size_type size() const;
+};
+
+// Functions
+
+template <typename E>
+vertex_edge_list<E>::vertex_edge_list()
+    : base_type()
+{ }
+
+template <typename E>
+void
+vertex_edge_list<E>::add(edge_descriptor e)
+{
+    this->_store.push_back(e);
+}
+
+template <typename E>
+typename vertex_edge_list<E>::iterator
+vertex_edge_list<E>::find(edge_descriptor e)
+{
+    return std::find(this->_store.begin(), this->_store.end(), e);
+}
+
+template <typename E>
+typename vertex_edge_list<E>::const_iterator
+vertex_edge_list<E>::find(edge_descriptor e) const
+{
+    return std::find(this->_store.begin(), this->_store.end(), e);
+}
+
+template <typename E>
+void
+vertex_edge_list<E>::remove(edge_descriptor e)
+{
+    this->_store.erase(find(e));
+}
+
+template <typename E>
+void
+vertex_edge_list<E>::clear()
+{
+    this->_store.clear();
+}
+
+template <typename E>
+typename vertex_edge_list<E>::size_type
+vertex_edge_list<E>::size() const
+{
+    return this->_store.size();
+}
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/ves/vertex_edge_set.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/ves/vertex_edge_set.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,96 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_SET_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_SET_HPP
+
+#include <set>
+
+#include <boost/graphs/adjacency_list/ves/vertex_edge_store.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * The vertex edge set provides set-based storage for edges connected to
+ * vertices. This type supports insertions, find, and removal in logarithmic
+ * time. Vertex edge sets only work for simple graphs since they preclude the
+ * possibility of parallel edges.
+ */
+template <typename Edge>
+class vertex_edge_set
+    : public vertex_edge_store< std::set<Edge> >
+{
+    typedef vertex_edge_store< std::set<Edge> > base_type;
+public:
+    typedef Edge edge_descriptor;
+    typedef typename base_type::iterator iterator;
+    typedef typename base_type::const_iterator const_iterator;
+    typedef typename base_type::size_type size_type;
+
+    // Constructors
+    vertex_edge_set();
+
+    // Add/Find/Remove interface.
+    void add(edge_descriptor e);
+    iterator find(edge_descriptor e);
+    const_iterator find(edge_descriptor e) const;
+    void remove(edge_descriptor e);
+    void clear();
+    size_type size() const;
+};
+
+// Functions
+
+template <typename E>
+vertex_edge_set<E>::vertex_edge_set()
+    : base_type()
+{ }
+
+template <typename E>
+void
+vertex_edge_set<E>::add(edge_descriptor e)
+{
+    this->_store.insert(e);
+}
+
+template <typename E>
+typename vertex_edge_set<E>::iterator
+vertex_edge_set<E>::find(edge_descriptor e)
+{
+    return this->_store.find(e);
+}
+
+template <typename E>
+typename vertex_edge_set<E>::const_iterator
+vertex_edge_set<E>::find(edge_descriptor e) const
+{
+    return this->_store.find(e);
+}
+
+template <typename E>
+void
+vertex_edge_set<E>::remove(edge_descriptor e)
+{
+    this->_store.erase(e);
+}
+
+template <typename E>
+void
+vertex_edge_set<E>::clear()
+{
+    this->_store.clear();
+}
+
+template <typename E>
+typename vertex_edge_set<E>::size_type
+vertex_edge_set<E>::size() const
+{
+    return this->_store.size();
+}
+
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/ves/vertex_edge_store.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/ves/vertex_edge_store.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,76 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_SET_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_SET_HPP
+
+#include <set>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * The vertex store is a simple helper class that provides a number of common
+ * functions for derived types.
+ */
+template <typename Store>
+class vertex_edge_store
+{
+public:
+    typedef typename Store::iterator iterator;
+    typedef typename Store::const_iterator const_iterator;
+    typedef typename Store::size_type size_type;
+
+    // Constructors
+    vertex_edge_store();
+
+    // Iterator access.
+    iterator begin();
+    iterator end();
+
+    const_iterator begin() const;
+    const_iterator end() const;
+
+protected:
+    Store _store;
+};
+
+// Functions
+
+template <typename S>
+vertex_edge_store<S>::vertex_edge_store()
+    : _store()
+{ }
+
+template <typename S>
+typename vertex_edge_store<S>::iterator
+vertex_edge_store<S>::begin()
+{
+    return _store.begin();
+}
+
+template <typename S>
+typename vertex_edge_store<S>::iterator
+vertex_edge_store<S>::end()
+{
+    return _store.end();
+}
+
+template <typename S>
+typename vertex_edge_store<S>::const_iterator
+vertex_edge_store<S>::begin() const
+{
+    return _store.begin();
+}
+
+template <typename S>
+typename vertex_edge_store<S>::const_iterator
+vertex_edge_store<S>::end() const
+{
+    return _store.end();
+}
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/ves/vertex_edge_vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/ves/vertex_edge_vector.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,95 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_VECTOR_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_EDGE_VECTOR_HPP
+
+#include <vector>
+
+#include <boost/graphs/adjacency_list/ves/vertex_edge_store.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * The vertex edge vector provides vector-based storage for edges connected to
+ * vertices. This type supports insertions in constant time, and find and
+ * remove are supported in linear time. The remove operation will invalidate
+ * vertex edge iterators (i.e., in, out, incident, adjacency).
+ */
+template <typename Edge>
+class vertex_edge_vector
+    : public vertex_edge_store< std::vector<Edge> >
+{
+    typedef vertex_edge_store< std::vector<Edge> > base_type;
+public:
+    typedef Edge edge_descriptor;
+    typedef typename base_type::iterator iterator;
+    typedef typename base_type::const_iterator const_iterator;
+    typedef typename base_type::size_type size_type;
+
+    // Constructors
+    vertex_edge_vector();
+
+    // Add/Find/Remove interface.
+    void add(edge_descriptor e);
+    iterator find(edge_descriptor e);
+    const_iterator find(edge_descriptor e) const;
+    void remove(edge_descriptor e);
+    void clear();
+    size_type size() const;
+};
+
+// Functions
+
+template <typename E>
+vertex_edge_vector<E>::vertex_edge_vector()
+    : base_type()
+{ }
+
+template <typename E>
+void
+vertex_edge_vector<E>::add(edge_descriptor e)
+{
+    this->_store.push_back(e);
+}
+
+template <typename E>
+typename vertex_edge_vector<E>::iterator
+vertex_edge_vector<E>::find(edge_descriptor e)
+{
+    return std::find(this->_store.begin(), this->_store.end(), e);
+}
+
+template <typename E>
+typename vertex_edge_vector<E>::const_iterator
+vertex_edge_vector<E>::find(edge_descriptor e) const
+{
+    return std::find(this->_store.begin(), this->_store.end(), e);
+}
+
+template <typename E>
+void
+vertex_edge_vector<E>::remove(edge_descriptor e)
+{
+    this->_store.erase(find(e));
+}
+
+template <typename E>
+void
+vertex_edge_vector<E>::clear()
+{
+    this->_store.clear();
+}
+
+template <typename E>
+typename vertex_edge_vector<E>::size_type
+vertex_edge_vector<E>::size() const
+{
+    return this->_store.size();
+}
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/indexed_vertex_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/indexed_vertex_iterator.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,79 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_INDEXED_VERTEX_ITERATOR_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_INDEXED_VERTEX_ITERATOR_HPP
+
+#include <algorithm>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * The indexed vertex iterator provides a vertex iterator for stores whose
+ * descriptors cannot be pointers (i.e., vectors).
+ */
+template <typename Store>
+class indexed_vertex_iterator
+{
+    typedef typename Store::const_iterator iterator;
+public:
+    typedef typename Store::value_type vertex_type;
+    typedef typename vertex_type::descriptor_type 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 indexed_vertex_iterator()
+        : store(0)
+        , iter()
+    { }
+
+    inline indexed_vertex_iterator(indexed_vertex_iterator const& x)
+        : store(x.store)
+        , iter(x.iter)
+    { }
+
+    inline indexed_vertex_iterator(Store const& s, iterator const& x)
+        : store(&s)
+        , iter(x)
+    { }
+
+    inline indexed_vertex_iterator& operator++()
+    {
+        ++iter;
+        return *this;
+    }
+
+    // Support addition and subtraction as per random access iterators
+    inline indexed_vertex_iterator operator+(difference_type n) const
+    { return iter + n; }
+
+    inline indexed_vertex_iterator operator-(difference_type n) const
+    { return iter - n; }
+
+    inline difference_type operator-(indexed_vertex_iterator const& x) const
+    { return iter - x.iter; }
+
+    // The returned descriptor is simply the distance from the beginning of
+    // the underlying store to the end.
+    inline reference operator*()
+    { return std::distance(store->begin(), iter); }
+
+    inline bool operator==(indexed_vertex_iterator const& x) const
+    { return (store == x.store) && (iter == x.iter); }
+
+    inline bool operator!=(indexed_vertex_iterator const& x) const
+    { return (store == x.store) && (iter != x.iter); }
+
+    Store const* store;
+    iterator iter;
+};
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/mapped_vertex_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/mapped_vertex_iterator.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,60 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_MAPPED_VERTEX_ITERATOR_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_MAPPED_VERTEX_ITERATOR_HPP
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * 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.
+ */
+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::descriptor_type vertex_descriptor;
+
+    typedef vertex_descriptor value_type;
+    typedef vertex_descriptor reference;
+    typedef vertex_descriptor pointer;
+
+    inline mapped_vertex_iterator()
+        : iter()
+    { }
+
+    inline mapped_vertex_iterator(mapped_vertex_iterator const& x)
+        : iter(x.iter)
+    { }
+
+    inline mapped_vertex_iterator(iterator const& x)
+        : iter(x)
+    { }
+
+    inline mapped_vertex_iterator& operator++()
+    {
+        ++iter;
+        return *this;
+    }
+
+    inline reference operator*()
+    { return &const_cast<vertex_type&>(iter->second); }
+
+    inline bool operator==(mapped_vertex_iterator const& x) const
+    { return iter == x.iter; }
+
+    inline bool operator!=(mapped_vertex_iterator const& x) const
+    { return iter != x.iter; }
+
+    iterator iter;
+};
+
+} /* namespace adj_list */
+} /* namespace graph */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/value_vertex_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/value_vertex_iterator.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,67 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VALUE_VERTEX_ITERATOR_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_VALUE_VERTEX_ITERATOR_HPP
+
+#include <iterator>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * The value vertex iterator provides a vertex iterator unique associative
+ * containers and sequences that don't invalidate memory on insertions
+ * (lists).
+ *
+ * Note that this is actually a random access iterator and can be used to
+ * support trivial fill (memset) and copy (memcpy) operations.
+ */
+template <typename Store>
+class value_vertex_iterator
+{
+    typedef typename Store::const_iterator iterator;
+public:
+    typedef typename Store::value_type vertex_type;
+    typedef typename vertex_type::descriptor_type vertex_descriptor;
+
+    typedef typename iterator::iterator_category iterator_category;
+    typedef vertex_descriptor value_type;
+    typedef vertex_descriptor reference;
+    typedef vertex_descriptor pointer;
+    typedef typename iterator::difference_type difference_type;
+
+    inline value_vertex_iterator()
+        : iter()
+    { }
+
+    inline value_vertex_iterator(value_vertex_iterator const& x)
+        : iter(x.iter)
+    { }
+
+    inline value_vertex_iterator(iterator const& x)
+        : iter(x)
+    { }
+
+    inline value_vertex_iterator& operator++()
+    {
+        ++iter;
+        return *this;
+    }
+
+    inline reference operator*()
+    { return &const_cast<vertex_type&>(*iter); }
+
+    inline bool operator==(value_vertex_iterator const& x) const
+    { return iter == x.iter; }
+
+    inline bool operator!=(value_vertex_iterator const& x) const
+    { return iter != x.iter; }
+
+    iterator iter;
+};
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_list.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,238 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_LIST_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_LIST_HPP
+
+#include <list>
+
+#include <boost/graphs/adjacency_list/vs/value_vertex_iterator.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+namespace detail {
+    // Extend the notion of a vertex for list storage so that we can store each
+    // vertex's iterator the vertex. Basically, this is used to provide constant
+    // time access to correct vertex in the container. I can't think of a better
+    // way to to do this.
+    template <typename Vertex, template <typename> class Alloc>
+    struct basic_vertex_list_node
+        : Vertex
+    {
+        typedef basic_vertex_list_node<Vertex, Alloc> this_type;
+        typedef typename Vertex::properties_type properties_type;
+        typedef typename std::list<
+                this_type, Alloc<this_type>
+            >::iterator iterator;
+
+        inline basic_vertex_list_node(properties_type const& vp)
+            : Vertex(vp)
+            , iter()
+        { }
+
+        iterator iter;
+    };
+} /* namespace detail */
+
+/**
+ * The basic_vertex_list provides a list-based implementation of vertex storage
+ * for an adjacency list. List-based storage is best for graphs with
+ * unidentified vertices and requirements for fast vertex addition and deletion.
+ *
+ * Adding vertices to a list does not invalidate any vertex or edge descriptors.
+ * Removing vertices will invalidate descriptors referencing the removed
+ * vertex. All insertions and removals occur in constant time. However, getting
+ * the number of vertices is linear.
+ */
+template <
+        typename Vertex,
+        template <typename> class Alloc = std::allocator
+    >
+class basic_vertex_list
+{
+public:
+    typedef detail::basic_vertex_list_node<Vertex, Alloc> vertex_type;
+    typedef typename vertex_type::descriptor_type vertex_descriptor;
+    typedef typename vertex_type::properties_type vertex_properties;
+
+    typedef std::list<vertex_type, Alloc<vertex_type> > vertex_store;
+    typedef value_vertex_iterator<vertex_store> vertex_iterator;
+    typedef typename vertex_store::size_type vertices_size_type;
+
+    // FIXME: Clearly, this should go away during conceptization.
+    typedef hashed_property_map_tag vertex_property_map_category;
+
+    basic_vertex_list()
+        : _verts()
+    { }
+
+    // Add/remove vertices.
+    vertex_descriptor add_vertex();
+    vertex_descriptor add_vertex(vertex_properties const& vp);
+
+    // Remove vertices.
+    void remove_vertex(vertex_descriptor v);
+
+    // Number of vertices.
+    vertices_size_type num_vertices() const;
+
+    // Vertex iteration.
+    std::pair<vertex_iterator, vertex_iterator> vertices() const;
+    vertex_iterator begin_vertices() const;
+    vertex_iterator end_vertices() const;
+
+    // Vertex accessors.
+    vertex_type& vertex(vertex_descriptor);
+    vertex_type const& vertex(vertex_descriptor) const;
+    vertex_properties& properties(vertex_descriptor);
+    vertex_properties const& properties(vertex_descriptor) const;
+
+private:
+    vertex_store _verts;
+};
+
+/**
+ * Create a default specialization of the basic vertex list.
+ */
+template <typename Vertex>
+struct vertex_list : basic_vertex_list<Vertex> { };
+
+/**
+ * Add a vertex to the store with no or default properties.
+ *
+ * @complexity O(1)
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_list<V,A>::vertex_descriptor
+basic_vertex_list<V,A>::add_vertex()
+{
+    return add_vertex(vertex_properties());
+}
+
+
+/**
+ * Add a vertex to the store with the given properties. If not specified, the
+ * vertex is created with default properties. Note that vertices are not mapped
+ * or ordered so multiple, equivalent vertices can be added to the graph.
+ * This adds the vertex to the end of the list.
+ *
+ * @complexity O(1)
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_list<V,A>::vertex_descriptor
+basic_vertex_list<V,A>::add_vertex(vertex_properties const& vp)
+{
+    typename vertex_store::iterator i = _verts.insert(_verts.end(), vertex_type(vp));
+    i->iter = i;
+    return &(*i);
+}
+
+/**
+ * Remove a vertex from the store.
+ *
+ * Removing a vertex will invalidate all vertex and edge descriptors.
+ *
+ * @complexity O(|V|)
+ */
+template <typename V, template <typename> class A>
+void
+basic_vertex_list<V,A>::remove_vertex(vertex_descriptor v)
+{
+    vertex_type* vp = static_cast<vertex_type*>(v);
+    _verts.erase(vp->iter);
+}
+
+/**
+ * Return the number of vertices in the vertex store.
+ *
+ * @complexity O(V)
+ *
+ * @todo I'm not sure about the interface I'd like to build for list storage.
+ * If we don't include a lot of splice-style operations, then it's not a big
+ * deal to manage the size of this list internally.
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_list<V,A>::vertices_size_type
+basic_vertex_list<V,A>::num_vertices() const
+{
+    return _verts.size();
+}
+
+/**
+ * Return the iterator range for the graph.
+ */
+template <typename V, template <typename> class A>
+std::pair<
+    typename basic_vertex_list<V,A>::vertex_iterator,
+    typename basic_vertex_list<V,A>::vertex_iterator
+>
+basic_vertex_list<V,A>::vertices() const
+{
+    return std::make_pair(_verts.begin(), _verts.end());
+}
+
+/**
+ * Return the iterator for the begining of the vertices.
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_list<V,A>::vertex_iterator
+basic_vertex_list<V,A>::begin_vertices() const
+{
+    return _verts.begin();
+}
+
+/**
+ * Return the iterator for the begining of the vertices.
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_list<V,A>::vertex_iterator
+basic_vertex_list<V,A>::end_vertices() const
+{
+    return _verts.end();
+}
+
+/**
+ * Get access to the given vertex.
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_list<V,A>::vertex_type&
+basic_vertex_list<V,A>::vertex(vertex_descriptor v)
+{
+    return *static_cast<vertex_type*>(v.desc);
+}
+
+/**
+ * Get access to the given vertex.
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_list<V,A>::vertex_type const&
+basic_vertex_list<V,A>::vertex(vertex_descriptor v) const
+{
+    return *static_cast<vertex_type*>(v.desc);
+}
+
+/**
+ * Access the properties ofthe given vertex.
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_list<V,A>::vertex_properties&
+basic_vertex_list<V,A>::properties(vertex_descriptor v)
+{
+    return *vertex(v);
+}
+
+/**
+ * Access the properties ofthe given vertex.
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_list<V,A>::vertex_properties const&
+basic_vertex_list<V,A>::properties(vertex_descriptor v) const
+{
+    return *vertex(v);
+}
+
+} /* namespace adj_list */
+} /* namesapce graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_map.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_map.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,370 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_MAP_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_MAP_HPP
+
+#include <map>
+#include <string>
+
+#include <boost/graphs/adjacency_list/vs/mapped_vertex_iterator.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+namespace detail {
+    // Extend the notion of a vertex for set storage so that we can store each
+    // vertex's iterator with current vertex. This is used to provide constant
+    // time access to the correct position in the underliying store.
+    template <
+            typename Vertex,
+            typename Key,
+            template <typename> class Compare,
+            template <typename> class Alloc
+        >
+    class basic_vertex_map_node
+        : public Vertex
+    {
+    public:
+        typedef basic_vertex_map_node<Vertex, Key, Compare, Alloc> this_type;
+        typedef typename Vertex::properties_type properties_type;
+        typedef typename std::map<
+                Key, this_type, Compare<Key>, Alloc< std::pair<Key, this_type> >
+            >::iterator iterator;
+
+        inline basic_vertex_map_node(properties_type const& vp)
+            : Vertex(vp)
+            , iter()
+        { }
+
+        iterator iter;
+    };
+} /* namespace detail */
+
+/**
+ * The basic_vertex_map provides a list-based implementation of vertex storage
+ * for an adjacency list. List-based storage is best for graphs with
+ * unidentified vertices and requirements for fast vertex addition and deletion.
+ *
+ * This class requires that the graph's vertex properties be less than
+ * comparable since the ordering of vertices in the set is based on that
+ * implementation of the ordering. Note that the vertex type provides a built
+ * in ordering using operator<() that delegates the call to the properties.
+ *
+ * Adding vertices to a list does not invalidate any vertex or edge descriptors.
+ * Removing vertices will invalidate descriptors referencing the removed
+ * vertex. All insertions and removals occur in constant time. However, getting
+ * the number of vertices is linear.
+ *
+ * @require LessThanComparable<Vertex::properties_type>
+ */
+template <
+        typename Vertex,
+        typename Key,
+        template <typename> class Compare = std::less,
+        template <typename> class Alloc = std::allocator
+    >
+class basic_vertex_map
+{
+public:
+    typedef detail::basic_vertex_map_node<Vertex, Key, Compare, Alloc> vertex_type;
+    typedef typename vertex_type::descriptor_type vertex_descriptor;
+    typedef typename vertex_type::properties_type vertex_properties;
+
+    typedef Key key_type;
+
+    typedef std::map<
+            key_type, vertex_type, Compare<key_type>, Alloc< std::pair<key_type, vertex_type> >
+        > vertex_store;
+    typedef mapped_vertex_iterator<vertex_store> vertex_iterator;
+    typedef typename vertex_store::size_type vertices_size_type;
+
+    // FIXME: Clearly, this should go away during conceptization.
+    typedef hashed_property_map_tag vertex_property_map_category;
+
+    // Constructors
+    basic_vertex_map();
+
+    // Add a vertex.
+    vertex_descriptor add_vertex(key_type const& k);
+    vertex_descriptor add_vertex(key_type const& k, vertex_properties const& vp);
+
+    // Insert a vertex.
+    std::pair<vertex_descriptor, bool> insert_vertex(key_type const& k);
+    std::pair<vertex_descriptor, bool> insert_vertex(key_type const& k, vertex_properties const& vp);
+
+    // Remove a vertex.
+    void remove_vertex(vertex_descriptor v);
+
+    // Find a vertex
+    vertex_descriptor find_vertex(key_type const& k) const;
+
+    // Number of vertices.
+    vertices_size_type num_vertices() const;
+
+    // Vertex iteration.
+    std::pair<vertex_iterator, vertex_iterator> vertices() const;
+    vertex_iterator begin_vertices() const;
+    vertex_iterator end_vertices() const;
+
+    // Vertex accessors.
+    vertex_type& vertex(vertex_descriptor v);
+    vertex_type const& vertex(vertex_descriptor v) const;
+    vertex_descriptor descriptor(vertex_type const& v) const;
+    key_type const& key(vertex_descriptor v) const;
+
+    // Property accessors.
+    vertex_properties& properties(vertex_descriptor v);
+    vertex_properties const& properties(vertex_descriptor v) const;
+
+
+private:
+    vertex_store _verts;
+};
+
+// There isn't really a single trivial specialization of the mapped vertex
+// store since the key is a required parameter. Basically, using this type
+// requires the programmer to build different specializations of this basic
+// vertex store.
+
+/**
+ * Provide a specialization for keyed to strings.
+ */
+template <typename Vertex>
+struct string_to_vertex_map : basic_vertex_map<Vertex, std::string> { };
+
+/**
+ * Provide a specialization for integers.
+ */
+template <typename Vertex>
+struct int_to_vertex_map : basic_vertex_map<Vertex, int> { };
+
+
+/**
+ * The default constructor creates an empty vertex set.
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+basic_vertex_map<V,K,C,A>::basic_vertex_map()
+    : _verts()
+{ }
+
+/**
+ * Add a vertex to the store with the given key. If the key is already mapped
+ * to a vertex, then do nothing. Return a descriptor to either the new or
+ * existing vertex.
+ *
+ * @complexity O(log(V))
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+typename basic_vertex_map<V,K,C,A>::vertex_descriptor
+basic_vertex_map<V,K,C,A>::add_vertex(const K& k)
+{
+    return insert_vertex(k).first;
+}
+
+
+/**
+ * Add a vertex to the store with the key and properties. If the key is mapped
+ * to a vertex, do nothing. Return a descriptor to the existing or new vertex.
+ *
+ * @complexity O(log(V))
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+typename basic_vertex_map<V,K,C,A>::vertex_descriptor
+basic_vertex_map<V,K,C,A>::add_vertex(const K& k, vertex_properties const& vp)
+{
+    return insert_vertex(k, vp).first;
+}
+
+/**
+ * Add a vertex to the store with the given key. Return a pair that includes
+ * a descriptor for the inserted vertex and a boolean value that indicates
+ * whether or not the vertex was actually inserted.
+ *
+ * @complexity O(log(V))
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+std::pair<typename basic_vertex_map<V,K,C,A>::vertex_descriptor, bool>
+basic_vertex_map<V,K,C,A>::insert_vertex(key_type const& k)
+{
+    return insert_vertex(k, vertex_properties());
+}
+
+
+/**
+ * Add a vertex to the store with the given properties. If not specified, the
+ * vertex is created with default properties and return a descriptor to the
+ * inserted vertex. If the vertex exists, the second element of the returned
+ * pair is false.
+ *
+ * @complexity O(log(V))
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+std::pair<typename basic_vertex_map<V,K,C,A>::vertex_descriptor, bool>
+basic_vertex_map<V,K,C,A>::insert_vertex(key_type const& k, vertex_properties const& vp)
+{
+    std::pair<vertex_descriptor, bool> ret;
+    std::pair<typename vertex_store::iterator, bool> ins =
+            _verts.insert(make_pair(k, vertex_type(vp)));
+    if(ins.second) {
+        // Yikes... so dirty. Normally, we can't modify an object via its
+        // iterator since that would indicate a change to the key. However,
+        // the key is based on the properties of the vertex, not the part of
+        // the object that we're going to change.
+        vertex_type& v = ins.first->second;
+        v.iter = ins.first;
+        ret.first = &v;
+    }
+    else {
+        ret.first = &(ins.first->second);
+    }
+    ret.second = ins.second;
+
+    return ret;
+}
+
+/**
+ * Find a vertex given a key. If the key does not exist, return an invalid
+ * descriptor.
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+typename basic_vertex_map<V,K,C,A>::vertex_descriptor
+basic_vertex_map<V,K,C,A>::find_vertex(key_type const& k) const
+{
+    vertex_descriptor ret;
+    typename vertex_store::const_iterator iter = _verts.find(k);
+    if(iter != _verts.end()) {
+        // Because the function is const, the resulting vertex should also be
+        // const. Unfortunately, this isn't really going to work for me.
+        vertex_type& v = const_cast<vertex_type&>(iter->second);
+        ret = &v;
+    }
+    return ret;
+}
+
+/**
+ * Remove a vertex from the store.
+ *
+ * Removing a vertex will invalidate all vertex and edge descriptors.
+ *
+ * @complexity O(|V|)
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+void
+basic_vertex_map<V,K,C,A>::remove_vertex(vertex_descriptor v)
+{
+    vertex_type* vp = static_cast<vertex_type*>(v);
+    _verts.erase(vp->iter);
+}
+
+/**
+ * Return the number of vertices in the vertex store.
+ *
+ * @complexity O(V)
+ *
+ * @todo I'm not sure about the interface I'd like to build for list storage.
+ * If we don't include a lot of splice-style operations, then it's not a big
+ * deal to manage the size of this list internally.
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+typename basic_vertex_map<V,K,C,A>::vertices_size_type
+basic_vertex_map<V,K,C,A>::num_vertices() const
+{
+    return _verts.size();
+}
+
+/**
+ * Return the iterator range for the graph.
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+std::pair<
+    typename basic_vertex_map<V,K,C,A>::vertex_iterator,
+    typename basic_vertex_map<V,K,C,A>::vertex_iterator
+>
+basic_vertex_map<V,K,C,A>::vertices() const
+{
+    return std::make_pair(_verts.begin(), _verts.end());
+}
+
+/**
+ * Get a vertex iterator to the beginning iterator of the vertices.
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+typename basic_vertex_map<V,K,C,A>::vertex_iterator
+basic_vertex_map<V,K,C,A>::begin_vertices() const
+{ return _verts.begin(); }
+
+/**
+ * Get a vertex iterator to an iterator past the end of the vertices.
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+typename basic_vertex_map<V,K,C,A>::vertex_iterator
+basic_vertex_map<V,K,C,A>::end_vertices() const
+{ return _verts.end(); }
+
+/**
+ * Get access to the given vertex.
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+typename basic_vertex_map<V,K,C,A>::vertex_type&
+basic_vertex_map<V,K,C,A>::vertex(vertex_descriptor v)
+{
+    return *static_cast<vertex_type*>(v.desc);
+}
+
+/**
+ * Get access to the given vertex.
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+typename basic_vertex_map<V,K,C,A>::vertex_type const&
+basic_vertex_map<V,K,C,A>::vertex(vertex_descriptor v) const
+{
+    return *static_cast<vertex_type*>(v.desc);
+}
+
+/**
+ * Return a descriptor for the given vertex.
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+typename basic_vertex_map<V,K,C,A>::vertex_descriptor
+basic_vertex_map<V,K,C,A>::descriptor(vertex_type const& v) const
+{
+    return &const_cast<vertex_type&>(v);
+}
+
+/**
+ * Get the key of a vertex descriptor.
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+typename basic_vertex_map<V,K,C,A>::key_type const&
+basic_vertex_map<V,K,C,A>::key(vertex_descriptor v) const
+{
+    vertex_type& vert = *static_cast<vertex_type*>(v.desc);
+    return vert.iter->first;
+}
+
+
+/**
+ * Get the properties of the given vertex.
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+typename basic_vertex_map<V,K,C,A>::vertex_properties&
+basic_vertex_map<V,K,C,A>::properties(vertex_descriptor v)
+{
+    return *vertex(v);
+}
+
+/**
+ * Get the properties of the given vertex.
+ */
+template <typename V, typename K, template <typename> class C, template <typename> class A>
+typename basic_vertex_map<V,K,C,A>::vertex_properties const&
+basic_vertex_map<V,K,C,A>::properties(vertex_descriptor v) const
+{
+    return *vertex(v);
+}
+
+} /* namespace adj_list */
+} /* namesapce graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_multimap.hpp
==============================================================================

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_multiset.hpp
==============================================================================

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_set.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_set.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,332 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_SET_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_SET_HPP
+
+#include <set>
+#include <tr1/unordered_map>
+
+#include <boost/graphs/properties.hpp>
+#include <boost/graphs/adjacency_list/vs/value_vertex_iterator.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+namespace detail {
+    // Extend the notion of a vertex for set storage so that we can store each
+    // vertex's iterator with current vertex. This is used to provide constant
+    // time access to the correct position in the underliying store.
+    template <
+            typename Vertex,
+            template <typename> class Compare,
+            template <typename> class Alloc>
+    class basic_vertex_set_node
+        : public Vertex
+    {
+    public:
+        typedef basic_vertex_set_node<Vertex, Compare, Alloc> this_type;
+        typedef typename Vertex::properties_type properties_type;
+
+        typedef typename std::set<
+                this_type, Compare<this_type>, Alloc<this_type>
+            >::iterator iterator;
+
+        inline basic_vertex_set_node(properties_type const& vp)
+            : Vertex(vp)
+            , iter()
+        { }
+
+        iterator iter;
+    };
+
+} /* namespace detail */
+
+/**
+ * The basic_vertex_set provides a list-based implementation of vertex storage
+ * for an adjacency list. List-based storage is best for graphs with
+ * unidentified vertices and requirements for fast vertex addition and deletion.
+ *
+ * This class requires that the graph's vertex properties be less than
+ * comparable since the ordering of vertices in the set is based on that
+ * implementation of the ordering. Note that the vertex type provides a built
+ * in ordering using operator<() that delegates the call to the properties.
+ *
+ * Adding vertices to a list does not invalidate any vertex or edge descriptors.
+ * Removing vertices will invalidate descriptors referencing the removed
+ * vertex. All insertions and removals occur in constant time. However, getting
+ * the number of vertices is linear.
+ *
+ * @require LessThanComparable<Vertex::properties_type>
+ */
+template <
+        typename Vertex,
+        template <typename> class Compare = std::less,
+        template <typename> class Alloc = std::allocator
+    >
+class basic_vertex_set
+{
+public:
+    typedef detail::basic_vertex_set_node<Vertex, Compare, Alloc> vertex_type;
+    typedef typename vertex_type::descriptor_type vertex_descriptor;
+    typedef typename vertex_type::properties_type vertex_properties;
+
+    typedef std::set<
+            vertex_type, Compare<vertex_type>, Alloc<vertex_type>
+        > vertex_store;
+    typedef value_vertex_iterator<vertex_store> vertex_iterator;
+    typedef typename vertex_store::size_type vertices_size_type;
+
+    // This is kind of hack, but we need some way of communicating a preference
+    // of the favored underlying property store to higher level features.
+    // FIXME: Clearly, this should go away during conceptization.
+    typedef hashed_property_map_tag vertex_property_map_category;
+
+    // Constructors
+    basic_vertex_set();
+
+    // Add vertices. Note that you can't add without properties.
+    vertex_descriptor add_vertex(vertex_properties const& vp);
+    std::pair<vertex_descriptor, bool> insert_vertex(vertex_properties const& vp);
+
+    // Remove vertices.
+    void remove_vertex(vertex_descriptor v);
+    void remove_vertex(vertex_properties const& v);
+
+    // Find a vertex based on its properties.
+    vertex_descriptor find_vertex(vertex_properties const& vp) const;
+
+    // Number of vertices.
+    vertices_size_type num_vertices() const;
+
+    // Vertex iteration.
+    std::pair<vertex_iterator, vertex_iterator> vertices() const;
+    vertex_iterator begin_vertices() const;
+    vertex_iterator end_vertices() const;
+
+    // Vertex accessors.
+    vertex_type& vertex(vertex_descriptor);
+    vertex_type const& vertex(vertex_descriptor) const;
+    vertex_properties& properties(vertex_descriptor);
+    vertex_properties const& properties(vertex_descriptor) const;
+
+private:
+    vertex_store _verts;
+};
+
+
+/**
+ * The default implementation of a vertex set is given here. Specialized
+ * versions of the basic vertex set can be generated using inheritance like
+ * this. This version fixes the default comparator and allocator of the vertex
+ * set to the common defaults.
+ */
+template <typename Vertex>
+struct vertex_set : basic_vertex_set<Vertex> { };
+
+// Some examples of specialized (curried) variants of the basic vertex set.
+// These provide specific orderings. Note that the "less set" is actually the
+// same as the default vertex set.
+template <typename Vertex>
+struct min_vertex_set : public basic_vertex_set<Vertex, std::less> { };
+
+template <typename Vertex>
+struct max_vertex_set : public basic_vertex_set<Vertex, std::greater> { };
+
+
+#define BOOST_GRAPH_VS_PARAMS \
+    typename V, template <typename> class C, template <typename> class A
+
+/**
+ * The default constructor creates an empty vertex set.
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+basic_vertex_set<V,C,A>::basic_vertex_set()
+    : _verts()
+{ }
+
+/**
+ * Add a vertex to the store with the given properties. If not specified, the
+ * vertex is created with default properties. Note that vertices are not mapped
+ * or ordered so multiple, equivalent vertices can be added to the graph.
+ *
+ * @complexity O(log(V))
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+typename basic_vertex_set<V,C,A>::vertex_descriptor
+basic_vertex_set<V,C,A>::add_vertex(vertex_properties const& vp)
+{
+    return insert_vertex(vp).first;
+}
+
+/**
+ * Add a vertex to the store with the given properties. If not specified, the
+ * vertex is created with default properties and return a descriptor to the
+ * inserted vertex. If the vertex exists, the second element of the returned
+ * pair is false.
+ *
+ * @complexity O(log(V))
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+std::pair<typename basic_vertex_set<V,C,A>::vertex_descriptor, bool>
+basic_vertex_set<V,C,A>::insert_vertex(vertex_properties const& vp)
+{
+    std::pair<vertex_descriptor, bool> ret;
+    std::pair<typename vertex_store::iterator, bool> ins =
+            _verts.insert(vertex_type(vp));
+    if(ins.second) {
+        // Yikes... so dirty. Normally, we can't modify an object via its
+        // iterator since that would indicate a change to the key. However,
+        // the key is based on the properties of the vertex, not the part of
+        // the object that we're going to change.
+        vertex_type& v = const_cast<vertex_type&>(*(ins.first));
+        v.iter = ins.first;
+        ret.first = &v;
+    }
+    else {
+        ret.first = &const_cast<vertex_type&>(*ins.first);
+    }
+    ret.second = ins.second;
+
+    return ret;
+}
+
+/**
+ * Remove a vertex from the store.
+ *
+ * @complexity O(log(V))
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+void
+basic_vertex_set<V,C,A>::remove_vertex(vertex_descriptor v)
+{
+    vertex_type* vp = static_cast<vertex_type*>(v.desc);
+    _verts.erase(vp->iter);
+}
+
+/**
+ * Remove the vertex identified by the given properties from the store.
+ *
+ * @complexity O(log(V))
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+void
+basic_vertex_set<V,C,A>::remove_vertex(vertex_properties const& vp)
+{
+    remove_vertex(find(vp));
+}
+
+/**
+ * Find a vertex by its properties.
+ *
+ * @complexity O(log(V))
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+typename basic_vertex_set<V,C,A>::vertex_descriptor
+basic_vertex_set<V,C,A>::find_vertex(vertex_properties const& vp) const
+{
+    // This is a little gross... We have to tempoararily construct an empty
+    // vertex with the given properties in order for the find operations to
+    // work.
+    vertex_descriptor ret;
+    typename vertex_store::iterator iter = _verts.find(vertex_type(vp));
+    if(iter != _verts.end()) {
+        ret = &const_cast<vertex_type&>(*iter);
+    }
+    return ret;
+}
+
+/**
+ * Return the number of vertices in the vertex store.
+ *
+ * @complexity O(V)
+ *
+ * @todo I'm not sure about the interface I'd like to build for list storage.
+ * If we don't include a lot of splice-style operations, then it's not a big
+ * deal to manage the size of this list internally.
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+typename basic_vertex_set<V,C,A>::vertices_size_type
+basic_vertex_set<V,C,A>::num_vertices() const
+{
+    return _verts.size();
+}
+
+/**
+ * Return the iterator range for the graph.
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+std::pair<
+    typename basic_vertex_set<V,C,A>::vertex_iterator,
+    typename basic_vertex_set<V,C,A>::vertex_iterator
+>
+basic_vertex_set<V,C,A>::vertices() const
+{
+    return std::make_pair(_verts.begin(), _verts.end());
+}
+
+/**
+ * Get a vertex iterator to the beginning iterator of the vertices.
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+typename basic_vertex_set<V,C,A>::vertex_iterator
+basic_vertex_set<V,C,A>::begin_vertices() const
+{
+    return _verts.begin();
+}
+
+/**
+ * Get a vertex iterator to an iterator past the end of the vertices.
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+typename basic_vertex_set<V,C,A>::vertex_iterator
+basic_vertex_set<V,C,A>::end_vertices() const
+{
+    return _verts.end();
+}
+
+/**
+ * Get access to the given vertex.
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+typename basic_vertex_set<V,C,A>::vertex_type&
+basic_vertex_set<V,C,A>::vertex(vertex_descriptor v)
+{
+    return *static_cast<vertex_type*>(v.desc);
+}
+
+/**
+ * Get access to the given vertex.
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+typename basic_vertex_set<V,C,A>::vertex_type const&
+basic_vertex_set<V,C,A>::vertex(vertex_descriptor v) const
+{
+    return *static_cast<vertex_type*>(v.desc);
+}
+
+/**
+ * Access the properties of the given vertex.
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+typename basic_vertex_set<V,C,A>::vertex_properties&
+basic_vertex_set<V,C,A>::properties(vertex_descriptor v)
+{
+    return *vertex(v);
+}
+
+/**
+ * Access the properties of the given vertex.
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+typename basic_vertex_set<V,C,A>::vertex_properties const&
+basic_vertex_set<V,C,A>::properties(vertex_descriptor v) const
+{
+    return *vertex(v);
+}
+
+} /* namespace adj_list */
+
+} /* namesapce graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/vertex_vector.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,225 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_VECTOR_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_VECTOR_HPP
+
+#include <vector>
+
+#include <boost/graphs/properties.hpp>
+#include <boost/graphs/adjacency_list/vs/indexed_vertex_iterator.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * The vertex_vector template implements veretex storage for adjacency lists
+ * as a vector. This essentially provides a heavily constrained interface
+ * to the underlying vector. Note that many operations normally supported by
+ * a vector are not allowed with graphs.
+ *
+ * Adding vertices does not invalidate descriptors, but may result in the
+ * reallocation of the underlying store. However, removing vertices could
+ * corrupt the entire graph (since indices are adjusted). As a result, this
+ * store type does not provide remove operations.
+ */
+template <
+        typename Vertex,
+        template <typename> class Alloc
+    >
+class basic_vertex_vector
+{
+public:
+    typedef Vertex vertex_type;
+    typedef typename vertex_type::descriptor_type vertex_descriptor;
+    typedef typename vertex_type::properties_type vertex_properties;
+
+    typedef std::vector<vertex_type, Alloc<vertex_type> > vertex_store;
+    typedef indexed_vertex_iterator<vertex_store> vertex_iterator;
+    typedef typename vertex_store::size_type vertices_size_type;
+
+    // FIXME: This is old school.
+    typedef indexed_property_map_tag vertex_property_map_category;
+
+    // Constructors
+    basic_vertex_vector();
+
+    // Add/remove vertex.
+    vertex_descriptor add_vertex();
+    vertex_descriptor add_vertex(vertex_properties const& vp);
+
+    // Number of vertices.
+    vertices_size_type num_vertices() const;
+
+    // Vertex iteration.
+    std::pair<vertex_iterator, vertex_iterator> vertices() const;
+    vertex_iterator begin_vertices() const;
+    vertex_iterator end_vertices() const;
+
+    // Vertex/vertex property accessors.
+    vertex_type& vertex(vertex_descriptor v);
+    vertex_type const& vertex(vertex_descriptor v) const;
+    vertex_properties& properties(vertex_descriptor);
+    vertex_properties const& properties(vertex_descriptor) const;
+
+private:
+    vertex_store _verts;
+};
+
+/**
+ * Specialization of the storage traits to redefine the descriptor. Vectors for
+ * any store type must use their indices as descriptors since the underlying
+ * storage memory can be reallocated or shiftetd on inserts and removals.
+ *
+ * @todo For some reason, this doesn't work as a catch all for derived types.
+ * How will this work if we use template aliases instead of inheritance? This
+ * doesn't seem to be a problem for non-vectors since the default template
+ * catches all aspects of it.
+ */
+template <typename Vertex, template <typename> class Alloc>
+struct storage_traits< basic_vertex_vector<Vertex, Alloc> >
+{
+    typedef std::size_t descriptor_type;
+};
+
+/**
+ * The default specialization of a vector store.
+ */
+template <typename Vertex>
+struct vertex_vector : basic_vertex_vector<Vertex, std::allocator> { };
+
+/**
+ * Apparently, we have to provide a specific partial specialization for each
+ * specialized storage. Is this right? Is it wrong? Is the compiler broken?
+ */
+template <typename Vertex>
+struct storage_traits< vertex_vector<Vertex> >
+{
+    typedef std::size_t descriptor_type;
+};
+
+// Functions
+
+template <typename V, template <typename> class A>
+basic_vertex_vector<V,A>::basic_vertex_vector()
+    : _verts()
+{ }
+
+/**
+ * Add a vertex to the store with no or default properties, returning the
+ * the descriptor to the added vertex. Adding a vertex does not invalidate
+ * any vertices or edges.
+ *
+ * @complexity O(1) amortized
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_vector<V,A>::vertex_descriptor
+basic_vertex_vector<V,A>::add_vertex()
+{
+    return add_vertex(vertex_properties());
+}
+
+/**
+ * Add a vertex to the store with the given properties. Adding a vertex does
+ * not invalidate any other descriptors.
+ *
+ * @complexity O(1) amortized
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_vector<V,A>::vertex_descriptor
+basic_vertex_vector<V,A>::add_vertex(vertex_properties const& vp)
+{
+    // Basically, just push the vertex to the back and return its index.
+    _verts.push_back(vertex_type(vp));
+    return _verts.size() - 1;
+}
+
+/**
+ * Return the number of vertices in the vertex store.
+ *
+ * @complexity constant
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_vector<V,A>::vertices_size_type
+basic_vertex_vector<V,A>::num_vertices() const
+{
+    return _verts.size();
+}
+
+/**
+ * Return the iterator range for the graph.
+ */
+template <typename V, template <typename> class A>
+std::pair<
+    typename basic_vertex_vector<V,A>::vertex_iterator,
+    typename basic_vertex_vector<V,A>::vertex_iterator
+>
+basic_vertex_vector<V,A>::vertices() const
+{
+    return std::make_pair(begin_vertices(), end_vertices());
+}
+
+/**
+ * Get an iterator to the beginning of the vertices.
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_vector<V,A>::vertex_iterator
+basic_vertex_vector<V,A>::begin_vertices() const
+{
+    return vertex_iterator(_verts, _verts.begin());
+}
+
+/**
+ * Get an iterator past the end of the vertices.
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_vector<V,A>::vertex_iterator
+basic_vertex_vector<V,A>::end_vertices() const
+{
+    return vertex_iterator(_verts, _verts.end());
+}
+
+/**
+ * Get access to the underlying vertex.
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_vector<V,A>::vertex_type&
+basic_vertex_vector<V,A>::vertex(vertex_descriptor v)
+{
+    return _verts[v.desc];
+}
+
+/**
+ * Get access to the underlying vertex.
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_vector<V,A>::vertex_type const&
+basic_vertex_vector<V,A>::vertex(vertex_descriptor v) const
+{
+    return _verts[v.desc];
+}
+
+/**
+ * Get access to the properties of the given vertex.
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_vector<V,A>::vertex_properties&
+basic_vertex_vector<V,A>::properties(vertex_descriptor v)
+{
+    return *vertex(v);
+}
+
+/**
+ * Get access to the properties of the given vertex.
+ */
+template <typename V, template <typename> class A>
+typename basic_vertex_vector<V,A>::vertex_properties const&
+basic_vertex_vector<V,A>::properties(vertex_descriptor v) const
+{
+    return *vertex(v);
+}
+
+} /* namespace adj_list */
+} /* namesapce graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_matrix/adjacency_matrix.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_matrix/adjacency_matrix.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,22 @@
+
+#ifndef BOOST_GRAPH_ADJACENCY_MATRIX_HPP
+#define BOOST_GRAPH_ADJACENCY_MATRIX_HPP
+
+namespace boost {
+namespace graph {
+
+/**
+ * The adjacency_matrix...
+ */
+template <
+    typename VertexProperty,
+    typename EdgeProperty
+>
+class adjacency_matrix
+{
+};
+
+} /* namesapce graph */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/breadth_first_search.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/breadth_first_search.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,42 @@
+
+#ifndef BOOST_GRAPHS_BREADTH_FIRST_SEARCH_HPP
+#define BOOST_GRAPHS_BREADTH_FIRST_SEARCH_HPP
+
+#include <boost/graphs/properties.hpp>
+
+namespace boost {
+namespace graphs {
+
+template <typename Graph>
+void breadth_first_search(const Graph& g,
+                          typename Graph::vertex_descriptor start)
+{
+
+}
+
+/**
+ * Run a BFS on the graph starting at the given start vertex and stopping when
+ * then end vertex is found (or visiting all vertices if never found).
+ */
+template <typename Graph>
+void breadth_first_search(const Graph& g,
+                          typename Graph::vertex_descriptor start,
+                          typename Graph::vertex_descriptor end)
+{
+}
+
+/**
+ * Run a BFS on the graph starting at an arbitrary vertex (actually the first
+ * vertex).
+ */
+template <typename Graph>
+void breadth_first_search(const Graph& g)
+{
+    breadth_first_search(g, *g.begin_vertices());
+}
+
+} /* namespace graphs */
+} /* namespace boost */
+
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/incidence_list/incidence_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/incidence_list/incidence_list.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,22 @@
+
+#ifndef BOOST_GRAPH_INCIDENCE_LIST_HPP
+#define BOOST_GRAPH_INCIDENCE_LIST_HPP
+
+namespace boost {
+namespace graph {
+
+/**
+ * The incidecence_list
+ */
+template <
+    typename VertexProperty,
+    typename EdgeProperty
+>
+class incidence_list
+{
+};
+
+} /* namesapce graph */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/incidence_matrix/incidence_matrix.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/incidence_matrix/incidence_matrix.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,22 @@
+
+#ifndef BOOST_GRAPH_INCIDENCE_MATRIX_HPP
+#define BOOST_GRAPH_INCIDENCE_MATRIX_HPP
+
+namespace boost {
+namespace graph {
+
+/**
+ * The incidence_matrix...
+ */
+template <
+    typename VertexProperty,
+    typename EdgeProperty
+>
+class incidence_matrix
+{
+};
+
+} /* namesapce graph */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/properties.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/properties.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,146 @@
+
+#ifndef BOOST_GRAPHS_PROPERTIES_HPP
+#define BOOST_GRAPHS_PROPERTIES_HPP
+
+#include <vector>
+#include <tr1/unordered_map>
+
+#include <boost/type_traits.hpp>
+#include <boost/mpl/if.hpp>
+
+#include <boost/graphs/property_map/simple_properties.hpp>
+#include <boost/graphs/property_map/bundled_properties.hpp>
+#include <boost/graphs/property_map/hashed_properties.hpp>
+#include <boost/graphs/property_map/indexed_properties.hpp>
+
+namespace boost {
+namespace graphs {
+
+/**
+ * Default color types for this library.
+ */
+enum color {
+    white_color,
+    gray_color,
+    black_color,
+    red_color,
+    green_color,
+    blue_color
+};
+
+/**
+ * A traits class for colors. Specialize this if, for some reason, you ever
+ * plan to specialize the notion of colors - which may be possible.
+ *
+ * @todo Obviously, this will be conceptized. See below.
+ */
+template <typename Color>
+struct color_traits
+{
+    static color white()   { return white_color; }
+    static color gray()    { return gray_color; }
+    static color black()   { return black_color; }
+    static color red()     { return red_color; }
+    static color green()   { return green_color; }
+    static color blue()    { return blue_color; }
+};
+
+// All the fun of exterior properties... We need a mechanism that determines
+// the underlying mapping type of exterior properties. For vector-based stores
+// we can simply map each vertex to its corresponding element in another vector.
+// For non-vector-based stores, it's easier to use a hash of the descriptor.
+
+// For now, these tags are used to actually decide the underlying implementation
+// of the property map.
+struct indexed_property_map_tag { };
+struct hashed_property_map_tag { };
+
+template <typename Tag, typename Iterator, typename Property>
+struct exterior_property
+{
+    typedef typename mpl::if_<
+            is_same<Tag, hashed_property_map_tag>,          // predicate
+            hashed_property_container<Iterator, Property>,  // on true
+            indexed_property_container<Iterator, Property>  // on false
+        >::type container_type;
+
+    typedef typename mpl::if_<
+            is_same<Tag, hashed_property_map_tag>,      // predicate
+            hashed_property_map<Iterator, Property>,    // on true
+            indexed_property_map<Iterator, Property>    // on false
+        >::type map_type;
+};
+
+template <typename Graph, typename Property>
+struct exterior_vertex_property
+{
+    typedef exterior_property<
+            typename Graph::vertex_property_map_category,
+            typename Graph::vertex_iterator,
+            Property
+                    > base_type;
+            typedef typename base_type::container_type container_type;
+            typedef typename base_type::map_type map_type;};
+
+template <typename Graph, typename Property>
+struct exterior_edge_property
+{
+    typedef exterior_property<
+            typename Graph::edge_property_map_category,
+            typename Graph::edge_iterator,
+            Property
+        > base_type;
+    typedef typename base_type::container_type container_type;
+    typedef typename base_type::map_type map_type;
+
+};
+
+
+// Interior properties aer also a great deal of fun.
+
+template <typename Graph, typename Property = typename Graph::vertex_properties>
+struct interior_vertex_property
+{
+    typedef simple_property_map<
+            Graph,
+            typename Graph::vertex_descriptor,
+            typename Graph::vertex_properties
+        > map_type;
+};
+
+template <typename Graph, typename Bundle, typename Property>
+struct interior_vertex_property<Graph, Property Bundle::*>
+{
+    typedef bundled_property_map<
+            Graph,
+            typename Graph::vertex_descriptor,
+            Bundle,
+            Property
+        > map_type;
+};
+
+template <typename Graph, typename Property = typename Graph::vertex_properties>
+struct interior_edge_property
+{
+    typedef simple_property_map<
+            Graph,
+            typename Graph::edge_descriptor,
+            typename Graph::edge_properties
+        > map_type;
+};
+
+template <typename Graph, typename Bundle, typename Property>
+struct interior_edge_property<Graph, Property Bundle::*>
+{
+    typedef bundled_property_map<
+            Graph,
+            typename Graph::edge_descriptor,
+            Bundle,
+            Property
+        > map_type;
+};
+
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/property_map/bundled_properties.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/property_map/bundled_properties.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,69 @@
+
+#ifndef BOOST_GRAPHS_PROPERTY_MAP_BUNDLED_PROPERTIES_HPP
+#define BOOST_GRAPHS_PROPERTY_MAP_BUNDLED_PROPERTIES_HPP
+
+namespace boost {
+namespace graphs {
+
+/**
+ * A simple property map provides get/put functions for non-bundled or simple
+ * vertex and edge properties. This is not called "simple" because it is
+ * trivially implemented but because it return the properties assigned to the
+ * vertex or edge (depending on the descriptor) without any indirection. To
+ * build property maps over members or a structured (or bundled) property,
+ * use the bundled property map.
+ */
+template <typename Graph, typename Descriptor, typename Bundle, typename Property>
+struct bundled_property_map
+{
+    typedef Descriptor key_type;
+    typedef Property property_type;
+
+    inline bundled_property_map(Graph& g, Property Bundle::* mem)
+        : graph(g)
+        , member(mem)
+    { }
+
+    inline bundled_property_map(bundled_property_map const& x)
+        : graph(x.g)
+        , member(x.mem)
+    { }
+
+    inline Bundle const& bundle(key_type const& k) const
+    { return graph.properties(k); }
+
+    inline Bundle& bundle(key_type const& k)
+    { return graph.properties(k); }
+
+
+    inline Property const& get(key_type const& k) const
+    { return bundle(k).*member; }
+
+    inline void put(key_type const& k, Property const& v)
+    { bundle(k).*member = v; }
+
+    Graph& graph;
+    Property Bundle::* member;
+};
+
+template <typename G, typename D, typename B, typename P>
+typename bundled_property_map<G,D,B,P>::property_type const&
+get(bundled_property_map<G,D,B,P> const& pm,
+    typename bundled_property_map<G,D,B,P>::key_type const& k)
+{
+    return pm.get(k);
+}
+
+template <typename G, typename D, typename B, typename P>
+void
+put(bundled_property_map<G,D,B,P>& pm,
+    typename bundled_property_map<G,D,B,P>::key_type const& k,
+    typename bundled_property_map<G,D,B,P>::property_type const& v)
+{
+    pm.put(k, v);
+}
+
+} /* namesapce graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/property_map/hashed_properties.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/property_map/hashed_properties.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,126 @@
+
+#ifndef BOOST_GRAPHS_PROPERTY_MAP_HASHED_PROPERTIES_HPP
+#define BOOST_GRAPHS_PROPERTY_MAP_HASHED_PROPERTIES_HPP
+
+#include <tr1/unordered_map>
+
+#include <boost/functional/hash.hpp>
+
+namespace boost {
+namespace graphs {
+
+namespace detail {
+
+template <typename Iterator, typename Property>
+struct make_pair_iterator
+{
+    typedef typename Iterator::iterator_category iterator_category;
+    typedef typename Iterator::difference_type difference_type;
+    typedef std::pair<typename Iterator::value_type, Property> value_type;
+    typedef value_type reference;
+    typedef value_type pointer;
+
+    make_pair_iterator(Iterator i)
+        : iter(i)
+    { }
+
+    make_pair_iterator& operator++()
+    { ++iter; return *this; }
+
+    reference operator*()
+    { return make_pair(*iter, Property()); }
+
+    bool operator==(make_pair_iterator const& x) const
+    { return iter == x.iter; }
+
+    bool operator!=(make_pair_iterator const& x) const
+    { return iter != x.iter; }
+
+    Iterator iter;
+};
+
+} /* namespace detail */
+
+
+/**
+ * A simple wrapper around an unordered map, this is used to map descriptors
+ * to arbitrary property values. Note that the property type must be default
+ * constructible.
+ *
+ * This may seem a little odd because we're passing an iterator and not the key
+ * type. However, the key type is always the iterator's value type.
+ */
+template <typename Iterator, typename Property>
+class hashed_property_container
+{
+    typedef detail::make_pair_iterator<Iterator, Property> pair_iterator;
+public:
+    typedef Property value_type;
+    typedef typename Iterator::value_type key_type;
+    typedef std::tr1::unordered_map<key_type, value_type, hash<key_type> > container_type;
+
+
+    // Construct the container over n elements with the given default property
+    // value. If a number of buckets is explicitly given (and is not 0), then
+    // construct the object with b buckets. Otherwise, construct with n buckets.
+    // The default behavior will prevent rehashing during construction.
+    inline hashed_property_container(Iterator f, Iterator l)
+        : _map(pair_iterator(f), pair_iterator(l))
+    { }
+
+    inline hashed_property_container(std::pair<Iterator, Iterator> rng)
+        : _map(pair_iterator(rng.first), pair_iterator(rng.second))
+    { }
+
+    // Get the property associated with the key k.
+    inline value_type& operator[](key_type const& k)
+    { return _map[k]; }
+
+private:
+    container_type _map;
+};
+
+/**
+ * The corresponding property map implements a lightweight, regular accessor
+ * to a hashed property container.
+ */
+template <typename Iterator, typename Property>
+class hashed_property_map
+{
+    typedef hashed_property_container<Iterator, Property> container_type;
+public:
+    typedef typename container_type::value_type property_type;
+    typedef typename container_type::key_type key_type;
+
+    hashed_property_map(container_type& cont)
+        : data(cont)
+    { }
+
+    hashed_property_map(hashed_property_map const& x)
+        : data(x.data)
+    { }
+
+    container_type& data;
+};
+
+template <typename I, typename P>
+typename hashed_property_map<I,P>::property_type const&
+get(hashed_property_map<I,P> const& pm,
+    typename hashed_property_map<I,P>::key_type const& x)
+{
+    return pm.data[x];
+}
+
+template <typename I, typename P>
+void
+put(hashed_property_map<I,P>& pm,
+    typename hashed_property_map<I,P>::key_type const& x,
+    typename hashed_property_map<I,P>::property_type const& v)
+{
+    pm.data[x] = v;
+}
+
+} /* namesapce graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/property_map/indexed_properties.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/property_map/indexed_properties.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,83 @@
+
+#ifndef BOOST_GRAPHS_PROPERTY_MAP_INDEXED_PROPERTIES_HPP
+#define BOOST_GRAPHS_PROPERTY_MAP_INDEXED_PROPERTIES_HPP
+
+#include <iterator>
+#include <vector>
+
+namespace boost {
+namespace graphs {
+
+/**
+ * A simple wrapper around a vector. Because the "key" to this vector is
+ * actually given as a descriptor, we have to get the underlying index that
+ * allows us to map this value to a property.
+ */
+template <typename Iterator, typename Property>
+struct indexed_property_container
+{
+    typedef Property value_type;
+    typedef typename Iterator::value_type key_type;
+    typedef std::vector<Property> container_type;
+
+    // Construct the container over the elements given by the iterator range
+    // and the default property value.
+    indexed_property_container(Iterator f, Iterator l)
+        : _map(std::distance(f, l), Property())
+    { }
+
+    indexed_property_container(std::pair<Iterator, Iterator> rng)
+        : _map(std::distance(rng.first, rng.second), Property())
+    { }
+
+    value_type& operator[](key_type const& k)
+    { return _map[k.get()]; }
+
+    container_type _map;
+};
+
+
+/**
+ * The corresponding property map implements a lightweight, regular accessor
+ * to a indexed property container.
+ */
+template <typename Iterator, typename Property>
+struct indexed_property_map
+{
+    typedef indexed_property_container<Iterator, Property> container_type;
+
+    typedef typename container_type::value_type property_type;
+    typedef typename container_type::key_type key_type;
+
+    indexed_property_map(container_type& cont)
+        : data(cont)
+    { }
+
+    indexed_property_map(indexed_property_map const& x)
+        : data(x.data)
+    { }
+
+    container_type& data;
+};
+
+template <typename I, typename P>
+typename indexed_property_map<I,P>::property_type const&
+get(indexed_property_map<I,P> const& pm,
+    typename indexed_property_map<I,P>::key_type const& x)
+{
+    return pm.data[x];
+}
+
+template <typename I, typename P>
+void
+put(indexed_property_map<I,P>& pm,
+    typename indexed_property_map<I,P>::key_type const& x,
+    typename indexed_property_map<I,P>::property_type const& v)
+{
+    pm.data[x] = v;
+}
+
+} /* namesapce graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/property_map/simple_properties.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/property_map/simple_properties.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,53 @@
+
+#ifndef BOOST_GRAPHS_PROPERTY_MAP_SIMPLE_PROPERTIES_HPP
+#define BOOST_GRAPHS_PROPERTY_MAP_SIMPLE_PROPERTIES_HPP
+
+namespace boost {
+namespace graphs {
+
+/**
+ * A simple property map provides get/put functions for non-bundled or simple
+ * vertex and edge properties. This is not called "simple" because it is
+ * trivially implemented but because it return the properties assigned to the
+ * vertex or edge (depending on the descriptor) without any indirection. To
+ * build property maps over members or a structured (or bundled) property,
+ * use the bundled property map.
+ */
+template <typename Graph, typename Descriptor, typename Property>
+struct simple_property_map
+{
+    typedef Descriptor key_type;
+    typedef Property property_type;
+
+    simple_property_map(Graph& g)
+        : graph(g)
+    { }
+
+    simple_property_map(simple_property_map const& x)
+        : graph(x.g)
+    { }
+
+    Graph& graph;
+};
+
+template <typename G, typename D, typename P>
+typename simple_property_map<G,D,P>::property_type const&
+get(simple_property_map<G,D,P> const& pm,
+    typename simple_property_map<G,D,P>::key_type const& x)
+{
+    return pm.graph.properties(x);
+}
+
+template <typename G, typename D, typename P>
+void
+put(simple_property_map<G,D,P>& pm,
+    typename simple_property_map<G,D,P>::key_type const& x,
+    typename simple_property_map<G,D,P>::property_type const& v)
+{
+    pm.graph.properties(x) = v;
+}
+
+} /* namesapce graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/utility.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/utility.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,22 @@
+
+#ifndef BOOST_GRAPH_UTILITY_HPP
+#define BOOST_GRAPH_UTILITY_HPP
+
+#include <boost/graphs/utility/unordered_pair.hpp>
+#include <boost/graphs/utility/ordered_pair.hpp>
+
+namespace boost {
+namespace graphs {
+
+/**
+ * The all important "none" type, used for empty properties and dummy type
+ * arguments.
+ *
+ * @todo Is there a general purpose Boost none?
+ */
+struct none { };
+
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/boost/graphs/utility/ordered_pair.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/utility/ordered_pair.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,70 @@
+
+#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

Added: sandbox/SOC/2008/graphs/boost/graphs/utility/unordered_pair.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/utility/unordered_pair.hpp	2008-05-29 08:54:53 EDT (Thu, 29 May 2008)
@@ -0,0 +1,143 @@
+
+#ifndef BOOST_GRAPH_UTILITY_UNORDERED_PAIR_HPP
+#define BOOST_GRAPH_UTILITY_UNORDERED_PAIR_HPP
+
+#include <functional>
+
+namespace boost {
+namespace graphs {
+
+/**
+ * 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
+
+/**
+ * Provide a lexicographical ordering for the elements in the pair. This
+ * is taken from the ordering of std::pair.
+ */
+template <typename T, typename C>
+bool
+operator<(unordered_pair<T,C> const& a, unordered_pair<T,C> const& b)
+{
+    C c;
+    return c(a.first(), b.first()) ||
+           (!c(b.first(), a.first()) &&
+             c(a.second(), b.second()));
+}
+
+template <typename T, typename C>
+bool
+operator==(unordered_pair<T,C> const& a, unordered_pair<T,C> const& b)
+{
+    return a.first() == b.first() && a.second() == b.second();
+}
+
+/**
+ * Make an ordered pair over the two values.
+ */
+template <typename T>
+unordered_pair<T>
+make_unordered_pair(T const& f, T const& s)
+{
+    unordered_pair<T> x(f, s);
+    return x;
+}
+
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif