Boost logo

Boost :

From: Douglas Gregor (gregod_at_[hidden])
Date: 2003-08-28 11:34:49


Vladimir,
        The patch you recently checked in:

revision 1.36
date: 2003/08/28 11:48:59; author: vladimir_prus; state: Exp; lines: +53
-18
Implement depth_first_visit variant which allows to stop the search at
certain vertices.

        breaks depth_first_search by aborting before it starts unless a different
TerminatorFunc is specified. I've checked in the patch below to fix this.

        Doug

Index: depth_first_search.hpp
===================================================================
RCS file: /cvsroot/boost/boost/boost/graph/depth_first_search.hpp,v
retrieving revision 1.36
diff -u -r1.36 depth_first_search.hpp
--- depth_first_search.hpp 28 Aug 2003 11:48:59 -0000 1.36
+++ depth_first_search.hpp 28 Aug 2003 16:31:14 -0000
@@ -76,9 +76,9 @@

   namespace detail {

- struct truth2 {
+ struct nontruth2 {
       template<class T, class T2>
- bool operator()(const T&, const T2&) const { return true; }
+ bool operator()(const T&, const T2&) const { return false; }
     };

@@ -127,7 +127,7 @@
       put(color, u, Color::gray());
       vis.discover_vertex(u, g);
       tie(ei, ei_end) = out_edges(u, g);
- if (static_cast<TF&>(func)(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 {
@@ -166,7 +166,7 @@
     }

 #else // BOOST_RECURSIVE_DFS is defined
-
+
     template <class IncidenceGraph, class DFSVisitor, class ColorMap,
               class TerminatorFunc>
     void depth_first_visit_impl
@@ -219,14 +219,14 @@
     }

     if (start_vertex != *vertices(g).first){ vis.start_vertex(start_vertex,
g);
- detail::depth_first_visit_impl(g, start_vertex, vis, color,
- detail::truth2());
+ detail::depth_first_visit_impl(g, start_vertex, vis, color,
+ detail::nontruth2());
     }

     for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
       ColorValue u_color = get(color, *ui);
       if (u_color == Color::white()) { vis.start_vertex(*ui, g);
- detail::depth_first_visit_impl(g, *ui, vis, color, detail::truth2());
+ detail::depth_first_visit_impl(g, *ui, vis, color,
detail::nontruth2());
       }
     }
   }
@@ -360,14 +360,14 @@
      DFSVisitor vis, ColorMap color)
   {
     vis.start_vertex(u, g);
- detail::depth_first_visit_impl(g, u, vis, color, detail::truth2());
+ detail::depth_first_visit_impl(g, u, vis, color, detail::nontruth2());
   }

   template <class IncidenceGraph, class DFSVisitor, class ColorMap,
             class TerminatorFunc>
   void depth_first_visit
     (const IncidenceGraph& g,
- typename graph_traits<IncidenceGraph>::vertex_descriptor u,
+ typename graph_traits<IncidenceGraph>::vertex_descriptor u,
      DFSVisitor vis, ColorMap color, TerminatorFunc func = TerminatorFunc())
   {
     vis.start_vertex(u, g);


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk