[Boost-commit] svn:boost r46557 - sandbox/SOC/2008/graphs/trunk/boost/graphs

From: asutton_at_[hidden]
Date: 2008-06-20 09:29:00

Author: asutton
Date: 2008-06-20 09:28:59 EDT (Fri, 20 Jun 2008)
New Revision: 46557
URL: http://svn.boost.org/trac/boost/changeset/46557

Log:
Finished initial implementation of edge sets.

Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp |     1                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp       |    49 +++++++++++++++++++++++++++++++-------- 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_descriptor.hpp |     1                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp       |     8 ++++-                                   
   4 files changed, 46 insertions(+), 13 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp	2008-06-20 09:28:59 EDT (Fri, 20 Jun 2008)
@@ -29,6 +29,7 @@
 #include "directed_edge.hpp"
 #include "edge_vector.hpp"
 #include "edge_list.hpp"
+#include "edge_set.hpp"
 
 #include "adjacency_iterator.hpp"
 

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-20 09:28:59 EDT (Fri, 20 Jun 2008)
@@ -4,38 +4,65 @@
 
 #include "property_list.hpp"
 #include "incidence_set.hpp"
+#include "out_set.hpp"
+#include "in_set.hpp"
 
 /**
  * The edge set metafunction defines the basic facets of set-based edge
  * storage. Edge sets are best used to implement simple graphs (that do not
  * allow multiple edges).
  *
- * There are three parmaters to this function:
- * Compare - A function that compares vertex descriptors
- * IncAlloc - An allocator for the edge set
- * PropAlloc - An allocator for the global property set.
- *
- * Note that the edge set uses a map for the incidence store.
+ * @param Compare - A unary template class that compares vertex descriptors.
+ * @param FirstAlloc - An allocator template for either incident edges or out edges.
+ * @param SecondAlloc - An allocator template for either global properties or in edges.
  */
 template <
     template <typename> class Compare,
-    template <typename> class IncAlloc,
-    template <typename> class PropAlloc>
+    template <typename> class FirstAlloc,
+    template <typename> class SecondAlloc>
 struct basic_edge_set
 {
+    // The property store metafunnction generates the global store type
+    // for undirected graphs.
     template <typename EdgeProps>
     struct property_store
     {
-        typedef property_list<EdgeProps, PropAlloc<EdgeProps> > type;
+        typedef SecondAlloc<EdgeProps> allocator;
+        typedef property_list<EdgeProps, allocator> type;
     };
 
+    // The incidence store metafunction generates the per-vertex stores for
+    // incident edges.
     template <typename VertexDesc, typename PropDesc>
     struct incidence_store
     {
         typedef std::pair<VertexDesc, PropDesc> value;
         typedef Compare<VertexDesc> compare;
-        typedef IncAlloc<value> alloc;
-        typedef incidence_set<value, compare, alloc> type;
+        typedef FirstAlloc<value> allocator;
+        typedef incidence_set<value, compare, allocator> type;
+    };
+
+    // The out store metafunction generates the type of set used to store out
+    // edges of a vertex in a directed graph.
+    template <typename VertexDesc, typename Props>
+    struct out_store
+    {
+        typedef std::pair<VertexDesc, Props> out_pair;
+        typedef Compare<VertexDesc> compare;
+        typedef FirstAlloc<out_pair> allocator;
+        typedef out_set<out_pair, compare, allocator> type;
+    };
+
+    // The in store metafunction generates the type of list used to store
+    // incoming edges of directed graph. In edges are represented by the
+    // referencing vertex and an out edge descriptor.
+    template <typename VertexDesc, typename OutDesc>
+    struct in_store
+    {
+        typedef std::pair<VertexDesc, OutDesc> in_pair;
+        typedef Compare<VertexDesc> compare;
+        typedef SecondAlloc<in_pair> allocator;
+        typedef in_set<in_pair, compare, allocator> type;
     };
 };
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_descriptor.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_descriptor.hpp	2008-06-20 09:28:59 EDT (Fri, 20 Jun 2008)
@@ -33,6 +33,7 @@
     inline basic_out_descriptor(OutPair const& o)
         : _d(&const_cast<OutPair&>(o))
     { }
+
     //@{
 
     OutPair& pair() const

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp	2008-06-20 09:28:59 EDT (Fri, 20 Jun 2008)
@@ -36,6 +36,7 @@
 
     inline out_list()
         : _edges()
+        , _size(0)
     { }
 
     std::pair<const_iterator, bool> allow(vertex_descriptor v) const;
@@ -55,11 +56,12 @@
 
     /** Get the number of outgoing edges. */
     inline size_type size() const
-    { return _edges.size(); }
+    { return _size; }
     //@{
 
 private:
-    store_type _edges;
+    store_type  _edges;
+    size_type   _size;
 };
 
 /**
@@ -81,6 +83,7 @@
 typename out_list<E,A>::out_descriptor
 out_list<E,A>::add(out_pair e)
 {
+    ++_size;
     _edges.push_back(e);
     return _edges.back();
 }
@@ -112,6 +115,7 @@
 void
 out_list<E,A>::remove(out_pair e)
 {
+    --_size;
     _edges.erase(find(e));
 }