[boost] [graph] non-recursive version of undirected_dfs

From: Synge Todo (wistaria_at_[hidden])
Date: 2004-08-19 00:33:19

Dear Boosters,

I'm posting a non-recursive version of undirected_dfs, which should
have advantages in space and time over the current implementation
based on recursion, especially for huge graphs.  It's a direct
counterpart of the non-recursive version of depth_first_search for
digraphs.

I have confirmed that libs/graph/example/undirected_dfs.cpp as well as
my own programs using undirected_dfs reproduce the identical outputs as
those with the original recursive version.

Best regards,
Synge


*** boost/graph/undirected_dfs.hpp	6 Aug 2004 05:02:41 -0000	1.1.1.1
--- boost/graph/undirected_dfs.hpp	19 Aug 2004 05:11:32 -0000	1.2
***************
*** 28,38 ****
--- 28,106 ----
  #define BOOST_GRAPH_UNDIRECTED_DFS_HPP
  
  #include <boost/graph/depth_first_search.hpp>
+ #include <vector>
  
  namespace boost {
  
    namespace detail {
  
+ // Define BOOST_RECURSIVE_DFS to use older, recursive version.
+ // It is retained for a while in order to perform performance
+ // comparison.
+ #ifndef BOOST_RECURSIVE_DFS
+ 
+     template <typename IncidenceGraph, typename DFSVisitor, 
+               typename VertexColorMap, typename EdgeColorMap>
+     void undir_dfv_impl
+       (const IncidenceGraph& g,
+        typename graph_traits<IncidenceGraph>::vertex_descriptor u, 
+        DFSVisitor& vis,
+        VertexColorMap vertex_color,
+        EdgeColorMap edge_color)
+     {
+       function_requires<IncidenceGraphConcept<IncidenceGraph> >();
+       function_requires<DFSVisitorConcept<DFSVisitor, IncidenceGraph> >();
+       typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
+       typedef typename graph_traits<IncidenceGraph>::edge_descriptor Edge;
+       function_requires<ReadWritePropertyMapConcept<VertexColorMap,Vertex> >();
+       function_requires<ReadWritePropertyMapConcept<EdgeColorMap,Edge> >();
+       typedef typename property_traits<VertexColorMap>::value_type ColorValue;
+       typedef typename property_traits<EdgeColorMap>::value_type EColorValue;
+       function_requires< ColorValueConcept<ColorValue> >();
+       function_requires< ColorValueConcept<EColorValue> >();
+       typedef color_traits<ColorValue> Color;
+       typedef color_traits<EColorValue> EColor;
+       typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter;
+       typedef std::pair<Vertex, std::pair<Iter, Iter> > VertexInfo;
+ 
+       std::vector<VertexInfo> stack;
+ 
+       put(vertex_color, u, Color::gray());
+       vis.discover_vertex(u, g);
+       stack.push_back(std::make_pair(u, out_edges(u, g)));
+       while (!stack.empty()) {
+ 	VertexInfo& back = stack.back();
+ 	u = back.first;
+ 	Iter ei, ei_end;
+ 	tie(ei, ei_end) = back.second;
+ 	stack.pop_back();
+ 	while (ei != ei_end) {
+ 	  Vertex v = target(*ei, g);
+ 	  vis.examine_edge(*ei, g);
+ 	  ColorValue v_color = get(vertex_color, v);
+ 	  EColorValue uv_color = get(edge_color, *ei);
+ 	  put(edge_color, *ei, EColor::black());
+ 	  if (v_color == Color::white()) {
+ 	    vis.tree_edge(*ei, g);
+ 	    stack.push_back(std::make_pair(u, std::make_pair(++ei, ei_end)));
+ 	    u = v;
+ 	    put(vertex_color, u, Color::gray());
+ 	    vis.discover_vertex(u, g);
+ 	    tie(ei, ei_end) = out_edges(u, g);
+ 	  } else if (v_color == Color::gray()) {
+ 	    if (uv_color == EColor::white()) vis.back_edge(*ei, g);
+ 	    ++ei;
+ 	  } else { // if (v_color == Color::black())
+ 	    ++ei;
+ 	  }
+ 	}
+ 	put(vertex_color, u, Color::black());
+ 	vis.finish_vertex(u, g);
+       }
+     }
+ 
+ #else // BOOST_RECURSIVE_DFS
+ 
      template <typename IncidenceGraph, typename DFSVisitor, 
                typename VertexColorMap, typename EdgeColorMap>
      void undir_dfv_impl
***************
*** 69,74 ****
--- 137,145 ----
        }
        put(vertex_color, u, Color::black());  vis.finish_vertex(u, g);
      }
+ 
+ #endif // ! BOOST_RECURSIVE_DFS
+ 
    } // namespace detail
  
    template <typename Graph, typename DFSVisitor,