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

From: asutton_at_[hidden]
Date: 2008-06-26 20:18:07

Author: asutton
Date: 2008-06-26 20:18:05 EDT (Thu, 26 Jun 2008)
New Revision: 46757
URL: http://svn.boost.org/trac/boost/changeset/46757

Log:
Rewriting big chunks of things to try and make them work better.

Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp                   |     9 +++                                     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp                      |    10 +--                                     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp                   |    64 ++++++++++------------                  
   sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_properties.hpp |     1                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp                 |    89 +++++++++++++++++++++++++++----         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp                 |   111 ++++++++++++++++++++------------------- 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp                |    28 +++++----                               
   sandbox/SOC/2008/graphs/trunk/boost/graphs/unordered_pair.hpp                  |    55 +++++++++++++------                     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp               |     2                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp                   |     2                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/edge.cpp                             |     4 +                                       
   sandbox/SOC/2008/graphs/trunk/libs/graphs/props.cpp                            |    15 ++++-                                   
   sandbox/SOC/2008/graphs/trunk/libs/graphs/square.hpp                           |    23 +++++++                                 
   13 files changed, 267 insertions(+), 146 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp	2008-06-26 20:18:05 EDT (Thu, 26 Jun 2008)
@@ -36,6 +36,15 @@
     { }
     //@}
 
+   /**
+     * Return a value that uniquely describes the edge. This is basically going
+     * to be the address of the property. Note that directed graphs can't use
+     * indexed exterior edge properties because there's no method for maintaining
+     * a global edge index.
+     */
+    inline edge_properties* get() const
+    { return &properties(); }
+
     /** Return the source of the edge. */
     inline vertex_descriptor source() const
     { return _src; }

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp	2008-06-26 20:18:05 EDT (Thu, 26 Jun 2008)
@@ -68,13 +68,9 @@
 
 template <typename Graph, typename Property>
 struct exterior_edge_property
-    : choose_container<
-            typename Graph::edge_store_selector, typename Graph::edge_descriptor, Property
-        >::type
-{
-    typedef typename choose_container<
-            typename Graph::edge_store_selector, typename Graph::edge_descriptor, Property
-        >::type base_type;
+    : hashed_property_container<typename Graph::edge_descriptor, Property>
+{
+    typedef hashed_property_container<typename Graph::edge_descriptor, Property> base_type;
 
     exterior_edge_property(const Graph& g)
         : base_type(g.num_edges())

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp	2008-06-26 20:18:05 EDT (Thu, 26 Jun 2008)
@@ -28,7 +28,7 @@
     typedef typename Props::second_type first_iterator;
     typedef typename Props::third_type second_iterator;
 public:
-    typedef typename store_type::const_iterator iterator;
+    typedef typename store_type::iterator iterator;
     typedef typename store_type::size_type size_type;
     typedef proplist_descriptor<typename store_type::iterator> property_descriptor;
 
@@ -56,6 +56,10 @@
         d.iter->third.put(tgt);
     }
 
+    /** Convert an iterator to a descriptor. */
+    inline property_descriptor describe(iterator i) const
+    { return i; }
+
     /** Return the number of properties. */
     inline size_type size() const
     { return _size; }
@@ -67,8 +71,8 @@
     { return _props.end(); }
 
 private:
-    store_type  _props;
-    size_type   _size;
+    mutable store_type  _props;
+    size_type           _size;
 };
 
 /**
@@ -89,8 +93,7 @@
 property_list<P,A>::add(edge_properties const& p)
 {
     ++_size;
-    return _props.insert(_props.end(),
-                          make_triple(p, first_iterator(), second_iterator()));
+    return _props.insert(_props.end(), make_triple(p, first_iterator(), second_iterator()));
 }
 
 /**
@@ -117,6 +120,8 @@
 template <typename Iter>
 struct proplist_descriptor
 {
+    typedef typename Iter::pointer value_type;
+
     inline proplist_descriptor()
         : iter()
     { }
@@ -125,41 +130,30 @@
         : iter(iter)
     { }
 
-    inline bool operator==(proplist_descriptor const& x) const
-    { return iter == x.iter; }
-
-    inline bool operator<(proplist_descriptor const& x) const
-    { return &*iter < &*x.iter; }
+    inline value_type get() const
+    { return &*iter; }
 
     Iter iter;
 };
 
+template <typename I>
+inline bool
+operator==(proplist_descriptor<I> const& a, proplist_descriptor<I> const& b)
+{ return a.iter == b.iter; }
+
+template <typename I>
+inline bool
+operator<(proplist_descriptor<I> const& a, proplist_descriptor<I> const& b)
+{ return a.get() < b.get(); }
 
-// This helper type is used to erase global edge properties during edge removal
-// of undirected graphs.
-template <typename PropList>
-struct property_eraser
-{
-    property_eraser(PropList& props)
-        : props(props)
-    { }
-
-    template <typename PropDesc>
-    void operator()(PropDesc p)
-    { props.remove(p); }
-
-    PropList& props;
-};
-
-// The noop eraser does nothing.
-struct noop_eraser
-{
-    noop_eraser() { }
-
-    template <typename PropDesc>
-    void operator()(PropDesc)
-    { }
-};
+/**
+ * Hashing a property descriptor returns the hash value over the address of
+ * the property object pointed at by the descriptor inside the iterator.
+ */
+template <typename Iter>
+inline std::size_t
+hash_value(proplist_descriptor<Iter> const& x)
+{ return boost::hash_value(x.get()); }
 
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_properties.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_properties.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_map/indexed_properties.hpp	2008-06-26 20:18:05 EDT (Thu, 26 Jun 2008)
@@ -113,4 +113,5 @@
     container_type& data;
 };
 
+
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp	2008-06-26 20:18:05 EDT (Thu, 26 Jun 2008)
@@ -6,10 +6,22 @@
 
 #include "triple.hpp"
 
-// 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 Store> class propvec_descriptor;
 
+// NOTE: Property stores hold two additional values. Right now, they contain
+// vertex descriptors, but would ideally by "iterators" into the incidence store
+// to make remove operations involing recipricol edge stubs more efficient.
+//
+// This really highlights the need for something like a "stable" iterator that
+// isn't invalidated by little things like complete reallocations and copies.
+// The problem can be stated as: how do you describe a never-invalidating
+// iterator into arbitrary containers and, can we map this onto iterators.
+
+/**
+ * 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
 {
@@ -21,9 +33,9 @@
     typedef typename Props::second_type first_iterator;
     typedef typename Props::third_type second_iterator;
 public:
-    typedef typename store_type::const_iterator iterator;
+    typedef typename store_type::iterator iterator;
     typedef typename store_type::size_type size_type;
-    typedef std::size_t property_descriptor;
+    typedef propvec_descriptor<store_type> property_descriptor;
 
     inline property_vector()
         : _props()
@@ -33,16 +45,21 @@
     property_descriptor add(edge_properties const&);
 
     inline edge_properties& properties(property_descriptor d)
-    { return _props[d].first; }
+    { return d->first; }
 
-    /** Bind iterators into the incidence lists into the global property. */
-    template <typename Iter>
-    void bind(property_descriptor d, Iter src, Iter tgt)
+    /** Bind descriptors into the incidence lists into the global property. */
+    template <typename VertexDesc>
+    void bind(property_descriptor d, VertexDesc src, VertexDesc tgt)
     {
-        _props[d].second.put(src);
-        _props[d].third.put(tgt);
+        BOOST_ASSERT(&_props == d.store);
+        _props[d.off].second.put(src);
+        _props[d.off].third.put(tgt);
     }
 
+    /** Convert an iterator to a descriptor. */
+    inline property_descriptor describe(iterator i) const
+    { return property_descriptor(&_props, std::distance(_props.begin(), i)); }
+
     /** Return the number of properties in the store. */
     inline size_type size() const
     { return _props.size(); }
@@ -54,7 +71,7 @@
     { return _props.end(); }
 
 private:
-    store_type _props;
+    mutable store_type _props;
 };
 
 
@@ -70,8 +87,54 @@
 property_vector<P,A>::add(edge_properties const& p)
 {
     _props.push_back(make_triple(p, first_iterator(), second_iterator()));
-    return _props.size() - 1;
+    return property_descriptor(&_props, _props.size() - 1);
 }
 
+/**
+ * The propvec descriptor provides an opaque reference into the property list
+ * for undirected graphs.
+ */
+template <typename Store>
+struct propvec_descriptor
+{
+    typedef Store store_type;
+    typedef typename Store::size_type value_type;
+
+    propvec_descriptor()
+        : store(0), off(value_type(-1))
+    { }
+
+    propvec_descriptor(store_type* store, value_type n)
+        : store(store), off(n)
+    { }
+
+    value_type get() const
+    { return off; }
+
+    store_type* store;
+    value_type  off;
+};
+
+template <typename S>
+inline bool
+operator==(propvec_descriptor<S> const& a, propvec_descriptor<S> const& b)
+{ return a.store == b.store && a.off == b.off; }
+
+template <typename S>
+inline bool
+operator<(propvec_descriptor<S> const& a, propvec_descriptor<S> const& b)
+{ return a.get() < b.get(); }
+
+/**
+ * Hashing a property descriptor returns the hash value over the address of
+ * the property object pointed at by the descriptor inside the iterator.
+ */
+template <typename S>
+inline std::size_t
+hash_value(propvec_descriptor<S> const& x)
+{ return boost::hash_value(x.get()); }
+
+
+
 #endif
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp	2008-06-26 20:18:05 EDT (Thu, 26 Jun 2008)
@@ -20,20 +20,33 @@
     typedef PropDesc property_descriptor;
     typedef unordered_pair<vertex_descriptor> edge_pair;
 
-    inline undirected_edge();
-    inline undirected_edge(vertex_descriptor u, vertex_descriptor v, property_descriptor p);
+    inline undirected_edge()
+        : ends(), prop()
+    { }
+
+    inline undirected_edge(vertex_descriptor u, vertex_descriptor v, property_descriptor p)
+        : ends(u, v), prop(p)
+    { }
+
+    /**
+     * Return the underlying value of the property that uniquely describes the
+     * edge. This is primarily used to support mapping applications for exterior
+     * edge properties.
+     */
+    inline typename property_descriptor::value_type get() const
+    { return prop.get(); }
 
     inline property_descriptor properties() const
-    { return _prop; }
+    { return prop; }
 
     inline edge_pair const& edge() const
-    { return _edge; }
+    { return ends; }
 
     inline vertex_descriptor first() const
-    { return _edge.first(); }
+    { return ends.first(); }
 
     inline vertex_descriptor second() const
-    { return _edge.second(); }
+    { return ends.second(); }
 
     /** Return true if the edge connects the two vertices. */
     inline bool connects(vertex_descriptor u, vertex_descriptor v) const
@@ -45,54 +58,39 @@
     inline vertex_descriptor opposite(vertex_descriptor v)
     { return v == first() ? second() : first(); }
 
-    inline bool operator==(undirected_edge const& x);
-    inline bool operator!=(undirected_edge const& x);
-    inline bool operator<(undirected_edge const& x);
-
-private:
-    edge_pair _edge;
-    PropDesc _prop;
+    edge_pair               ends;
+    property_descriptor     prop;
 };
 
-template <typename VD, typename PD>
-undirected_edge<VD,PD>::undirected_edge()
-    : _edge()
-    , _prop()
-{ }
-
-template <typename VD, typename PD>
-undirected_edge<VD,PD>::undirected_edge(vertex_descriptor u,
-                                        vertex_descriptor v,
-                                        property_descriptor p)
-    : _edge(u, v)
-    , _prop(p)
-{ }
-
-template <typename VD, typename PD>
-bool
-undirected_edge<VD,PD>::operator==(undirected_edge const& x)
-{
-    return _edge == x._edge && _prop == x._prop;
-}
+template <typename V, typename P>
+inline bool
+operator==(undirected_edge<V,P> const& a, undirected_edge<V,P> const& b)
+{ return a.ends == b.ends && a.prop == b.prop; }
 
-template <typename VD, typename PD>
-bool
-undirected_edge<VD,PD>::operator!=(undirected_edge const& x)
-{
-    return !(*this->operator==(x));
-}
+template <typename V, typename P>
+inline bool
+operator!=(undirected_edge<V,P> const& a, undirected_edge<V,P> const& b)
+{ return !(a == b); }
 
-template <typename VD, typename PD>
-bool
-undirected_edge<VD,PD>::operator<(undirected_edge const& x)
-{
-    return _edge < x._edge || (!(x._edge < _edge) && _prop < x._prop);
-}
+template <typename V, typename P>
+inline bool
+operator<(undirected_edge<V,P> const& a, undirected_edge<V,P> const& b)
+{ return std::make_pair(a.ends, a.prop) < std::make_pair(b.ends < b.props); }
 
-template <typename VD, typename PD>
-std::ostream& operator<<(std::ostream& os, undirected_edge<VD,PD> const& e)
+template <typename V, typename P>
+std::ostream& operator<<(std::ostream& os, undirected_edge<V,P> const& e)
 { return os << "{" << e.first() << " " << e.second() << "}"; }
 
+template <typename V, typename P>
+inline std::size_t
+hash_value(undirected_edge<V,P> const& e)
+{
+    std::size_t seed;
+    boost::hash_combine(seed, e.ends);
+    boost::hash_combine(seed, e.prop);
+    return seed;
+}
+
 /**
  * The undirected edge iterator simply wraps the iterator over the global edge
  * property store of undirected graphs.
@@ -102,8 +100,11 @@
 {
     typedef typename Graph::property_store store_type;
     typedef typename Graph::vertex_type vertex_type;
+    typedef typename Graph::property_descriptor property_descriptor;
+    typedef typename Graph::vertex_descriptor vertex_descriptor;
+
+    // This is an iterator directly into the global property store.
     typedef typename store_type::iterator prop_iterator;
-    typedef typename vertex_type::iterator edge_iterator;
 
     typedef std::forward_iterator_tag iterator_category;
     typedef std::size_t size_type;
@@ -112,8 +113,8 @@
     typedef value_type reference;
     typedef value_type pointer;
 
-    undirected_edge_iterator(prop_iterator i)
-        : iter(i)
+    undirected_edge_iterator(store_type const& store, prop_iterator i)
+        : store(&store), iter(i)
     { }
 
     inline undirected_edge_iterator& operator++()
@@ -121,12 +122,14 @@
 
     inline reference operator*() const
     {
-        edge_iterator p = iter->second.template get<edge_iterator>();
-        edge_iterator q = iter->third.template get<edge_iterator>();
-        return reference(p->first, q->first, iter->first);
+        // Grab the vertex descrip
+        vertex_descriptor u = iter->second.template get<vertex_descriptor>();
+        vertex_descriptor v = iter->third.template get<vertex_descriptor>();
+        return reference(u, v, store->describe(iter));
     }
 
-    prop_iterator iter;
+    store_type const*   store;
+    prop_iterator       iter;
 };
 
 template <typename Graph>

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp	2008-06-26 20:18:05 EDT (Thu, 26 Jun 2008)
@@ -365,12 +365,10 @@
                                         vertex_descriptor v,
                                         edge_properties const& ep)
 {
-    // To add the edge or not... We need to consult the virtual edge set
-    // to determine whether or not this edge already exists. For multigraph
-    // stores, this should always return false. The protocol is: ask the source
-    // if it can be connected to the target. If so, connect them. If they're
-    // connected, return the existing edge. If they can't be connected, return
-    // a null descriptor.
+    // To add the edge or not... The protocol is: ask the source if it can be
+    // connected to the target. If so, connect them. If they're connected,
+    // return the existing edge. If they can't be connected, return a null
+    // descriptor.
     reorder(u, v);
     vertex_type& src = _verts.vertex(u);
     vertex_type& tgt = _verts.vertex(v);
@@ -382,9 +380,12 @@
         // iterator.
         if(ins.first == src.end()) {
             property_descriptor p = _props.add(ep);
-            typename vertex_type::iterator i = src.connect(v, p);
-            typename vertex_type::iterator j = tgt.connect(u, p);
-            _props.bind(p, i, j);
+            src.connect(v, p);
+            tgt.connect(u, p);
+
+            // Bind the iterators back into the property store and return an
+            // edge descriptor.
+            _props.bind(p, u, v);
             return edge_descriptor(u, v, p);
         }
         else {
@@ -445,9 +446,10 @@
 std::pair<typename undirected_graph<VP,EP,VS,ES>::edge_descriptor, bool>
 undirected_graph<VP,EP,VS,ES>::edge(vertex_descriptor u, vertex_descriptor v) const
 {
-    vertex_type& src = _verts.vertex(u);
+    reorder(u, v);
+    vertex_type const& src = _verts.vertex(u);
     typename vertex_type::iterator i = src.find(v);
-    return i == src.end() ?
+    return i != src.end() ?
         std::make_pair(edge_descriptor(u, v, i->second), true) :
         std::make_pair(edge_descriptor(), false);
 }
@@ -647,13 +649,13 @@
 template <BOOST_GRAPH_UG_PARAMS>
 typename undirected_graph<VP,EP,VS,ES>::edge_iterator
 undirected_graph<VP,EP,VS,ES>::begin_edges() const
-{ return _props.begin(); }
+{ return edge_iterator(_props, _props.begin()); }
 
 /** Return an iterator past the end of the edges. */
 template <BOOST_GRAPH_UG_PARAMS>
 typename undirected_graph<VP,EP,VS,ES>::edge_iterator
 undirected_graph<VP,EP,VS,ES>::end_edges() const
-{ return _props.end(); }
+{ return edge_iterator(_props, _props.end()); }
 
 /** Return an iterator range over the edges in the graph. */
 template <BOOST_GRAPH_UG_PARAMS>

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/unordered_pair.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/unordered_pair.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/unordered_pair.hpp	2008-06-26 20:18:05 EDT (Thu, 26 Jun 2008)
@@ -4,6 +4,8 @@
 
 #include <functional>
 
+#include <boost/functional/hash.hpp>
+
 /**
  * The unordered pair template provides a homogenously typed 2-element
  * whose values are unordered. By unordered, we simply mean that two pairs
@@ -102,25 +104,45 @@
 
 // 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
+inline bool
+operator==(unordered_pair<T,C> const& a, unordered_pair<T,C> const& b)
+{ return a.first() == b.first() && a.second() == b.second(); }
+
+template <typename T, typename C>
+inline bool
+operator!=(unordered_pair<T,C> const& a, unordered_pair<T,C> const& b)
+{ return !(a == b); }
+
+template <typename T, typename C>
+inline bool
 operator<(unordered_pair<T,C> const& a, unordered_pair<T,C> const& b)
-{
-    C c;
-    return c(a.first(), b.first()) ||
-           (!c(b.first(), a.first()) &&
-             c(a.second(), b.second()));
-}
+{ return std::make_pair(a.first(), a.second()) < std::make_pair(b.first(), b.second()); }
 
 template <typename T, typename C>
-bool
-operator==(unordered_pair<T,C> const& a, unordered_pair<T,C> const& b)
+inline bool
+operator>(unordered_pair<T,C> const& a, unordered_pair<T,C> const& b)
+{ return b < a; }
+
+template <typename T, typename C>
+inline bool
+operator<=(unordered_pair<T,C> const& a, unordered_pair<T,C> const& b)
+{ return !(b < a); }
+
+template <typename T, typename C>
+inline bool
+operator>=(unordered_pair<T,C> const& a, unordered_pair<T,C> const& b)
+{ return !(a < b); }
+
+/** Compute the hash value of the unordered pair. */
+template <typename T, typename C>
+inline std::size_t
+hash_value(unordered_pair<T,C> const& x)
 {
-    return a.first() == b.first() && a.second() == b.second();
+    std::size_t seed = 0;
+    boost::hash_combine(seed, x.first());
+    boost::hash_combine(seed, x.second());
+    return seed;
 }
 
 /**
@@ -129,10 +151,7 @@
 template <typename T>
 unordered_pair<T>
 make_unordered_pair(T const& f, T const& s)
-{
-    unordered_pair<T> x(f, s);
-    return x;
-}
+{ return unordered_pair<T>(f, s); }
 
 /**
  * A swap-like sort function that will "unorder" two objects.

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp	2008-06-26 20:18:05 EDT (Thu, 26 Jun 2008)
@@ -110,10 +110,10 @@
 std::ostream& operator<<(std::ostream& os, const basic_vertex_descriptor<D>& v)
 { return os << v.get(); }
 
+/** Compute the hash value of the descriptor. */
 template <typename D>
 std::size_t hash_value(basic_vertex_descriptor<D> const& x)
 { return boost::hash_value(x.get()); }
 
-
 #endif
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp	2008-06-26 20:18:05 EDT (Thu, 26 Jun 2008)
@@ -139,7 +139,7 @@
  * Add a vertex to the store with the given properties. Adding a vertex does
  * not invalidate any other descriptors.
  *
- * @complexity O(~1)
+ * @complexity O(1)
  */
 template <typename V, typename A>
 typename vertex_vector_impl<V,A>::vertex_descriptor

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/edge.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/edge.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/edge.cpp	2008-06-26 20:18:05 EDT (Thu, 26 Jun 2008)
@@ -4,6 +4,7 @@
 #include <boost/graphs/directed_graph.hpp>
 #include <boost/graphs/undirected_graph.hpp>
 
+#include "demangle.hpp"
 #include "square.hpp"
 
 using namespace std;
@@ -18,12 +19,14 @@
 int main()
 {
     directed();
+    undirected();
 
     return 0;
 }
 
 void directed()
 {
+    cout << "--- directed (vec/vec) ---" << endl;
     typedef directed_graph<int, int, vvec, evec> Graph;
     Graph g;
     make_square(g);
@@ -36,6 +39,7 @@
 
 void undirected()
 {
+    cout << "--- undirected (vec/vec) ---" << endl;
     typedef undirected_graph<int, int, vvec, evec> Graph;
     Graph g;
     make_square(g);

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/props.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/props.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/props.cpp	2008-06-26 20:18:05 EDT (Thu, 26 Jun 2008)
@@ -34,8 +34,17 @@
 template <typename Graph>
 void test_ext_vertex_props(Graph& g)
 {
-    exterior_vertex_property<Graph, double> vp(g, 5.0);
-    cout << demangle<typename exterior_vertex_property<Graph, double>::base_type>() << endl;
+    typedef exterior_vertex_property<Graph, double> VertexWeight;
+    typedef exterior_edge_property<Graph, double> EdgeWeight;
+
+    VertexWeight vp(g, 5.0);
+    EdgeWeight ep(g, 1.0);
+
+    cout << "vertex using: " << demangle<typename VertexWeight::base_type>() << endl;
+    cout << "edge using: " << demangle<typename EdgeWeight::base_type>() << endl;
+
+    cout << ep[*g.begin_edges()] << endl;
+    cout << ep.data.size() << endl;
 }
 
 int main()
@@ -59,5 +68,5 @@
     typedef undirected_graph<int, int, vertex_list<>, edge_list<> > Graph;
     Graph g;
     make_square(g);
-    test_ext_vertex_props(g);
+    // test_ext_vertex_props(g);
 }

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/square.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/square.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/square.hpp	2008-06-26 20:18:05 EDT (Thu, 26 Jun 2008)
@@ -2,8 +2,9 @@
 #ifndef SQUARE_HPP
 #define SQUARE_HPP
 
-// Make a K4 square
+#include <boost/assert.hpp>
 
+// Make a K4 square
 template <typename G>
 void make_square(G& g)
 {
@@ -13,6 +14,26 @@
     g.add_edge(v[3], v[0], 3);
     g.add_edge(v[0], v[2], 4);
     g.add_edge(v[1], v[3], 5);
+
+    // Check the basic structure...
+    BOOST_ASSERT(g.num_vertices() == 4);
+    BOOST_ASSERT(g.num_edges() == 6);
+
+    // Make sure that this actually does what I think it does. It should have
+    // the following edges:
+    // (0,1), (1,2), (2,3), (3,0), (0,2), and (1,3)
+    BOOST_ASSERT(g.edge(v[0], v[1]).second);
+    BOOST_ASSERT(g.edge(v[1], v[2]).second);
+    BOOST_ASSERT(g.edge(v[2], v[3]).second);
+    BOOST_ASSERT(g.edge(v[3], v[0]).second);
+    BOOST_ASSERT(g.edge(v[0], v[2]).second);
+    BOOST_ASSERT(g.edge(v[1], v[3]).second);
+
+    // Just to check again, assert that the degrees are correct.
+    BOOST_ASSERT(g.degree(v[0]) == 3);
+    BOOST_ASSERT(g.degree(v[1]) == 3);
+    BOOST_ASSERT(g.degree(v[2]) == 3);
+    BOOST_ASSERT(g.degree(v[3]) == 3);
 }
 
 #endif