Boost logo

Boost-Commit :

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;
     }
- */
 }


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk