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

From: asutton_at_[hidden]
Date: 2008-07-20 08:51:24

Author: asutton
Date: 2008-07-20 08:51:24 EDT (Sun, 20 Jul 2008)
New Revision: 47632
URL: http://svn.boost.org/trac/boost/changeset/47632

Log:
Fixing a broken directed edge iterator. The previous definition would not
accomodate increments over vertices without edges (i.e., breaks). This commit
provides a fairly inelegant solution to the problem.

Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp |    73 ++++++++++++++++++++++++++------------- 
   1 files changed, 49 insertions(+), 24 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-07-20 08:51:24 EDT (Sun, 20 Jul 2008)
@@ -88,6 +88,17 @@
 { return os << "(" << e.source() << " " << e.target() << ")"; }
 
 /**
+ * This is gonna be a little funky.
+ */
+template <typename O, typename I>
+std::size_t hash_value(directed_edge<O,I> const& e)
+{
+    using boost::hash;
+    std::cout << e.out << std::endl;
+    return hash_value(e.out);
+}
+
+/**
  * The directed edge iterator provides functionality for iterating over the
  * edges of a directed graph. This is essenitally done by iterating over the
  * out edges of each vertex in the order in which they were added to the graph.
@@ -110,24 +121,48 @@
     typedef value_type pointer;
 
     directed_edge_iterator()
-        : verts(0), vert(), edge()
+        : store(0), vert(), edge()
     { }
 
-    directed_edge_iterator(vertex_store& store, vertex_iterator i)
-        : verts(&store)
+    directed_edge_iterator(vertex_store& s, vertex_iterator i)
+        : store(&s)
         , vert(i)
-        , edge((i == store.end_vertices())
-            ? edge_iterator()               // empty out iterator
-            : vertex(*i).begin_out())       // first out iterator of v
+        , edge(next(vert == store->end_vertices()
+                    ? edge_iterator()
+                    : vertex().begin_out(), true))
     { }
 
+    /** Locate the next valid edge iterator, skipping the update on init. */
+    inline edge_iterator next(edge_iterator e, bool first = false)
+    {
+        if(vert == store->end_vertices()) {
+            // If we're at the end already, don't do anything, Just return the same
+            // iterator that we got.
+            return e;
+        }
+        else {
+            if(e != vertex().end_out() && !first) {
+                ++e;
+            }
+
+            // If after incrementing, we reach the end of the vertices, then
+            // we have to skip to the next non-empty vertex or the end of the
+            // sequence, whichever comes first.
+            while(e == vertex().end_out() && vert != store->end_vertices()) {
+                ++vert;
+                e = vertex().begin_out();
+            }
+            return vert != store->end_vertices() ? e : edge_iterator();
+        }
+    }
+
     /** Return the vertex, given the descriptor. */
-    inline vertex_type& vertex(vertex_descriptor v)
-    { return verts->vertex(v); }
+    inline vertex_type& vertex()
+    { return store->vertex(*vert); }
 
     /** Return the vertex, given the descriptor. */
-    inline vertex_type const& vertex(vertex_descriptor v) const
-    { return verts->vertex(v); }
+    inline vertex_type const& vertex() const
+    { return store->vertex(*vert); }
 
     /** Return the source vertex of the current edge. */
     inline vertex_descriptor source() const
@@ -142,22 +177,12 @@
      * descriptor
      */
     inline out_descriptor out_edge() const
-    { return vertex(*vert).out_edge(edge); }
+    { return vertex().out_edge(edge); }
 
     inline directed_edge_iterator& operator++()
     {
-        // If we're not done, increment the current edge. If that increment
-        // pushes the edge iterator off the vertex, move to the next vertex
-        // and reset the edge iterator.
-        if(vert != verts->end_vertices()) {
-            ++edge;
-            if(edge == vertex(*vert).end_out()) {
-                // Move to the next vertex, resetting the edge iterator.
-                ++vert;
-                edge = (vert != verts->end_vertices())
-                    ? vertex(*vert).begin_out()
-                    : edge_iterator();
-            }
+        if(vert != store->end_vertices()) {
+            edge = next(edge);
         }
         return *this;
     }
@@ -177,7 +202,7 @@
     inline reference operator*() const
     { return Edge(source(), target(), out_edge()); }
 
-    vertex_store*       verts;
+    vertex_store*       store;
     vertex_iterator     vert;
     edge_iterator       edge;
 };