are all the same.
Define the macro BOOST_NONRECURSIVE_DFS in your project to use the nonrecursive implementation. If it is left undefined the orginal recursive code will remain in effect.
Some of the details could have been done a little differently. std::stack could have been used in place of std::vector. Instead of storing ei_end on the stack, it could have been recalculated using the Vertex value. But saving ei and ei_end together as a pair seemed more straightforward.
Bruce
_________________________________________________________________
Help STOP SPAM with the new MSN 8 and get 2 months FREE* http://join.msn.com/?page=features/junkmail
*** depth_first_search.hpp.orig Mon Aug 19 18:16:50 2002 --- depth_first_search.hpp Fri May 30 10:51:32 2003 *************** *** 27,33 **** #ifndef BOOST_GRAPH_RECURSIVE_DFS_HPP #define BOOST_GRAPH_RECURSIVE_DFS_HPP
- #include <stack> #include <boost/config.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/graph_concepts.hpp> --- 27,32 ---- *************** *** 35,40 **** --- 34,40 ---- #include <boost/graph/visitors.hpp> #include <boost/graph/named_function_params.hpp> #include <vector> + #include <utility>
namespace boost {
*************** *** 61,66 **** --- 61,133 ----
namespace detail {
+ #ifdef BOOST_NONRECURSIVE_DFS
+
+ template <class IncidenceGraph, class DFSVisitor, class ColorMap>
+ void depth_first_visit_impl
+ (const IncidenceGraph& g,
+ typename graph_traits<IncidenceGraph>::vertex_descriptor u,
+ DFSVisitor& vis,
+ ColorMap color)
+ {
+ function_requires<IncidenceGraphConcept<IncidenceGraph> >();
+ function_requires<DFSVisitorConcept<DFSVisitor, IncidenceGraph> >();
+ typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
+ function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >();
+ typedef typename property_traits<ColorMap>::value_type ColorValue;
+ 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;
+ Vertex v;
+ ColorValue v_color;
+ std::vector<VertexInfo> stack;
+
+ // Each item on the stack holds a vertex and its current out-edge
+ // iterators. The vertex is needed to restore the value of u when
+ // the stack is popped.
+
+ // Possible optimization for vector
+ //stack.reserve(num_vertices(g));
+
+ stack.push_back(make_pair(u, out_edges(u, g)));
+ put(color, u, Color::gray());
+ vis.discover_vertex(u, g);
+
+ while (!stack.empty()) {
+ VertexInfo& back = stack.back();
+ u = back.first;
+ tie(ei, ei_end) = back.second;
+ stack.pop_back();
+ while (ei != ei_end) {
+ v = target(*ei, g);
+ vis.examine_edge(*ei, g);
+ v_color = get(color, v);
+
+ if (v_color == Color::white()) {
+ vis.tree_edge(*ei, g);
+ stack.push_back(make_pair(u, make_pair(++ei, ei_end)));
+ u = v;
+ tie(ei, ei_end) = out_edges(u, g);
+ put(color, u, Color::gray());
+ vis.discover_vertex(u, g);
+ } else if (v_color == Color::gray()) {
+ vis.back_edge(*ei, g);
+ ++ei;
+ } else {
+ vis.forward_or_cross_edge(*ei, g);
+ ++ei;
+ }
+ }
+ put(color, u, Color::black());
+ vis.finish_vertex(u, g);
+ }
+ }
+
+ #else // BOOST_NONRECURSIVE_DFS not defined
+
template <class IncidenceGraph, class DFSVisitor, class ColorMap>
void depth_first_visit_impl
(const IncidenceGraph& g,
***************
*** 88,93 ****
--- 155,163 ----
}
put(color, u, Color::black()); vis.finish_vertex(u, g);
}
+
+ #endif
+
} // namespace detail
template <class VertexListGraph, class DFSVisitor, class ColorMap,
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
