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

From: asutton_at_[hidden]
Date: 2008-06-20 11:27:56

Author: asutton
Date: 2008-06-20 11:27:55 EDT (Fri, 20 Jun 2008)
New Revision: 46561
URL: http://svn.boost.org/trac/boost/changeset/46561

Log:
Rewriting some of the add-edge protocol and types for directed graphs to help
better support constant edge deletions. This is done by making the out
descriptor wrap an iterator (const or otherwise) into the out edge list.
Since that gets piggy-backed around by edge descriptors, we can do a
pretty good job removing vertices. This adds a lot of const-based grossness,
however.

Added a couple of missing files.

Added:
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp   |     4 +++                                     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp  |    12 +++++----                               
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp |    12 +++++-----                              
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_descriptor.hpp  |    47 +++++++++++++++++---------------------- 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp        |    20 ++++++++++------                        
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp      |     6 ++--                                    
   6 files changed, 52 insertions(+), 49 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-20 11:27:55 EDT (Fri, 20 Jun 2008)
@@ -38,6 +38,10 @@
     inline vertex_descriptor target() const
     { return _out.target(); }
 
+    /** Return the out edge descriptor. */
+    inline out_descriptor out_edge() const
+    { return _out; }
+
     /** @name Property Accessors
      * Return the properties associated with the edge.
      */

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 11:27:55 EDT (Fri, 20 Jun 2008)
@@ -396,19 +396,21 @@
     vertex_type &tgt = _verts.vertex(v);
 
     // Do we add the edge or not?
-    std::pair<typename vertex_type::out_iterator, bool> ins = src.allow(v);
+    std::pair<out_descriptor, bool> ins = src.allow(v);
     if(ins.second) {
         // The addition is allowed... Was there already an edge there? If not,
         // connect u to v (and vice-versa) with the given properties. Otherwise,
         // just return the existing edge.
         edge_descriptor e;
-        if(ins.first == src.end_out()) {
+        // Yuck. Is there no better way to this (i.e., provide some kind of
+        // switch for validity?).
+        if(ins.first.iter == src.end_out()) {
             out_descriptor o = src.connect_target(v, ep);
             tgt.connect_source(u, o);
             e = edge_descriptor(u, o);
         }
         else {
-            e = edge_descriptor(u, *ins.first);
+            e = edge_descriptor(u, ins.first);
         }
 
         // Remember that we're allocating the edge.
@@ -429,7 +431,7 @@
 template <BOOST_GRAPH_DG_PARAMS>
 typename directed_graph<VP,EP,VS,ES>::edge_descriptor
 directed_graph<VP,EP,VS,ES>::add_edge(vertex_properties const& u,
-                                        vertex_properties const& v)
+                                      vertex_properties const& v)
 {
     return add_edge(u, v, edge_properties());
 }
@@ -484,7 +486,7 @@
     vertex_type& tgt = _verts.vertex(e.target());
 
     // Remove the connections... That's it.
-    src.disconnect_target(e.target());
+    src.disconnect_target(e.out_edge());
     tgt.disconnect_source(e.source());
 }
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp	2008-06-20 11:27:55 EDT (Fri, 20 Jun 2008)
@@ -44,12 +44,12 @@
     //@}
 
 
-    std::pair<out_iterator, bool> allow(vertex_descriptor) const;
+    std::pair<out_descriptor, bool> allow(vertex_descriptor);
 
     out_descriptor connect_target(vertex_descriptor, edge_properties const&);
     void connect_source(vertex_descriptor, out_descriptor);
 
-    void disconnect_target(vertex_descriptor);
+    void disconnect_target(out_descriptor);
     void disconnect_source(vertex_descriptor);
 
     /** @name Property Accessors */
@@ -120,8 +120,8 @@
  * be added anyways.
  */
 template <typename V, typename O, typename I>
-std::pair<typename directed_vertex<V,O,I>::out_iterator, bool>
-directed_vertex<V,O,I>::allow(vertex_descriptor v) const
+std::pair<typename directed_vertex<V,O,I>::out_descriptor, bool>
+directed_vertex<V,O,I>::allow(vertex_descriptor v)
 {
     return _out.allow(v);
 }
@@ -155,9 +155,9 @@
  */
 template <typename V, typename O, typename I>
 void
-directed_vertex<V,O,I>::disconnect_target(vertex_descriptor v)
+directed_vertex<V,O,I>::disconnect_target(out_descriptor d)
 {
-    _out.remove(v);
+    _out.remove(d);
 }
 
 /**

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp	2008-06-20 11:27:55 EDT (Fri, 20 Jun 2008)
@@ -0,0 +1,63 @@
+
+#ifndef IN_SET_HPP
+#define IN_SET_HPP
+
+#include <map>
+
+/**
+ * The in-edge set references incoming edges from other vertices. Each edge
+ * can be uniquely identified by its source vertex and property descriptor.
+ *
+ * @param Edge A pair describing a vertex descriptor and out edge descriptor.
+ * @param Alloc The allocator for edge pairs.
+ */
+template <typename Edge, typename Compare, typename Alloc>
+class in_set
+{
+public:
+    typedef Edge in_pair;
+    typedef typename Edge::first_type vertex_descriptor;
+    typedef typename Edge::second_type out_descriptor;
+private:
+    typedef std::map<vertex_descriptor, out_descriptor, Compare, Alloc> store_type;
+public:
+    typedef typename store_type::iterator iterator;
+    typedef typename store_type::const_iterator const_iterator;
+    typedef typename store_type::size_type size_type;
+
+    in_set()
+        : _edges()
+    { }
+
+    /**
+     * Add the edge to the set.
+     * @complexity O(deg(u))
+     */
+    void add(in_pair e)
+    { _edges.insert(e); }
+
+    /** Find the edge with the given vertex. */
+    iterator find(vertex_descriptor v)
+    { return _edges.find(v); }
+
+    /** Find the edge with the given vertex. */
+    const_iterator find(vertex_descriptor v) const
+    { return _edges.find(v); }
+
+    /** Remove the edge with the given descriptor. */
+    void remove(vertex_descriptor v)
+    { _edges.erase(find(v)); }
+
+    /** Remove all edges. */
+    void clear()
+    { _edges.clear(); }
+
+    /** Get the number of incoming edges (in degree). */
+    size_type size() const
+    { return _edges.size(); }
+
+private:
+    store_type _edges;
+};
+
+#endif

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 11:27:55 EDT (Fri, 20 Jun 2008)
@@ -3,52 +3,45 @@
 #define OUT_DESCRIPTOR_HPP
 
 /**
- * The out descriptor wraps an opaque reference to an out edge pair and
- * provides some convenience functions for translating between the elements
- * of the referenced pair and their "descriptors".
+ * The out descriptor wraps an iterator into the out vector. This is primarily
+ * provided to help decouple the directed edge from the underlying reference
+ * to the out edge list.
  *
- * @param OutPair The pair of vertex descriptor and edge property being
+ * @param OutIter The pair of vertex descriptor and edge property being
  * described.
  */
-template <typename OutPair>
+template <typename OutIter>
 struct basic_out_descriptor
 {
-    typedef typename OutPair::first_type vertex_descriptor;
-    typedef typename OutPair::second_type edge_properties;
+    typedef typename OutIter::value_type out_pair;
+    typedef typename out_pair::first_type vertex_descriptor;
+    typedef typename out_pair::second_type edge_properties;
 
     /** @name Constructors */
     //@{
     inline basic_out_descriptor()
-        : _d(0)
+        : iter()
     { }
 
     inline basic_out_descriptor(basic_out_descriptor const& x)
-        : _d(x._d)
+        : iter(x.iter)
     { }
 
-    inline basic_out_descriptor(OutPair& o)
-        : _d(&o)
+    inline basic_out_descriptor(OutIter const& iter)
+        : iter(iter)
     { }
+    //@}
 
-    inline basic_out_descriptor(OutPair const& o)
-        : _d(&const_cast<OutPair&>(o))
-    { }
-
-    //@{
-
-    OutPair& pair() const
-    { return *reinterpret_cast<OutPair*>(_d); }
-
-    vertex_descriptor target() const
-    { return pair().first; }
+    inline vertex_descriptor target() const
+    { return iter->first; }
 
-    edge_properties& properties()
-    { return pair().second; }
+    inline edge_properties& properties()
+    { return iter->second; }
 
-    edge_properties const& properties() const
-    { return pair().second; }
+    inline edge_properties const& properties() const
+    { return iter->second; }
 
-    mutable void* _d;
+    OutIter iter;
 };
 
 #endif

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 11:27:55 EDT (Fri, 20 Jun 2008)
@@ -4,8 +4,9 @@
 
 #include <list>
 
+#include <boost/next_prior.hpp>
+
 #include "out_descriptor.hpp"
-#include "select.hpp"
 
 /**
  * The out list implements list-based, out-edge storage for directed graphs.
@@ -33,7 +34,7 @@
     typedef typename store_type::const_iterator const_iterator;
     typedef typename store_type::size_type size_type;
 
-    typedef basic_out_descriptor<out_pair> out_descriptor;
+    typedef basic_out_descriptor<iterator> out_descriptor;
 
     inline out_list()
         : _edges()
@@ -41,15 +42,15 @@
     { }
 
     /** Allow an edge insertion? */
-    std::pair<const_iterator, bool> allow(vertex_descriptor v) const
-    { return std::make_pair(_edges.end(), true); }
+    std::pair<out_descriptor, bool> allow(vertex_descriptor v)
+    { return std::make_pair(out_descriptor(_edges.end()), true); }
 
     /** Add the edge to the list. */
     out_descriptor add(out_pair e)
     {
         ++_size;
         _edges.push_back(e);
-        return _edges.back();
+        return out_descriptor(boost::prior(_edges.end()));
     }
 
     /** Find the edge with the given vertex. */
@@ -72,11 +73,14 @@
         return end;
     }
 
-    /** Remove the edge with the given vertex. */
-    void remove(vertex_descriptor v)
+    /**
+     * Remove the edge with the given vertex.
+     * @complexity O(1)
+     */
+    void remove(out_descriptor d)
     {
         --_size;
-        _edges.erase(find(v));
+        _edges.erase(d.iter);
     }
 
     /** Remove all edges. */

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp	2008-06-20 11:27:55 EDT (Fri, 20 Jun 2008)
@@ -0,0 +1,89 @@
+
+#ifndef OUT_SET_HPP
+#define OUT_SET_HPP
+
+#include <map>
+
+#include "out_descriptor.hpp"
+
+/**
+ * The out set implements set-based, out-edge storage for directed graphs.
+ * out-edges are uniquely identified by their target vertex and property
+ * descriptor. List-based stores support medium inserts, mediam finds, and allow
+ * removals.
+ *
+ * The edge is required to be a pair containing a vertex descriptor and a edge
+ * property (not descriptor). This type defines the out_descriptor - an opaque
+ * reference to a target/property pair.
+ *
+ * The out edge set is actually implemented as a mapping from vertex descriptor
+ * to stored edge property.
+ *
+ * @param Edge A pair describing a vertex descriptor and the edge properties.
+ * @param Alloc The allocator for edge pairs.
+ */
+template <typename Edge, typename Compare, typename Alloc>
+class out_set
+{
+public:
+    typedef Edge out_pair;
+    typedef typename Edge::first_type vertex_descriptor;
+    typedef typename Edge::second_type edge_properties;
+private:
+    typedef std::map<vertex_descriptor, edge_properties, Compare, Alloc> store_type;
+public:
+    typedef typename store_type::iterator iterator;
+    typedef typename store_type::const_iterator const_iterator;
+    typedef typename store_type::size_type size_type;
+
+    typedef basic_out_descriptor<iterator> out_descriptor;
+
+    inline out_set()
+        : _edges()
+    { }
+
+    /** Allow the edge insertion? */
+    std::pair<out_descriptor, bool> allow(vertex_descriptor v)
+    { return std::make_pair(out_descriptor(find(v)), true); }
+
+    /** Add the edge to the set. */
+    out_descriptor add(out_pair e)
+    { return out_descriptor(_edges.insert(e).first); }
+
+    /** Find the edge with the given vertex descriptor. */
+    iterator find(vertex_descriptor v)
+    { return _edges.find(v); }
+
+    /** Find the edge with the given vertex descriptor. */
+    const_iterator find(vertex_descriptor v) const
+    { return _edges.find(v); }
+
+    /**
+     * Remove the edge with the given vertex descriptor.
+     * @complexity O(log(deg(u)))
+     */
+    void remove(out_descriptor d)
+    { _edges.erase(d.iter); }
+
+    /** Remove all edges. */
+    void clear()
+    { _edges.clear(); }
+
+    /** @name Iterators and Size */
+    //@{
+    inline const_iterator begin() const
+    { return _edges.begin(); }
+
+    inline const_iterator end() const
+    { return _edges.end(); }
+
+    /** Get the number of outgoing edges. */
+    inline size_type size() const
+    { return _edges.size(); }
+    //@{
+
+private:
+    store_type _edges;
+};
+
+#endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp	2008-06-20 11:27:55 EDT (Fri, 20 Jun 2008)
@@ -32,14 +32,14 @@
     typedef typename store_type::const_iterator const_iterator;
     typedef typename store_type::size_type size_type;
 
-    typedef basic_out_descriptor<out_pair> out_descriptor;
+    typedef basic_out_descriptor<const_iterator> out_descriptor;
 
     inline out_vector()
         : _edges()
     { }
 
     /** Allow the addition? */
-    std::pair<const_iterator, bool> allow(vertex_descriptor v) const
+    std::pair<out_descriptor, bool> allow(vertex_descriptor v)
     { return std::make_pair(_edges.end(), true); }
 
     /**
@@ -49,7 +49,7 @@
     out_descriptor add(out_pair e)
     {
         _edges.push_back(e);
-        return _edges.back();
+        return out_descriptor(boost::prior(_edges.end()));
     }
 
     /** Get the number of outgoing edges. */