[Boost-commit] svn:boost r46189 - in sandbox/SOC/2008/graphs/branches/tue: boost/graphs libs/graphs

From: asutton_at_[hidden]
Date: 2008-06-06 08:00:08

Author: asutton
Date: 2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
New Revision: 46189
URL: http://svn.boost.org/trac/boost/changeset/46189

Log:
Added files from IU work.

Added:
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/descriptor.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/edge_list.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/edge_set.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/edge_vector.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/incidence_list.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/incidence_set.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/incidence_vector.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/indexed_vertex_iterator.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/mapped_vertex_iterator.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/none.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/ordered_pair.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/property_index.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/property_list.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/property_vector.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/simple_vertex_iterator.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/undirected_graph.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/unordered_pair.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_list.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_map.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_multimap.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_multiset.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_set.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_vector.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/libs/graphs/Jamfile   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/libs/graphs/Jamroot   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/libs/graphs/demangle.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/libs/graphs/test.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/tue/libs/graphs/un.cpp   (contents, props changed)

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/descriptor.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/descriptor.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,110 @@
+
+#ifndef DESCRIPTOR_HPP
+#define DESCRIPTOR_HPP
+
+#include "unordered_pair.hpp"
+
+// 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.
+
+template <typename D>
+class basic_vertex_descriptor
+{
+public:
+    inline basic_vertex_descriptor()
+        : desc()
+    { }
+
+    inline basic_vertex_descriptor(D d)
+        : desc(d)
+    { }
+
+    // Assignment copy.
+    inline basic_vertex_descriptor& operator=(basic_vertex_descriptor const& d)
+    {
+        desc = d.desc;
+        return *this;
+    }
+
+    // value-type assignment.
+    inline basic_vertex_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 basic_vertex_descriptor
+    // is not the same as its default value.
+    inline bool is_valid() const
+    { return desc != basic_vertex_descriptor().desc; }
+
+    inline bool operator<(basic_vertex_descriptor const& d) const
+    { return desc < d.desc; }
+
+    inline bool operator==(basic_vertex_descriptor const& d) const
+    { return desc == d.desc; }
+
+    inline bool operator!=(basic_vertex_descriptor const& d) const
+    { return desc != d.desc; }
+
+    D desc;
+};
+
+// We actually need a specialized undirected vertex descriptor that is capable of
+// representing an edge, given a source vertex, a target vertex and a reference
+// to the edge properties.
+template <typename VertexDesc, typename PropDesc>
+class undirected_edge_descriptor
+{
+public:
+    undirected_edge_descriptor()
+        : edge()
+        , prop()
+    { }
+
+    undirected_edge_descriptor(VertexDesc u, VertexDesc v, PropDesc p)
+        : edge(u, v)
+        , prop(p)
+    { }
+
+    bool operator<(undirected_edge_descriptor const& x)
+    {
+        return edge < x.edge || (!(x.edge < edge) && prop < x.prop);
+    }
+
+private:
+    unordered_pair<VertexDesc> edge;
+    PropDesc prop;
+};
+
+#endif
+

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/edge_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/edge_list.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,35 @@
+
+#ifndef EDGE_LIST_HPP
+#define EDGE_LIST_HPP
+
+#include "property_list.hpp"
+#include "incidence_list.hpp"
+
+// The edge list does two things. First, it indicates that edges will
+// be stored in an incidence list (as opposed to a vector or set).
+// Second, this will indicate the use of a global property list.
+// Again, as opposed to a vector.
+
+template <
+    template <typename> class IncAlloc,
+    template <typename> class PropAlloc>
+struct basic_edge_list
+{
+    template <typename EdgeProps>
+    struct property_store
+    {
+        typedef property_list<EdgeProps, PropAlloc<EdgeProps> > type;
+    };
+
+    template <typename VertexDesc, typename PropDesc>
+    struct incidence_store
+    {
+        typedef std::pair<VertexDesc, PropDesc> incidence_pair;
+        typedef incidence_list<incidence_pair, IncAlloc<incidence_pair> > type;
+    };
+};
+
+struct edge_list : basic_edge_list<std::allocator, std::allocator> { };
+
+#endif
+

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/edge_set.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/edge_set.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,27 @@
+
+#ifndef EDGE_SET_HPP
+#define EDGE_SET_HPP
+
+#include "property_list.hpp"
+
+// An edge set denotes a) that incident edges are stored in a set for
+// each vertex and b) that properties are stored in a list.
+
+template <
+    template <typename> class Compare,
+    template <typename> class IncAlloc,
+    template <typename> class PropAlloc>
+struct basic_edge_set
+{
+    template <typename EdgeProps>
+    struct property_store
+    {
+        typedef property_list<EdgeProps, PropAlloc<EdgeProps> > type;
+    };
+};
+
+template <template <typename> class Compare = std::less>
+struct edge_set : basic_edge_set<Compare, std::allocator, std::allocator> { };
+
+#endif
+

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/edge_vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/edge_vector.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,37 @@
+
+#ifndef EDGE_VECTOR_HPP
+#define EDGE_VECTOR_HPP
+
+#include "property_vector.hpp"
+#include "incidence_vector.hpp"
+
+// What's in an edge vector? Basically, an edge vector has to specify
+// the type of property storage and the type of incidence storage. What
+// are the possible parameters to edge storage?
+// 1. The edge properties
+// 2. Allocator for the property store
+// 3. Allocator for the incidence store
+
+template <
+    template <typename> class IncAlloc,
+    template <typename> class PropAlloc>
+struct basic_edge_vector
+{
+    template <typename EdgeProps>
+    struct property_store
+    {
+        typedef property_vector<EdgeProps, PropAlloc<EdgeProps> > type;
+    };
+
+    template <typename VertexDesc, typename PropDesc>
+    struct incidence_store
+    {
+        typedef std::pair<VertexDesc, PropDesc> incidence_pair;
+        typedef incidence_vector<incidence_pair, IncAlloc<incidence_pair> > type;
+    };
+};
+
+struct edge_vector : basic_edge_vector<std::allocator, std::allocator> { };
+
+#endif
+

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/incidence_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/incidence_list.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,99 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_LIST_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_LIST_HPP
+
+#include <list>
+#include <algorithm>
+
+template <typename IncEdge, typename Alloc>
+class incidence_list
+{
+    typedef std::list<IncEdge, Alloc> store_type;
+public:
+    typedef IncEdge incidence_pair;
+    typedef typename IncEdge::first_type vertex_descriptor;
+    typedef typename IncEdge::second_type property_descriptor;
+
+    typedef typename store_type::iterator iterator;
+    typedef typename store_type::const_iterator const_iterator;
+    typedef typename store_type::size_type size_type;
+
+    // Constructors
+    incidence_list();
+
+    void add(incidence_pair);
+
+    iterator find(incidence_pair);
+    const_iterator find(incidence_pair) const;
+
+    void remove(incidence_pair);
+    void clear();
+
+    size_type size() const;
+
+private:
+    store_type _edges;
+};
+
+#define BOOST_GRAPHS_IL_PARAMS \
+    typename IE, typename A
+
+template <BOOST_GRAPHS_IL_PARAMS>
+incidence_list<IE,A>::incidence_list()
+    : _edges()
+{ }
+
+#if 0
+
+// 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();
+}
+
+#endif
+
+#endif

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/incidence_set.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/incidence_set.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,96 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_HPP
+
+#include <set>
+
+#include <boost/graphs/adjacency_list/is/incidence_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.
+    inline void add(edge_descriptor e);
+    inline iterator find(edge_descriptor e);
+    inline const_iterator find(edge_descriptor e) const;
+    inline void remove(edge_descriptor e);
+    inline void clear();
+    inline 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/branches/tue/boost/graphs/incidence_vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/incidence_vector.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,120 @@
+
+#ifndef INCIDENCE_VECTOR
+#define INCIDENCE_VECTOR
+
+#include <vector>
+
+/**
+ * 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 IncEdge, typename Alloc>
+class incidence_vector
+{
+    typedef std::vector<IncEdge, Alloc> store_type;
+public:
+    typedef IncEdge incidence_pair;
+    typedef typename IncEdge::first_type vertex_descriptor;
+    typedef typename IncEdge::second_type property_descriptor;
+
+    typedef typename store_type::iterator iterator;
+    typedef typename store_type::const_iterator const_iterator;
+    typedef typename store_type::size_type size_type;
+
+    // Constructors
+    incidence_vector();
+
+    void add(incidence_pair);
+ 
+    iterator find(incidence_pair);
+    const_iterator find(incidence_pair) const;
+
+    void remove(incidence_pair);
+    void clear();
+
+    size_type size() const;
+
+private:
+    store_type _edges;
+};
+
+#define BOOST_GRAPHS_IV_PARAMS \
+    typename IE, typename A
+
+template <BOOST_GRAPHS_IV_PARAMS>
+incidence_vector<IE,A>::incidence_vector()
+    : _edges()
+{ }
+
+template <BOOST_GRAPHS_IV_PARAMS>
+void
+incidence_vector<IE,A>::add(incidence_pair e)
+{
+    _edges.push_back(e);
+}
+
+template <BOOST_GRAPHS_IV_PARAMS>
+typename incidence_vector<IE,A>::size_type
+incidence_vector<IE,A>::size() const
+{
+    return _edges.size();
+}
+
+#undef BOOST_GRAPHS_IV_PARAMS
+
+#if 0
+
+// 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();
+}
+
+#endif
+
+#endif

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/indexed_vertex_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/indexed_vertex_iterator.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,156 @@
+
+#ifndef INDEXED_VERTEX_ITERATOR
+#define INDEXED_VERTEX_ITERATOR
+
+#include <algorithm>
+
+/**
+ * The indexed vertex iterator provides a vertex iterator for stores whose
+ * descriptors cannot be pointers (i.e., vectors). By virtue of the fact that
+ * Store is required to be a vector of something, this is a random access
+ * iterator.
+ */
+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;
+
+    // Constructors
+    inline indexed_vertex_iterator();
+    inline indexed_vertex_iterator(indexed_vertex_iterator const& x);
+    inline indexed_vertex_iterator(Store const& s, iterator const& x);
+
+    // Assignment and increment
+    inline indexed_vertex_iterator& operator=(indexed_vertex_iterator const& x);
+    inline indexed_vertex_iterator& operator+=(difference_type n);
+    inline indexed_vertex_iterator& operator-=(difference_type n);
+    inline indexed_vertex_iterator& operator++();
+    inline indexed_vertex_iterator& operator--();
+
+    inline indexed_vertex_iterator operator+(difference_type n) const;
+    inline indexed_vertex_iterator operator-(difference_type n) const;
+    inline difference_type operator-(indexed_vertex_iterator const& x) const;
+
+    inline reference operator*();
+
+    inline bool operator==(indexed_vertex_iterator const& x) const;
+    inline bool operator!=(indexed_vertex_iterator const& x) const;
+
+private:
+    Store const* store;
+    iterator iter;
+};
+
+template <typename S>
+indexed_vertex_iterator<S>::indexed_vertex_iterator()
+    : store(0)
+    , iter()
+{ }
+
+template <typename S>
+indexed_vertex_iterator<S>::indexed_vertex_iterator(indexed_vertex_iterator const& x)
+    : store(x.store)
+    , iter(x.iter)
+{ }
+
+template <typename S>
+indexed_vertex_iterator<S>::indexed_vertex_iterator(S const& s, iterator const& x)
+    : store(&s)
+    , iter(x)
+{ }
+
+template <typename S>
+indexed_vertex_iterator<S>&
+indexed_vertex_iterator<S>::operator=(indexed_vertex_iterator const& x)
+{
+    iter = x.iter;
+    store = x.store;
+    return *this;
+}
+
+template <typename S>
+indexed_vertex_iterator<S>&
+indexed_vertex_iterator<S>::operator+=(difference_type n)
+{
+    iter += n;
+    return *this;
+}
+
+template <typename S>
+indexed_vertex_iterator<S>&
+indexed_vertex_iterator<S>::operator-=(difference_type n)
+{
+    iter -= n;
+    return *this;
+}
+
+template <typename S>
+indexed_vertex_iterator<S>&
+indexed_vertex_iterator<S>::operator++()
+{
+    ++iter;
+    return *this;
+}
+
+template <typename S>
+indexed_vertex_iterator<S>&
+indexed_vertex_iterator<S>::operator--()
+{
+    --iter;
+    return *this;
+}
+
+template <typename S>
+indexed_vertex_iterator<S>
+indexed_vertex_iterator<S>::operator+(difference_type n) const
+{
+    return iter + n;
+}
+
+template <typename S>
+indexed_vertex_iterator<S>
+indexed_vertex_iterator<S>::operator-(difference_type n) const
+{
+    return iter - n;
+}
+
+template <typename S>
+typename indexed_vertex_iterator<S>::difference_type
+indexed_vertex_iterator<S>::operator-(indexed_vertex_iterator const& x) const
+{
+    return iter - x.iter;
+}
+
+template <typename S>
+typename indexed_vertex_iterator<S>::reference
+indexed_vertex_iterator<S>::operator*()
+{
+    // The returned descriptor is simply the distance from the beginning of
+    // the underlying store to the end.
+    return std::distance(store->begin(), iter);
+}
+
+template <typename S>
+bool
+indexed_vertex_iterator<S>::operator==(indexed_vertex_iterator const& x) const
+{
+     return (store == x.store) && (iter == x.iter);
+}
+
+template <typename S>
+bool
+indexed_vertex_iterator<S>::operator!=(indexed_vertex_iterator const& x) const
+{
+    return (store == x.store) && (iter != x.iter);
+}
+
+#endif

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/mapped_vertex_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/mapped_vertex_iterator.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,110 @@
+
+#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. Because this iterator is taken
+ * from pair associative structures, it is bidirectional but not random access.
+ */
+template <typename Store>
+class mapped_vertex_iterator
+{
+    typedef typename Store::const_iterator iterator;
+public:
+    typedef typename Store::mapped_type vertex_type;
+    typedef typename vertex_type::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 mapped_vertex_iterator();
+    inline mapped_vertex_iterator(mapped_vertex_iterator const& x);
+    inline mapped_vertex_iterator(iterator const& x);
+
+    inline mapped_vertex_iterator& operator=(mapped_vertex_iterator const& x);
+    inline mapped_vertex_iterator& operator++();
+    inline mapped_vertex_iterator& operator--();
+
+    inline reference operator*();
+
+    inline bool operator==(mapped_vertex_iterator const& x) const;
+    inline bool operator!=(mapped_vertex_iterator const& x) const;
+
+private:
+    iterator iter;
+};
+
+template <typename S>
+mapped_vertex_iterator<S>::mapped_vertex_iterator()
+    : iter()
+{ }
+
+template <typename S>
+mapped_vertex_iterator<S>::mapped_vertex_iterator(mapped_vertex_iterator const& x)
+    : iter(x.iter)
+{ }
+
+template <typename S>
+mapped_vertex_iterator<S>::mapped_vertex_iterator(iterator const& x)
+    : iter(x)
+{ }
+
+template <typename S>
+mapped_vertex_iterator<S>&
+mapped_vertex_iterator<S>::operator=(mapped_vertex_iterator const& x)
+{
+    iter = x.iter;
+    return *this;
+}
+
+template <typename S>
+mapped_vertex_iterator<S>&
+mapped_vertex_iterator<S>::operator++()
+{
+    ++iter;
+    return *this;
+}
+
+template <typename S>
+mapped_vertex_iterator<S>&
+mapped_vertex_iterator<S>::operator--()
+{
+    --iter;
+    return *this;
+}
+
+template <typename S>
+typename mapped_vertex_iterator<S>::reference
+mapped_vertex_iterator<S>::operator*()
+{
+    return &const_cast<vertex_type&>(iter->second);
+}
+
+template <typename S>
+bool
+mapped_vertex_iterator<S>::operator==(mapped_vertex_iterator const& x) const
+{
+    return iter == x.iter;
+}
+
+template <typename S>
+bool
+mapped_vertex_iterator<S>::operator!=(mapped_vertex_iterator const& x) const
+{
+    return iter != x.iter;
+}
+
+} /* namespace adj_list */
+} /* namespace graph */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/none.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/none.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,9 @@
+
+#ifndef NONE_HPP
+#define NONE_HPP
+
+// The canonical none type.
+struct none { };
+
+#endif
+

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/ordered_pair.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/ordered_pair.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 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/branches/tue/boost/graphs/property_index.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/property_index.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,15 @@
+
+#ifndef PROPERTY_INDEX_HPP
+#define PROPERTY_INDEX_HPP
+
+// If no edge properties are given, then we can just manufacture
+// indices for edges without actually connecting them to anything.
+// I think. Is there anything that would make this /not/ work?
+
+class property_index
+{
+public:
+};
+
+#endif
+

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/property_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/property_list.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,78 @@
+
+#ifndef PROPERTY_LIST_HPP
+#define PROPERTY_LIST_HPP
+
+#include <list>
+
+// Forward descriptor
+template <typename Iter> class proplist_descriptor;
+
+// The property list implements global list of properties for node-based
+// edge storage. Note that we can get away with only a list because the
+// edge addition logic is implemented by the incidence list.
+
+template <typename Props, typename Alloc>
+class property_list
+{
+    typedef std::list<Props, Alloc> store_type;
+public:
+    typedef Props property_type;
+    typedef proplist_descriptor<typename store_type::iterator> property_descriptor;
+
+    property_list();
+
+    property_descriptor add();
+    property_descriptor add(property_type const&);
+
+private:
+    store_type _props;
+};
+
+template <typename Alloc>
+class property_list<none, Alloc>
+{
+public:
+    typedef std::size_t property_descriptor;
+};
+
+// The proplist descriptor provides a wrapper around a list iterator
+// that provides comparability for the underlying iterator. Note that
+// the comparison has little to do with actual ordering of eleemnts.
+// This is to say that i < j !=> *i < *j. This just provides a mechanism
+// for ordering the descriptors.
+
+template <typename Iter>
+class proplist_descriptor
+{
+    proplist_descriptor(Iter const& iter)
+        : iter(iter)
+    { }
+
+    bool operator <(proplist_descriptor const& x) const
+    { return &*iter < &*x.iter; } 
+
+    Iter iter;
+};
+
+template <typename P, typename A>
+property_list<P,A>::property_list()
+    : _props()
+{ }
+
+template <typename P, typename A>
+typename property_list<P,A>::property_descriptor
+property_list<P,A>::add()
+{
+    return add(property_type());
+}
+
+template <typename P, typename A>
+typename property_list<P,A>::property_descriptor
+property_list<P,A>::add(property_type const& p)
+{
+    return _props.insert(_props.end(), p);
+}
+
+
+#endif
+

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/property_vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/property_vector.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,56 @@
+
+#ifndef PROPERTY_VERTEX_HPP
+#define PROPERTY_VERTEX_HPP
+
+#include <vector>
+
+// The property vector implements a vector-based global property
+// store for vector-based edge storage. Assuming, of course, that
+// there are actually edge properties.
+
+template <typename Props, typename Alloc>
+class property_vector
+{
+    typedef std::vector<Props, Alloc> store_type;
+public:
+    typedef Props property_type;
+    typedef std::size_t property_descriptor;
+
+    property_vector();
+
+    property_descriptor add();
+    property_descriptor add(property_type const&);
+
+private:
+    store_type _props;
+};
+
+template <typename Alloc>
+class property_vector<none, Alloc>
+{
+public:
+    typedef std::size_t property_descriptor;
+};
+
+template <typename P, typename A>
+property_vector<P,A>::property_vector()
+    : _props()
+{ }
+
+template <typename P, typename A>
+typename property_vector<P,A>::property_descriptor
+property_vector<P,A>::add()
+{
+    return add(property_type());
+}
+
+template <typename P, typename A>
+typename property_vector<P,A>::property_descriptor
+property_vector<P,A>::add(property_type const& p)
+{
+    _props.push_back(p);
+    return _props.size() - 1;
+}
+
+#endif
+

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/simple_vertex_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/simple_vertex_iterator.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,103 @@
+
+#ifndef SIMPLE_VERTEX_ITERATOR_HPP
+#define SIMPLE_VERTEX_ITERATOR_HPP
+
+#include <iterator>
+
+/**
+ * The value vertex iterator provides a vertex iterator unique associative
+ * containers and sequences that don't invalidate memory on insertions
+ * (lists).
+ */
+template <typename Store>
+class simple_vertex_iterator
+{
+    typedef typename Store::const_iterator iterator;
+public:
+    typedef typename Store::value_type vertex_type;
+    typedef typename vertex_type::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 simple_vertex_iterator();
+    inline simple_vertex_iterator(simple_vertex_iterator const& x);
+    inline simple_vertex_iterator(iterator const& x);
+
+    inline simple_vertex_iterator& operator=(simple_vertex_iterator const& x);
+    inline simple_vertex_iterator& operator++();
+    inline simple_vertex_iterator& operator--();
+
+    inline reference operator*();
+
+    inline bool operator==(simple_vertex_iterator const& x) const;
+    inline bool operator!=(simple_vertex_iterator const& x) const;
+
+private:
+    iterator iter;
+};
+
+template <typename S>
+simple_vertex_iterator<S>::simple_vertex_iterator()
+    : iter()
+{ }
+
+template <typename S>
+simple_vertex_iterator<S>::simple_vertex_iterator(simple_vertex_iterator const& x)
+    : iter(x.iter)
+{ }
+
+template <typename S>
+simple_vertex_iterator<S>::simple_vertex_iterator(iterator const& x)
+    : iter(x)
+{ }
+
+template <typename S>
+simple_vertex_iterator<S>&
+simple_vertex_iterator<S>::operator=(simple_vertex_iterator const& x)
+{
+    iter = x.iter;
+    return *this;
+}
+
+template <typename S>
+simple_vertex_iterator<S>&
+simple_vertex_iterator<S>::operator++()
+{
+    ++iter;
+    return *this;
+}
+
+template <typename S>
+simple_vertex_iterator<S>&
+simple_vertex_iterator<S>::operator--()
+{
+    --iter;
+    return *this;
+}
+
+template <typename S>
+typename simple_vertex_iterator<S>::reference
+simple_vertex_iterator<S>::operator*()
+{
+    return &const_cast<vertex_type&>(*iter);
+}
+
+template <typename S>
+bool
+simple_vertex_iterator<S>::operator==(simple_vertex_iterator const& x) const
+{
+    return iter == x.iter;
+}
+
+template <typename S>
+bool
+simple_vertex_iterator<S>::operator!=(simple_vertex_iterator const& x) const
+{
+    return iter != x.iter;
+}
+
+#endif

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/undirected_graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/undirected_graph.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,141 @@
+
+#ifndef UNDIRECTED_GRAPH_HPP
+#define UNDIRECTED_GRAPH_HPP
+
+#include "none.hpp"
+
+// Various issues...
+// * Undirected graphs have a global property store.
+// * Global property stores are lists (for node-based edge stores) and
+//   vectors (for vector edge stores).
+// * Edge descriptors are a triple: an unordered pair consisting of
+//   vertex descriptors, and an a property descriptor.
+// * The property descriptor provide access to the properties of the
+//   given edge. This would best be described as the edge property
+//   accessors.
+// * If there are no properties, then the property store doesn't really
+//   need to exist. We can just pretend to allocate them and return
+//   an integer "pseudo descriptor".
+
+#include "vertex.hpp"
+#include "vertex_vector.hpp"
+#include "vertex_list.hpp"
+
+#include "descriptor.hpp"
+#include "edge_vector.hpp"
+#include "edge_list.hpp"
+#include "edge_set.hpp"
+
+template <
+    typename VertexProps,
+    typename EdgeProps,
+    typename VertexStore,
+    typename EdgeStore>
+class undirected_graph
+{
+public:
+    typedef VertexProps vertex_properties;
+    typedef EdgeProps edge_properties;
+
+    // Generate the property store type first. We can do this first because
+    // it's basically independant of everything else, but contributes to almost
+    // everything in the class by virtue of the property descriptor.
+    typedef typename EdgeStore::template property_store<edge_properties>::type property_store;
+
+    // Generate a bunch of descriptors. The vertex descriptor is fairly
+    // straightforward since, like the property store, its independant of almost
+    // everything. The property descriptor depends entirely upon the property
+    // store and the edge descriptor is actually fairly complicated.
+    typedef typename VertexStore::descriptor_type vertex_descriptor;
+    typedef typename property_store::property_descriptor property_descriptor;
+    typedef undirected_edge_descriptor<vertex_descriptor, property_descriptor> edge_descriptor;
+
+    // Generate the incidence list. The incidence list for a single vertex
+    // contains a pair: the opposite edge and a property descriptor.
+    typedef typename EdgeStore::template incidence_store<vertex_descriptor, property_descriptor>::type incidence_store;
+    typedef typename incidence_store::size_type incidence_size_type;
+
+    // Generate the vertex type over the given properties and the incidence
+    // store. Then, turn around and use that to generate the vertex store and its
+    // related types.
+    typedef vertex<vertex_properties, incidence_store> vertex_type;
+    typedef typename VertexStore::template store<vertex_type>::type vertex_store;
+    typedef typename vertex_store::size_type vertices_size_type;
+
+    // FIXME: This is a bit hacky, but without constrained members, we need a key
+    // type to enable mapped vertices.
+    typedef typename VertexStore::key_type key_type;
+
+    // Constructors
+    undirected_graph();
+
+    // Add vertices
+    vertex_descriptor add_vertex();
+    vertex_descriptor add_vertex(vertex_properties const&);
+    vertex_descriptor add_vertex(key_type const&, vertex_properties const&);
+
+    // Add edges
+    edge_descriptor add_edge(vertex_descriptor, vertex_descriptor);
+    edge_descriptor add_edge(vertex_descriptor, vertex_descriptor, edge_properties const&);
+
+    vertices_size_type num_vertices() const;
+
+    incidence_size_type degree() const;
+
+private:
+    property_store _props;
+    vertex_store _verts;
+};
+
+#define BOOST_GRAPHS_UG_PARAMS \
+    typename VP, typename EP, typename VS, typename ES
+
+template <BOOST_GRAPHS_UG_PARAMS>
+undirected_graph<VP,EP,VS,ES>::undirected_graph()
+    : _props()
+    , _verts()
+{ }
+
+template <BOOST_GRAPHS_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
+undirected_graph<VP,EP,VS,ES>::add_vertex()
+{
+    return _verts.add();
+}
+
+template <BOOST_GRAPHS_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
+undirected_graph<VP,EP,VS,ES>::add_vertex(vertex_properties const& vp)
+{
+    return _verts.add(vp);
+}
+
+template <BOOST_GRAPHS_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
+undirected_graph<VP,EP,VS,ES>::add_edge(vertex_descriptor u, vertex_descriptor v)
+{
+    // Start by getting a property descriptor for the edge.
+    property_descriptor p = _props.add();
+    vertex_type& vert = _verts.vertex(u);
+    vert.connect(v, p);
+
+    return edge_descriptor();
+}
+
+template <BOOST_GRAPHS_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertices_size_type
+undirected_graph<VP,EP,VS,ES>::num_vertices() const
+{ 
+    return _verts.size(); 
+}
+
+template <BOOST_GRAPHS_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::incidence_size_type
+undirected_graph<VP,EP,VS,ES>::degree(vertex_descriptor v) const
+{
+}
+
+#undef BOOST_GRAPHS_UG_PARAMS
+
+#endif
+

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/unordered_pair.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/unordered_pair.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,137 @@
+
+#ifndef UNORDERED_PAIR_HPP
+#define UNORDERED_PAIR_HPP
+
+#include <functional>
+
+/**
+ * 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;
+}
+
+#endif

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,52 @@
+
+#ifndef VERTEX_HPP
+#define VERTEX_HPP
+
+// A vertex, at least for an undirected graph, is simply an repository 
+// for the vertex' properties and an interface for the its incidence
+// list.
+//
+// For directed graphs, it's basically the same, but has an out edge
+// list and/or an in edge list, and the edge properties are stored on
+// the out edge list.
+
+template <typename VertexProps, typename IncStore>
+class vertex
+{
+    typedef IncStore incidence_store;
+public:
+    typedef VertexProps vertex_properties;
+    typedef typename incidence_store::vertex_descriptor vertex_descriptor;
+    typedef typename incidence_store::property_descriptor property_descriptor;
+
+    vertex();
+    vertex(vertex_properties const& vp);
+
+    void connect(vertex_descriptor, property_descriptor);
+
+private:
+    vertex_properties _props;
+    incidence_store _edges;
+};
+
+template <typename VP, typename IS>
+vertex<VP,IS>::vertex()
+    : _props()
+    , _edges()
+{ }
+
+template <typename VP, typename IS>
+vertex<VP,IS>::vertex(vertex_properties const& vp)
+    : _props(vp)
+    , _edges()
+{ }
+
+template <typename VP, typename IS>
+void
+vertex<VP,IS>::connect(vertex_descriptor v, property_descriptor p)
+{
+    _edges.add(make_pair(v, p));
+}
+
+#endif
+

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_list.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,257 @@
+
+#ifndef VERTEX_LIST_HPP
+#define VERTEX_LIST_HPP
+
+#include <list>
+
+#include "descriptor.hpp"
+#include "simple_vertex_iterator.hpp"
+
+// Forward declarations
+template <typename V, template <typename> class A> class vertex_list_elem;
+template <typename V, typename A> class vertex_list_impl;
+
+template <template <typename> class Allocator>
+struct basic_vertex_list
+{
+    typedef void* key_type;
+    typedef void* descriptor_type;
+
+    template <typename Vertex>
+    struct store
+    {
+        typedef vertex_list_elem<Vertex, Allocator> stored_vertex;
+        typedef vertex_list_impl<stored_vertex, Allocator<stored_vertex> > type;
+    };
+};
+
+struct vertex_list : basic_vertex_list<std::allocator> { };
+
+template <typename Vertex, template <typename> class Alloc>
+class vertex_list_elem
+    : public Vertex
+{
+    typedef vertex_list_elem<Vertex, Alloc> this_type;
+public:
+    typedef typename std::list<this_type, Alloc<this_type> >::iterator iterator;
+
+    inline vertex_list_elem(typename Vertex::vertex_properties const& vp)
+        : Vertex(vp)
+        , iter()
+    { }
+
+    iterator iter;
+};
+
+/**
+ * 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.
+ *
+ * FIXME: Track the size of the list, so that num_vertices() is constant.
+ */
+template <typename Vertex, typename Allocator>
+class vertex_list_impl
+{
+    typedef std::list<Vertex, Allocator> vertex_store;
+public:
+    typedef void* vertex_descriptor;
+    typedef Vertex vertex_type;
+    typedef typename Vertex::vertex_properties vertex_properties;
+    typedef typename vertex_store::size_type size_type;
+    typedef simple_vertex_iterator<vertex_store> iterator;
+    typedef std::pair<iterator, iterator> range;
+
+    // Constructors
+    vertex_list_impl();
+
+    // Add/remove vertices.
+    vertex_descriptor add();
+    vertex_descriptor add(vertex_properties const& vp);
+
+    // Remove vertices.
+    void remove(vertex_descriptor v);
+
+    // Number of vertices.
+    size_type size() const;
+
+    // Vertex iteration.
+    range vertices() const;
+    iterator begin() const;
+    iterator end() 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;
+};
+
+#define BOOST_GRAPHS_VL_PARAMS \
+    typename V, typename A
+
+/**
+ * Construct an empty vertex list.
+ */
+template <BOOST_GRAPHS_VL_PARAMS>
+vertex_list_impl<V,A>::vertex_list_impl()
+    : _verts()
+{ }
+
+/**
+ * Add a vertex to the list with no or default properties.
+ *
+ * @complexity O(1)
+ */
+template <BOOST_GRAPHS_VL_PARAMS>
+typename vertex_list_impl<V,A>::vertex_descriptor
+vertex_list_impl<V,A>::add()
+{
+    return add(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 <BOOST_GRAPHS_VL_PARAMS>
+typename vertex_list_impl<V,A>::vertex_descriptor
+vertex_list_impl<V,A>::add(vertex_properties const& vp)
+{
+    typename vertex_store::iterator i = _verts.insert(_verts.end(), vertex_type(vp));
+    i->iter = i;
+    return &(*i);
+}
+
+/**
+ * Return the number of vertices in the store.
+ */
+template <BOOST_GRAPHS_VL_PARAMS>
+typename vertex_list_impl<V,A>::size_type
+vertex_list_impl<V,A>::size() const
+{
+    return _verts.size();
+}
+
+#if 0
+
+/**
+ * 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
+vertex_list_impl<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 vertex_list_impl<V,A>::vertices_size_type
+vertex_list_impl<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 vertex_list_impl<V,A>::vertex_iterator,
+    typename vertex_list_impl<V,A>::vertex_iterator
+>
+vertex_list_impl<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 vertex_list_impl<V,A>::vertex_iterator
+vertex_list_impl<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 vertex_list_impl<V,A>::vertex_iterator
+vertex_list_impl<V,A>::end_vertices() const
+{
+    return _verts.end();
+}
+
+/**
+ * Get access to the given vertex.
+ */
+template <typename V, template <typename> class A>
+typename vertex_list_impl<V,A>::vertex_type&
+vertex_list_impl<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 vertex_list_impl<V,A>::vertex_type const&
+vertex_list_impl<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 vertex_list_impl<V,A>::vertex_properties&
+vertex_list_impl<V,A>::properties(vertex_descriptor v)
+{
+    return *vertex(v);
+}
+
+/**
+ * Access the properties ofthe given vertex.
+ */
+template <typename V, template <typename> class A>
+typename vertex_list_impl<V,A>::vertex_properties const&
+vertex_list_impl<V,A>::properties(vertex_descriptor v) const
+{
+    return *vertex(v);
+}
+
+#endif
+
+#endif
+

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_map.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_map.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,330 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_MAP_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_MAP_HPP
+
+#include <map>
+
+#include <boost/graphs/adjacency_list/descriptor.hpp>
+#include <boost/graphs/adjacency_list/vs/mapped_vertex_iterator.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+// Forward declarations
+template <typename V, typename K, template <typename> class C, template <typename> class A> class vertex_map_elem;
+template <typename V, typename K, typename C, typename A> class vertex_map_impl;
+
+template <typename Key, template <typename> class Compare, template <typename> class Allocator>
+struct basic_vertex_map
+{
+    typedef basic_vertex_descriptor<void*> descriptor_type;
+
+    template <typename Vertex>
+    struct store
+    {
+        typedef vertex_map_elem<Vertex, Key, Compare, Allocator> stored_vertex;
+        typedef std::pair<const Key, stored_vertex> stored_value;
+        typedef vertex_map_impl<stored_vertex, Key, Compare<Key>, Allocator<stored_value> > type;
+    };
+};
+
+template <typename Key, template <typename> class Compare = std::less>
+struct vertex_map : basic_vertex_map<Key, Compare, std::allocator> { };
+
+// 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 vertex_map_elem
+    : public Vertex
+{
+    typedef vertex_map_elem<Vertex, Key, Compare, Alloc> this_type;
+public:
+    typedef typename std::map<
+            Key, this_type, Compare<Key>, Alloc< std::pair<Key, this_type> >
+        >::iterator iterator;
+
+    inline vertex_map_elem(typename Vertex::vertex_properties const& vp)
+        : Vertex(vp)
+        , iter()
+    { }
+
+    iterator iter;
+};
+
+/**
+ * The vertex_map_impl 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, typename Compare, typename Allocator>
+class vertex_map_impl
+{
+    typedef std::map<Key, Vertex, Compare, Allocator> vertex_store;
+public:
+    typedef Key key_type;
+    typedef Vertex vertex_type;
+    typedef typename Vertex::vertex_properties vertex_properties;
+    typedef typename Vertex::vertex_descriptor vertex_descriptor;
+    typedef typename vertex_store::size_type vertices_size_type;
+    typedef mapped_vertex_iterator<vertex_store> vertex_iterator;
+
+    // Constructors
+    vertex_map_impl();
+
+    // Add or insert a vertex.
+    vertex_descriptor add_vertex(key_type const& k, vertex_properties const& vp);
+    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;
+};
+
+#define BOOST_GRAPHS_VM_PARAMS \
+    typename V, typename K, typename C, typename A
+
+template <BOOST_GRAPHS_VM_PARAMS>
+vertex_map_impl<V,K,C,A>::vertex_map_impl()
+    : _verts()
+{ }
+
+#undef BOOST_GRAPHS_VM_PARAMS
+
+#if 0
+
+/**
+ * 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 vertex_map_impl<V,K,C,A>::vertex_descriptor
+vertex_map_impl<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 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 vertex_map_impl<V,K,C,A>::vertex_descriptor, bool>
+vertex_map_impl<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 vertex_map_impl<V,K,C,A>::vertex_descriptor
+vertex_map_impl<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
+vertex_map_impl<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 vertex_map_impl<V,K,C,A>::vertices_size_type
+vertex_map_impl<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 vertex_map_impl<V,K,C,A>::vertex_iterator,
+    typename vertex_map_impl<V,K,C,A>::vertex_iterator
+>
+vertex_map_impl<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 vertex_map_impl<V,K,C,A>::vertex_iterator
+vertex_map_impl<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 vertex_map_impl<V,K,C,A>::vertex_iterator
+vertex_map_impl<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 vertex_map_impl<V,K,C,A>::vertex_type&
+vertex_map_impl<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 vertex_map_impl<V,K,C,A>::vertex_type const&
+vertex_map_impl<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 vertex_map_impl<V,K,C,A>::vertex_descriptor
+vertex_map_impl<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 vertex_map_impl<V,K,C,A>::key_type const&
+vertex_map_impl<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 vertex_map_impl<V,K,C,A>::vertex_properties&
+vertex_map_impl<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 vertex_map_impl<V,K,C,A>::vertex_properties const&
+vertex_map_impl<V,K,C,A>::properties(vertex_descriptor v) const
+{
+    return *vertex(v);
+}
+
+#endif
+
+} /* namespace adj_list */
+} /* namesapce graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_multimap.hpp
==============================================================================

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_multiset.hpp
==============================================================================

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_set.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_set.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,318 @@
+
+#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/adjacency_list/descriptor.hpp>
+#include <boost/graphs/adjacency_list/vs/simple_vertex_iterator.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+// Forward declarations
+template <typename V, template <typename> class C, template <typename> class A> class vertex_set_elem;
+template <typename V, typename C, typename A> class vertex_set_impl;
+
+template <template <typename> class Compare, template <typename> class Allocator>
+struct basic_vertex_set
+{
+    typedef basic_vertex_descriptor<void*> descriptor_type;
+
+    template <typename Vertex>
+    struct store
+    {
+        typedef vertex_set_elem<Vertex, Compare, Allocator> stored_vertex;
+        typedef vertex_set_impl<stored_vertex, Compare<stored_vertex>, Allocator<stored_vertex> > type;
+    };
+};
+
+template <template <typename> class Compare = std::less>
+struct vertex_set : basic_vertex_set<Compare, std::allocator> { };
+
+// 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 vertex_set_elem
+    : public Vertex
+{
+    typedef vertex_set_elem<Vertex, Compare, Alloc> this_type;
+public:
+    typedef typename std::set<
+            this_type, Compare<this_type>, Alloc<this_type>
+        >::iterator iterator;
+
+    inline vertex_set_elem(typename Vertex::vertex_properties const& vp)
+        : Vertex(vp)
+        , iter()
+    { }
+
+    iterator iter;
+};
+
+/**
+ * The vertex_set_impl 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 Compare, typename Allocator>
+class vertex_set_impl
+{
+    typedef std::set<Vertex, Compare, Allocator> vertex_store;
+public:
+    typedef Vertex vertex_type;
+    typedef typename Vertex::vertex_properties vertex_properties;
+    typedef typename Vertex::vertex_descriptor vertex_descriptor;
+    typedef typename vertex_store::size_type vertices_size_type;
+    typedef simple_vertex_iterator<vertex_store> vertex_iterator;
+    typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
+
+    // Constructors
+    vertex_set_impl();
+
+    // 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;
+};
+
+
+#define BOOST_GRAPHS_VS_PARAMS \
+    typename V, typename C, typename A
+
+template <BOOST_GRAPHS_VS_PARAMS>
+vertex_set_impl<V,C,A>::vertex_set_impl()
+    : _verts()
+{ }
+
+#undef BOOST_GRAPHS_VS_PARAMS
+
+#if 0
+
+/**
+ * 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 vertex_set_impl<V,C,A>::vertex_descriptor
+vertex_set_impl<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 vertex_set_impl<V,C,A>::vertex_descriptor, bool>
+vertex_set_impl<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
+vertex_set_impl<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
+vertex_set_impl<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 vertex_set_impl<V,C,A>::vertex_descriptor
+vertex_set_impl<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 vertex_set_impl<V,C,A>::vertices_size_type
+vertex_set_impl<V,C,A>::num_vertices() const
+{
+    return _verts.size();
+}
+
+/**
+ * Return the iterator range for the graph.
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+std::pair<
+    typename vertex_set_impl<V,C,A>::vertex_iterator,
+    typename vertex_set_impl<V,C,A>::vertex_iterator
+>
+vertex_set_impl<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 vertex_set_impl<V,C,A>::vertex_iterator
+vertex_set_impl<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 vertex_set_impl<V,C,A>::vertex_iterator
+vertex_set_impl<V,C,A>::end_vertices() const
+{
+    return _verts.end();
+}
+
+/**
+ * Get access to the given vertex.
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+typename vertex_set_impl<V,C,A>::vertex_type&
+vertex_set_impl<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 vertex_set_impl<V,C,A>::vertex_type const&
+vertex_set_impl<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 vertex_set_impl<V,C,A>::vertex_properties&
+vertex_set_impl<V,C,A>::properties(vertex_descriptor v)
+{
+    return *vertex(v);
+}
+
+/**
+ * Access the properties of the given vertex.
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+typename vertex_set_impl<V,C,A>::vertex_properties const&
+vertex_set_impl<V,C,A>::properties(vertex_descriptor v) const
+{
+    return *vertex(v);
+}
+
+#endif
+
+} /* namespace adj_list */
+} /* namesapce graphs */
+} /* namespace boost */
+
+#endif

Added: sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/boost/graphs/vertex_vector.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,216 @@
+
+#ifndef VERTEX_VECTOR_HPP
+#define VERTEX_VECTOR_HPP
+
+#include <vector>
+
+#include "indexed_vertex_iterator.hpp"
+
+// Forward declarations
+template <typename V, typename A> struct vertex_vector_impl;
+
+template <template <typename> class Allocator>
+struct basic_vertex_vector
+{
+    typedef void* key_type;
+    typedef std::size_t descriptor_type;
+
+    template <typename Vertex>
+    struct store
+    {
+        typedef vertex_vector_impl<Vertex, Allocator<Vertex> > type;
+    };
+};
+
+struct vertex_vector : basic_vertex_vector<std::allocator> { };
+
+
+/**
+ * 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, typename Allocator>
+class vertex_vector_impl
+{
+    typedef std::vector<Vertex, Allocator> vertex_store;
+public:
+    typedef std::size_t vertex_descriptor;
+
+    typedef Vertex vertex_type;
+    typedef typename Vertex::vertex_properties vertex_properties;
+    typedef typename vertex_store::size_type size_type;
+    typedef indexed_vertex_iterator<vertex_store> iterator;
+    typedef std::pair<iterator, iterator> range;
+
+    // Constructors
+    vertex_vector_impl();
+
+    // Add/remove vertex.
+    vertex_descriptor add();
+    vertex_descriptor add(vertex_properties const& vp);
+
+    // Number of vertices.
+    size_type size() const;
+
+    // Vertex iteration.
+    range vertices() const;
+    iterator begin() const;
+    iterator end() 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;
+};
+
+#define BOOST_GRAPHS_VV_PARAMS \
+    typename V, typename A
+
+template <BOOST_GRAPHS_VV_PARAMS>
+vertex_vector_impl<V,A>::vertex_vector_impl()
+    : _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 <BOOST_GRAPHS_VV_PARAMS>
+typename vertex_vector_impl<V,A>::vertex_descriptor
+vertex_vector_impl<V,A>::add()
+{
+    return add(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 <BOOST_GRAPHS_VV_PARAMS>
+typename vertex_vector_impl<V,A>::vertex_descriptor
+vertex_vector_impl<V,A>::add(vertex_properties const& vp)
+{
+    // 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 store.
+ */
+template <BOOST_GRAPHS_VV_PARAMS>
+typename vertex_vector_impl<V,A>::size_type
+vertex_vector_impl<V,A>::size() const
+{
+    return _verts.size();
+}
+
+/**
+ * Get access to the underlying vertex.
+ */
+template <BOOST_GRAPHS_VV_PARAMS>
+typename vertex_vector_impl<V,A>::vertex_type&
+vertex_vector_impl<V,A>::vertex(vertex_descriptor v)
+{
+    return _verts[v];
+}
+
+/**
+ * Get access to the underlying vertex.
+ */
+template <BOOST_GRAPHS_VV_PARAMS>
+typename vertex_vector_impl<V,A>::vertex_type const&
+vertex_vector_impl<V,A>::vertex(vertex_descriptor v) const
+{
+    return _verts[v];
+}
+
+#undef BOOST_GRAPHS_VV_PARAMS
+
+#if 0
+
+/**
+ * Return the number of vertices in the vertex store.
+ *
+ * @complexity constant
+ */
+template <typename V, template <typename> class A>
+typename vertex_vector_impl<V,A>::vertices_size_type
+vertex_vector_impl<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 vertex_vector_impl<V,A>::vertex_iterator,
+    typename vertex_vector_impl<V,A>::vertex_iterator
+>
+vertex_vector_impl<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 vertex_vector_impl<V,A>::vertex_iterator
+vertex_vector_impl<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 vertex_vector_impl<V,A>::vertex_iterator
+vertex_vector_impl<V,A>::end_vertices() const
+{
+    return vertex_iterator(_verts, _verts.end());
+}
+
+
+/**
+ * Get access to the properties of the given vertex.
+ */
+template <typename V, template <typename> class A>
+typename vertex_vector_impl<V,A>::vertex_properties&
+vertex_vector_impl<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 vertex_vector_impl<V,A>::vertex_properties const&
+vertex_vector_impl<V,A>::properties(vertex_descriptor v) const
+{
+    return *vertex(v);
+}
+
+#endif
+
+#endif

Added: sandbox/SOC/2008/graphs/branches/tue/libs/graphs/Jamfile
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/libs/graphs/Jamfile	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,4 @@
+
+exe un : un.cpp : <include>../../ <include>/usr/local/include ;
+
+exe test : test.cpp ;

Added: sandbox/SOC/2008/graphs/branches/tue/libs/graphs/Jamroot
==============================================================================

Added: sandbox/SOC/2008/graphs/branches/tue/libs/graphs/demangle.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/libs/graphs/demangle.hpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,14 @@
+
+#ifndef DEMANGLE_HPP
+#define DEMANGLE_HPP
+
+#include <string>
+#include <typeinfo>
+#include <cxxabi.h>
+
+std::string demangle(std::string const& name)
+{
+    return std::string(abi::__cxa_demangle(name.c_str(), 0, 0, 0));
+}
+
+#endif

Added: sandbox/SOC/2008/graphs/branches/tue/libs/graphs/test.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/libs/graphs/test.cpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,13 @@
+
+#include <list>
+
+using namespace std;
+
+int main()
+{
+    list<int> a;
+    list<int>::iterator x = a.begin(), y = a.end();
+    // x < y;
+    return 0;
+}
+

Added: sandbox/SOC/2008/graphs/branches/tue/libs/graphs/un.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/tue/libs/graphs/un.cpp	2008-06-06 08:00:06 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,73 @@
+
+#include <iostream>
+#include <set>
+
+#include <boost/graphs/undirected_graph.hpp>
+
+#include "demangle.hpp"
+
+using namespace std;
+
+struct City { };
+struct Road { };
+
+void list_list();
+void vec_vec();
+
+template <typename Graph>
+void print_types(const Graph&)
+{
+    cout << demangle(typeid(typename Graph::property_descriptor).name()) << endl;
+    cout << demangle(typeid(typename Graph::vertex_descriptor).name()) << endl;
+    cout << demangle(typeid(typename Graph::edge_descriptor).name()) << endl;
+    cout << demangle(typeid(typename Graph::property_store).name()) << endl;
+    cout << demangle(typeid(typename Graph::vertex_store).name()) << endl;
+    cout << demangle(typeid(typename Graph::incidence_store).name()) << endl;
+}
+
+template <typename Graph>
+void add_verts(Graph& g)
+{
+    for(int i = 0; i < 10; ++i) {
+        g.add_vertex();
+    }
+    cout << "num_verts: " << g.num_vertices() << std::endl;
+}
+
+template <typename Graph>
+void add_edges(Graph& g)
+{
+    typename Graph::vertex_descriptor u = g.add_vertex();
+    typename Graph::vertex_descriptor v = g.add_vertex();
+    g.add_edge(u, v);
+}
+
+int main()
+{
+    list_list();
+    cout << endl << endl;
+    vec_vec();
+    cout << endl << endl;
+
+    return 0;
+}
+
+void list_list()
+{
+    typedef undirected_graph<City, Road, vertex_list, edge_list> Graph;
+
+    Graph g;
+    cout << demangle(typeid(Graph).name()) << endl;
+    add_verts(g);
+}
+
+void vec_vec()
+{
+    typedef undirected_graph<City, Road, vertex_vector, edge_vector> Graph;
+
+    Graph g;
+    cout << demangle(typeid(Graph).name()) << endl;
+    add_verts(g);
+    add_edges(g);
+}
+