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

From: asutton_at_[hidden]
Date: 2008-06-25 12:38:48

Author: asutton
Date: 2008-06-25 12:38:47 EDT (Wed, 25 Jun 2008)
New Revision: 46684
URL: http://svn.boost.org/trac/boost/changeset/46684

Log:
Rewrote the proeprty stores to include back references to the incidence
stores of each vertex. This makes edge iteration trivial and will speed
up a number of edge operations.

Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp         |     6 ++-                                     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp          |     9 +++-                                    
   sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp       |     9 +++-                                    
   sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp    |     4 +-                                      
   sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp     |     4 +-                                      
   sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp  |     9 +++-                                    
   sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp     |    77 ++++++++++++++++----------------------- 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp   |    61 ++++++++++++++++---------------         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp   |    46 +++++++++++++++++++++++                 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp  |    61 ++++++++++++++++++-------------         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp |     6 +-                                      
   sandbox/SOC/2008/graphs/trunk/libs/graphs/edge.cpp               |    22 ++++++-----                             
   12 files changed, 188 insertions(+), 126 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp	2008-06-25 12:38:47 EDT (Wed, 25 Jun 2008)
@@ -29,8 +29,10 @@
     template <typename EdgeProps>
     struct property_store
     {
-        typedef SecondAlloc<EdgeProps> allocator;
-        typedef property_list<EdgeProps, allocator> type;
+        typedef placeholder<sizeof(typename std::list<int>::iterator)> dummy_type;
+        typedef triple<EdgeProps, dummy_type, dummy_type> property;
+        typedef SecondAlloc<property> allocator;
+        typedef property_list<property, allocator> type;
     };
 
     // The incidence store metafunction generates the per-vertex storage type

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp	2008-06-25 12:38:47 EDT (Wed, 25 Jun 2008)
@@ -2,6 +2,9 @@
 #ifndef EDGE_SET_HPP
 #define EDGE_SET_HPP
 
+#include "triple.hpp"
+#include "placeholder.hpp"
+
 #include "property_list.hpp"
 #include "incidence_set.hpp"
 #include "out_set.hpp"
@@ -27,8 +30,10 @@
     template <typename EdgeProps>
     struct property_store
     {
-        typedef SecondAlloc<EdgeProps> allocator;
-        typedef property_list<EdgeProps, allocator> type;
+        typedef placeholder<sizeof(std::list<int>::iterator)> dummy_type;
+        typedef triple<EdgeProps, dummy_type, dummy_type> property;
+        typedef SecondAlloc<property> allocator;
+        typedef property_list<property, allocator> type;
     };
 
     // The incidence store metafunction generates the per-vertex stores for

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp	2008-06-25 12:38:47 EDT (Wed, 25 Jun 2008)
@@ -45,8 +45,13 @@
     template <typename EdgeProps>
     struct property_store
     {
-        typedef SecondAlloc<EdgeProps> property_allocator;
-        typedef property_vector<EdgeProps, property_allocator > type;
+        // Define a dummy type that will eventually container iterators into
+        // an incidence container. Use this as part of the triple for each
+        // edge store - the properties and "out-facing" iterators.
+        typedef placeholder<sizeof(typename std::vector<int>::iterator)> dummy_type;
+        typedef triple<EdgeProps, dummy_type, dummy_type> property;
+        typedef SecondAlloc<property> allocator;
+        typedef property_vector<property, allocator> type;
     };
 
     // The incidence store metafunction generates the type of vector used to

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp	2008-06-25 12:38:47 EDT (Wed, 25 Jun 2008)
@@ -43,10 +43,10 @@
      * Add a vertex to the list.
      * @complexity O(1)
      */
-    inline void add(incidence_pair p)
+    inline iterator add(incidence_pair p)
     {
         ++_size;
-        _edges.push_back(p);
+        return _edges.insert(_edges.end(), p);
     }
 
     /**

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp	2008-06-25 12:38:47 EDT (Wed, 25 Jun 2008)
@@ -50,8 +50,8 @@
      * Add the incidence pair to the vertex.
      * @complexity O(lg(deg(v)))
      */
-    inline void add(incidence_pair p)
-    { _edges.insert(p); }
+    inline iterator add(incidence_pair p)
+    { return _edges.insert(p).first; }
 
     /**
      * Find the incidence pair.

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp	2008-06-25 12:38:47 EDT (Wed, 25 Jun 2008)
@@ -4,6 +4,8 @@
 
 #include <vector>
 
+#include <boost/next_prior.hpp>
+
 /**
  * The incidence vector stores incident "edges" of a vertex. In actuality,
  * this stores pairs containing an adjacent vertex descriptor and a property
@@ -40,8 +42,11 @@
     { return make_pair(_edges.end(), true); }
 
     /** Add the incidence pair to the vector. */
-    void add(incidence_pair p)
-    { _edges.push_back(p); }
+    iterator add(incidence_pair p)
+    {
+        _edges.push_back(p);
+        return boost::prior(_edges.end());
+    }
 
     /** Find the edge with the given vertex. */
     inline iterator find(vertex_descriptor v) const

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-25 12:38:47 EDT (Wed, 25 Jun 2008)
@@ -22,58 +22,55 @@
 {
     typedef std::list<Props, Alloc> store_type;
 public:
+    typedef Props properties_triple;
+    typedef typename Props::first_type edge_properties;
+private:
+    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::size_type size_type;
-
-    typedef Props property_type;
     typedef proplist_descriptor<typename store_type::iterator> property_descriptor;
 
-    inline property_list();
+    inline property_list()
+        : _props()
+        , _size(0)
+    { }
 
     // Add properties
     inline property_descriptor add();
-    inline property_descriptor add(property_type const&);
+    inline property_descriptor add(edge_properties const&);
 
     // Remove properties
     inline void remove(property_descriptor);
 
     // Property access.
-    inline property_type& properties(property_descriptor);
+    inline edge_properties& properties(property_descriptor d)
+    { return d.iter->first; }
+
+    /** Bind iterators into the incidence lists into the global property. */
+    template <typename Iter>
+    void bind(property_descriptor d, Iter src, Iter tgt)
+    {
+        d.iter->second.put(src);
+        d.iter->third.put(tgt);
+    }
 
     /** Return the number of properties. */
     inline size_type size() const
     { return _size; }
 
+    inline iterator begin() const
+    { return _props.begin(); }
+
+    inline iterator end() const
+    { return _props.end(); }
+
 private:
     store_type  _props;
     size_type   _size;
 };
 
-// TODO: This eventually needs to be specialized for empty edges. Basically, if
-// you don't want edges, then we can just hand out integers that for each
-// edge - probably.
-#if 0
-
-/**
- * Partially specialize the property list for the case where the user does
- * not want properties. This will completely remove the property list from
- * the graph, instead creating a simple index enumerator.
- */
-template <typename Alloc>
-class property_list<none, Alloc>
-{
-public:
-    typedef std::size_t property_descriptor;
-};
-
-#endif
-
-
-template <typename P, typename A>
-property_list<P,A>::property_list()
-    : _props()
-    , _size(0)
-{ }
-
 /**
  * Add an empty or default property to the list.
  */
@@ -81,8 +78,7 @@
 typename property_list<P,A>::property_descriptor
 property_list<P,A>::add()
 {
-    ++_size;
-    return add(property_type());
+    return add(edge_properties());
 }
 
 /**
@@ -90,10 +86,11 @@
  */
 template <typename P, typename A>
 typename property_list<P,A>::property_descriptor
-property_list<P,A>::add(property_type const& p)
+property_list<P,A>::add(edge_properties const& p)
 {
     ++_size;
-    return _props.insert(_props.end(), p);
+    return _props.insert(_props.end(),
+                          make_triple(p, first_iterator(), second_iterator()));
 }
 
 /**
@@ -111,16 +108,6 @@
 }
 
 /**
- * Return the properties corresponding to the given descriptor.
- */
-template <typename P, typename A>
-typename property_list<P,A>::property_type&
-property_list<P,A>::properties(property_descriptor p)
-{
-    return *p.iter;
-}
-
-/**
  * 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 elements. This is to say that

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-25 12:38:47 EDT (Wed, 25 Jun 2008)
@@ -4,6 +4,8 @@
 
 #include <vector>
 
+#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.
@@ -13,62 +15,63 @@
 {
     typedef std::vector<Props, Alloc> store_type;
 public:
+    typedef Props properties_triple;
+    typedef typename Props::first_type edge_properties;
+private:
+    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::size_type size_type;
-
-    typedef Props property_type;
     typedef std::size_t property_descriptor;
 
-    property_vector();
+    inline property_vector()
+        : _props()
+    { }
 
     property_descriptor add();
-    property_descriptor add(property_type const&);
+    property_descriptor add(edge_properties const&);
+
+    inline edge_properties& properties(property_descriptor d)
+    { return _props[d].first; }
 
-    property_type& properties(property_descriptor);
+    /** Bind iterators into the incidence lists into the global property. */
+    template <typename Iter>
+    void bind(property_descriptor d, Iter src, Iter tgt)
+    {
+        _props[d].second.put(src);
+        _props[d].third.put(tgt);
+    }
 
     /** Return the number of properties in the store. */
     inline size_type size() const
     { return _props.size(); }
 
+    inline iterator begin() const
+    { return _props.begin(); }
+
+    inline iterator end() const
+    { return _props.end(); }
+
 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());
+    return add(edge_properties());
 }
 
 template <typename P, typename A>
 typename property_vector<P,A>::property_descriptor
-property_vector<P,A>::add(property_type const& p)
+property_vector<P,A>::add(edge_properties const& p)
 {
-    _props.push_back(p);
+    _props.push_back(make_triple(p, first_iterator(), second_iterator()));
     return _props.size() - 1;
 }
 
-/**
- * Return the properties corresponding to the given descriptor.
- */
-template <typename P, typename A>
-typename property_vector<P,A>::property_type&
-property_vector<P,A>::properties(property_descriptor p)
-{
-    return _props[p];
-}
-
 #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-25 12:38:47 EDT (Wed, 25 Jun 2008)
@@ -45,7 +45,6 @@
     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);
@@ -94,5 +93,50 @@
 std::ostream& operator<<(std::ostream& os, undirected_edge<VD,PD> const& e)
 { return os << "{" << e.first() << " " << e.second() << "}"; }
 
+/**
+ * The undirected edge iterator simply wraps the iterator over the global edge
+ * property store of undirected graphs.
+ */
+template <typename Graph>
+struct undirected_edge_iterator
+{
+    typedef typename Graph::property_store store_type;
+    typedef typename Graph::vertex_type vertex_type;
+    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;
+
+    typedef typename Graph::edge_descriptor value_type;
+    typedef value_type reference;
+    typedef value_type pointer;
+
+    undirected_edge_iterator(prop_iterator i)
+        : iter(i)
+    { }
+
+    inline undirected_edge_iterator& operator++()
+    { ++iter; return *this; }
+
+    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);
+    }
+
+    prop_iterator iter;
+};
+
+template <typename Graph>
+inline bool
+operator==(undirected_edge_iterator<Graph> const& a, undirected_edge_iterator<Graph> const& b)
+{ return a.iter == b.iter; }
+
+template <typename Graph>
+inline bool
+operator!=(undirected_edge_iterator<Graph> const& a, undirected_edge_iterator<Graph> const& b)
+{ return !(a == b); }
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp	2008-06-25 12:38:47 EDT (Wed, 25 Jun 2008)
@@ -55,6 +55,8 @@
     // of the vertex.
     typedef undirected_vertex<vertex_properties, incidence_store> vertex_type;
     typedef typename vertex_type::size_type incident_edges_size_type;
+    typedef undirected_edge_iterator<this_type> edge_iterator;
+    typedef std::pair<edge_iterator, edge_iterator> edge_range;
     typedef incidence_iterator<typename vertex_type::iterator> incident_edge_iterator;
     typedef std::pair<incident_edge_iterator, incident_edge_iterator> incident_edge_range;
 
@@ -71,7 +73,6 @@
     // type to enable mapped vertices.
     typedef typename VertexStore::key_type vertex_key;
 
-
     // Constructors
     undirected_graph();
 
@@ -187,30 +188,23 @@
     void remove_edges(vertex_key const&, vertex_key const&);
     //@}
 
-    /** @name Vertex Iteration
-     * These functions allow iteration over the vertex set.
-     */
+    /** @name Size and Degree */
     //@{
-    vertex_range vertices() const;
-    vertex_iterator begin_vertices() const;
-    vertex_iterator end_vertices() const;
     vertices_size_type num_vertices() const;
-    //@}
-
-    /** @name Edge Iteration
-     * These function allow iteration over the edge set.
-     */
-    //@{
-    // edge_range edges() const;
-    // edge_iterator begin_edges() const;
-    // edge_iterator end_edges() const;
     edges_size_type num_edges() const;
+    incident_edges_size_type degree(vertex_descriptor) const;
     //@}
 
-    /** @name Incident Edge Iteration
-     * These functions allow iteration over the incident edges of a vertex.
-     */
+    /** @name Iterators */
     //@{
+    vertex_range vertices() const;
+    vertex_iterator begin_vertices() const;
+    vertex_iterator end_vertices() const;
+
+    edge_range edges() const;
+    edge_iterator begin_edges() const;
+    edge_iterator end_edges() const;
+
     incident_edge_iterator begin_incident_edges(vertex_descriptor) const;
     incident_edge_iterator end_incident_edges(vertex_descriptor) const;
     incident_edge_range incident_edges(vertex_descriptor) const;
@@ -218,8 +212,6 @@
     adjacent_vertex_iterator begin_adjacent_vertices(vertex_descriptor) const;
     adjacent_vertex_iterator end_adjacent_vertices(vertex_descriptor) const;
     adjacent_vertex_range adjacent_vertices(vertex_descriptor) const;
-
-    incident_edges_size_type degree(vertex_descriptor) const;
     //@}
 
     /** @name Property Accessors
@@ -230,11 +222,8 @@
     edge_properties& operator[](edge_descriptor);
     //@}
 
-private:
     property_store _props;
     vertex_store _verts;
-
-    std::size_t _edges;
 };
 
 #define BOOST_GRAPH_UG_PARAMS \
@@ -382,6 +371,7 @@
     // 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);
 
@@ -392,8 +382,9 @@
         // iterator.
         if(ins.first == src.end()) {
             property_descriptor p = _props.add(ep);
-            src.connect(v, p);
-            tgt.connect(u, p);
+            typename vertex_type::iterator i = src.connect(v, p);
+            typename vertex_type::iterator j = tgt.connect(u, p);
+            _props.bind(p, i, j);
             return edge_descriptor(u, v, p);
         }
         else {
@@ -652,6 +643,24 @@
     return _verts.end_vertices();
 }
 
+/** Return an iterator to the first edge. */
+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 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 an iterator range over the edges in the graph. */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::edge_range
+undirected_graph<VP,EP,VS,ES>::edges() const
+{ return std::make_pair(begin_edges(), end_edges()); }
+
 /**
  * Return the number of iterators in this graph.
  */

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp	2008-06-25 12:38:47 EDT (Wed, 25 Jun 2008)
@@ -40,7 +40,7 @@
      * connection is allowed and/or already existing.
      */
     inline std::pair<iterator, bool> allow(vertex_descriptor) const;
-    inline void connect(vertex_descriptor, property_descriptor);
+    inline iterator connect(vertex_descriptor, property_descriptor);
     inline void disconnect(vertex_descriptor, property_descriptor);
     inline iterator disconnect(iterator);
 
@@ -118,10 +118,10 @@
  * Connect this vertex to the vertex v with edge properties p.
  */
 template <typename VP, typename IS>
-void
+typename undirected_vertex<VP,IS>::iterator
 undirected_vertex<VP,IS>::connect(vertex_descriptor v, property_descriptor p)
 {
-    _edges.add(make_pair(v, p));
+    return _edges.add(make_pair(v, p));
 }
 
 /**

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-25 12:38:47 EDT (Wed, 25 Jun 2008)
@@ -2,6 +2,7 @@
 #include <iostream>
 
 #include <boost/graphs/directed_graph.hpp>
+#include <boost/graphs/undirected_graph.hpp>
 
 #include "square.hpp"
 
@@ -10,7 +11,9 @@
 typedef vertex_vector<> vvec;
 typedef edge_vector<> evec;
 
+
 void directed();
+void undirected();
 
 int main()
 {
@@ -29,17 +32,16 @@
     for(Graph::edge_iterator i = rng.first; i != rng.second; ++i) {
         cout << *i << endl;
     }
+}
 
+void undirected()
+{
+    typedef undirected_graph<int, int, vvec, evec> Graph;
+    Graph g;
+    make_square(g);
 
-    /*
-    // How can we iterate over the edges of a directed graph.. Iterate over
-    // the out edges of each vertex.
-    Graph::vertex_range v = g.vertices();
-    for(Graph::vertex_iterator i = v.first; i != v.second; ++i) {
-        Graph::out_edge_range o = g.out_edges(*i);
-        for(Graph::out_edge_iterator j = o.first; j != o.second; ++j) {
-            cout << g[*i] << " " << g[*j] << endl;
-        }
+    Graph::edge_range rng = g.edges();
+    for(Graph::edge_iterator i = rng.first ; i != rng.second; ++i) {
+        cout << *i << endl;
     }
-    */
 }