[Boost-commit] svn:boost r46420 - sandbox/SOC/2008/graphs/branches/iu/boost/graphs

From: asutton_at_[hidden]
Date: 2008-06-16 09:17:26

Author: asutton
Date: 2008-06-16 09:17:25 EDT (Mon, 16 Jun 2008)
New Revision: 46420
URL: http://svn.boost.org/trac/boost/changeset/46420

Log:
Implemented constant num_edges() for undirected graphs by maintaing a separate
size count for the property list.

Text files modified: 
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp    |     6 ++--                                    
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp    |    20 ++++++++++++---                         
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_vector.hpp  |     6 ++++                                    
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp |    50 ++++++++++++++++++++++++++++++++------- 
   4 files changed, 66 insertions(+), 16 deletions(-)

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp	2008-06-16 09:17:25 EDT (Mon, 16 Jun 2008)
@@ -21,9 +21,9 @@
     typedef typename IncEdge::second_type property_descriptor;
 private:
     // Actually, the incident set, as it fundamentally implements a simple
-    // graph is based on a map keyed on the adjacenct vertex and mapped to
-    // the edge properties that describe it.
-    // We're basically undwinding and rebuilding the edge pair for this map.
+    // graph is based on a map keyed on the adjacenct vertex and mapped to the
+    // edge properties that describe it. We're basically undwinding and
+    // rebuilding the edge pair for this map.
     typedef std::map<vertex_descriptor, property_descriptor, Compare, Alloc> store_type;
 public:
     typedef typename store_type::iterator iterator;

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp	2008-06-16 09:17:25 EDT (Mon, 16 Jun 2008)
@@ -11,12 +11,19 @@
  * 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.
+ *
+ * The property store actually maintains the number of elements internally.
+ * Because this store is built over a list, but only allows the insertion and
+ * removal of one element at a time, we do this to optimize calls to the size()
+ * function (which is used for the number of edges).
  */
 template <typename Props, typename Alloc>
 class property_list
 {
     typedef std::list<Props, Alloc> store_type;
 public:
+    typedef typename store_type::size_type size_type;
+
     typedef Props property_type;
     typedef proplist_descriptor<typename store_type::iterator> property_descriptor;
 
@@ -32,12 +39,13 @@
     // Property access.
     inline property_type& properties(property_descriptor);
 
-    // Don't ever call this function.
-    inline typename store_type::size_type size() const
-    { return _props.size(); }
+    /** Return the number of properties. */
+    inline size_type size() const
+    { return _size; }
 
 private:
-    store_type _props;
+    store_type  _props;
+    size_type   _size;
 };
 
 /**
@@ -56,6 +64,7 @@
 template <typename P, typename A>
 property_list<P,A>::property_list()
     : _props()
+    , _size(0)
 { }
 
 /**
@@ -65,6 +74,7 @@
 typename property_list<P,A>::property_descriptor
 property_list<P,A>::add()
 {
+    ++_size;
     return add(property_type());
 }
 
@@ -75,6 +85,7 @@
 typename property_list<P,A>::property_descriptor
 property_list<P,A>::add(property_type const& p)
 {
+    ++_size;
     return _props.insert(_props.end(), p);
 }
 
@@ -88,6 +99,7 @@
 void
 property_list<P,A>::remove(property_descriptor p)
 {
+    --_size;
     _props.erase(p.iter);
 }
 

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_vector.hpp	2008-06-16 09:17:25 EDT (Mon, 16 Jun 2008)
@@ -13,6 +13,8 @@
 {
     typedef std::vector<Props, Alloc> store_type;
 public:
+    typedef typename store_type::size_type size_type;
+
     typedef Props property_type;
     typedef std::size_t property_descriptor;
 
@@ -23,6 +25,10 @@
 
     property_type& properties(property_descriptor);
 
+    /** Return the number of properties in the store. */
+    inline size_type size() const
+    { return _props.size(); }
+
 private:
     store_type _props;
 };

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp	2008-06-16 09:17:25 EDT (Mon, 16 Jun 2008)
@@ -2,8 +2,6 @@
 #ifndef UNDIRECTED_GRAPH_HPP
 #define UNDIRECTED_GRAPH_HPP
 
-#include <boost/bind.hpp>
-
 #include "none.hpp"
 
 // Various issues...
@@ -47,6 +45,7 @@
     // 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;
+    typedef typename property_store::size_type edges_size_type;
 
     // Generate a bunch of descriptors. The vertex descriptor is fairly
     // straightforward since, like the property store, its independant of almost
@@ -62,19 +61,25 @@
 
     // 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.
+    // related types. Incident edge iterators are abstracted over the iterators
+    // of the vertex.
     typedef vertex<vertex_properties, incidence_store> vertex_type;
     typedef typename vertex_type::size_type incident_edges_size_type;
-
-    // Incident edge iterators are abstracted over the iterators of the vertex.
     typedef incidence_iterator<typename vertex_type::iterator> incident_edge_iterator;
     typedef std::pair<incident_edge_iterator, incident_edge_iterator> incident_edge_range;
 
+    // The vertex store and related properties can also be built on the vertex
+    // type.
     typedef typename VertexStore::template store<vertex_type>::type vertex_store;
     typedef typename vertex_store::size_type vertices_size_type;
     typedef typename vertex_store::vertex_iterator vertex_iterator;
     typedef typename vertex_store::vertex_range vertex_range;
 
+    // Because edges are "distributed" among vertices, the edge iterators are
+    // somewhat special.
+    typedef none edge_iterator;
+    typedef std::pair<edge_iterator, edge_iterator> edge_range;
+
     // 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;
@@ -98,10 +103,31 @@
     void remove_edge(edge_descriptor);
     void remove_edges(vertex_descriptor, vertex_descriptor);
 
+    /** @name Vertex Iteration
+     * These functions allow the iteration over the vertex set.
+     */
+    //@{
     vertex_range vertices() const;
     vertex_iterator begin_vertices() const;
     vertex_iterator end_vertices() const;
+    //@}
+
+    /** @name Edge Iteration
+     * These function allow the iteration over the edge set.
+     */
+    //@{
+    edge_range edges() const;
+    edge_iterator begin_edges() const;
+    edge_iterator end_edges() const;
+    //@}
+
+    /** @name Graph Size
+     * These functions return the number of vertices and edges in the graph.
+     */
+    //@{
     vertices_size_type num_vertices() const;
+    edges_size_type num_edges() const;
+    //@}
 
     // Edge incidence
     incident_edge_iterator begin_incident_edges(vertex_descriptor) const;
@@ -165,7 +191,6 @@
 
         // Remove all the properties too. Does this make sense here?
         _props.remove(e.properties());
-
     }
 }
 
@@ -271,9 +296,6 @@
 undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor u,
                                             vertex_descriptor v)
 {
-    using boost::bind;
-    using boost::ref;
-
     vertex_type& src = _verts.vertex(u);
     vertex_type& tgt = _verts.vertex(v);
 
@@ -331,6 +353,16 @@
 }
 
 /**
+ * Return the number of edges in this graph.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::edges_size_type
+undirected_graph<VP,EP,VS,ES>::num_edges() const
+{
+    return _props.size();
+}
+
+/**
  * Return an iterator to the first incident edge of the given vertex.
  */
 template <BOOST_GRAPH_UG_PARAMS>