[boost] [BGL] nonrecursive DFS simplification proposal - patch

From: Janusz Piwowarski (jpiw_at_[hidden])
Date: 2003-09-06 07:44:14

Hi all,

I've read disccusion between Bruce and Vladimir, and dfs-FAQ at
http://listarchives.boost.org/MailArchives/boost/msg48752.php . With
my changes isn't necessary to store current vertex on stack.

-- 
Regards, 
Janusz
--- depth_first_search.hpp.orig Fri Aug 29 22:15:14 2003
+++ depth_first_search.hpp      Sat Sep  6 12:10:58 2003
@@ -114,10 +114,9 @@
       function_requires< ColorValueConcept<ColorValue> >();
       typedef color_traits<ColorValue> Color;
       typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter;
-      typedef std::pair<Vertex, std::pair<Iter, Iter> > VertexInfo;
 
       Iter ei, ei_end;
-      std::vector<VertexInfo> stack;
+      std::vector< std::pair<Iter, Iter> > stack;
 
       // Possible optimization for vector
       //stack.reserve(num_vertices(g));
@@ -128,23 +127,16 @@
       vis.discover_vertex(u, g);
       tie(ei, ei_end) = out_edges(u, g);
       if (static_cast<TF&>(func)(u, g)) {
-          // If this vertex terminates the search, we push empty range
-          stack.push_back(std::make_pair(u, std::make_pair(ei_end, ei_end)));
-      } else {
-          stack.push_back(std::make_pair(u, std::make_pair(ei, ei_end)));
+        ei = ei_end;
       }
-      while (!stack.empty()) {
-        VertexInfo& back = stack.back();
-        u = back.first;
-        tie(ei, ei_end) = back.second;
-        stack.pop_back();
+      for (;;) {
         while (ei != ei_end) {
           Vertex v = target(*ei, g);
           vis.examine_edge(*ei, g);
           ColorValue v_color = get(color, v);
           if (v_color == Color::white()) {
             vis.tree_edge(*ei, g);
-            stack.push_back(std::make_pair(u, std::make_pair(++ei, ei_end)));
+            stack.push_back(std::make_pair(ei, ei_end));
             u = v;
             put(color, u, Color::gray());
             vis.discover_vertex(u, g);
@@ -162,6 +154,12 @@
         }
         put(color, u, Color::black());
         vis.finish_vertex(u, g);
+        if ( stack.empty() )
+          break;
+        tie(ei, ei_end) = stack.back();
+        u = source(*ei, g);
+        ++ei;
+        stack.pop_back();
       }
     }