[boost] Graph Library: target called before examine_edge in depth_first_visit_impl

From: Carl Baldwin (carl_at_[hidden])
Date: 2007-05-08 19:06:52

Greetings,

The following patch implements a proposed change to the graph library's
depth_first_visit implementation.

--- depth_first_search.hpp.orig 2007-05-08 16:29:48.015549215 -0600
+++ depth_first_search.hpp      2007-05-08 16:29:59.147451312 -0600
@@ -116,8 +116,8 @@
         tie(ei, ei_end) = back.second;
         stack.pop_back();
         while (ei != ei_end) {
-          Vertex v = target(*ei, g);
           vis.examine_edge(*ei, g);
+          Vertex v = target(*ei, g);
           ColorValue v_color = get(color, v);
           if (v_color == Color::white()) {
             vis.tree_edge(*ei, g);

There does not seem to be any good reason for target to be called before
examine_edge.  The object, 'v', returned from the call to target is not used
until after the call to examine_edge.

The natural way to perform a depth-first search is to discover a vertex,
examine each edge and follow the edge to its target.  The code should
reflect this natural flow of events as it does with the above patch.

As a real-world example, I have an application that uses the depth-first
visit algorithm to fix some broken edges in a graph.  Each edge in my
application could easily be fixed but it was necessary to fix it before
calling target to discover the target vertex.  Otherwise, the edge is
broken and the wrong target vertex would be returned.

I tried using the examine_edge call-back to fix the edges and was
surprised by the results until I made the change described by my above
patch.

Cheers,
Carl Baldwin