Finish_edge event misbehavior.

[edwin.carlinet@…]

Consider the following diamond DAG:

  3
 / \
1   2
 \ /
  0

A depth first search on this graph with a visitor that records the on-finish-vertex and on-vinish-edge events should output something that:

Finish vertex: 3
Finish vertex: 1
Finish edge: (1,3)
Finish edge: (2,3)
Finish vertex: 2
Finish edge: (0,1)
Finish vertex: 0
Finish edge: (0,2

But it acually outputs:

Finish vertex: 3
Finish edge: (1,3)
Finish vertex: 1
Finish edge: (1,3)
Finish edge: (2,3)
Finish vertex: 2
Finish edge: (0,2)
Finish vertex: 0
Finish edge: (0,2)

The edge (0,2) is seen twice while (0,1) not at all (see the attachment).

The problem comes from "boost/graph/depth_first_search.hpp" in depth_first_visit_impl(). The variable "src_e" is overwritten during the propagation with another tree edge.

The following simple fix solves the problem:

--- /tmp/depth_first_search.hpp	2014-03-11 15:11:53.616272419 +0100
+++ boost/graph/depth_first_search.hpp	2014-03-11 15:11:14.854137441 +0100
@@ -143,8 +143,8 @@
           ColorValue v_color = get(color, v);
           if (v_color == Color::white()) {
             vis.tree_edge(*ei, g);
-            src_e = *ei;
+            Edge src_e = *ei;
	     stack.push_back(std::make_pair(u, std::make_pair(src_e, std::make_pair(++ei, ei_end))));
             u = v;
             put(color, u, Color::gray());

[anonymous]

Minimum bug example.

[edwin.carlinet@…]

The fix I proposed a few hours ago is just as wrong as the original code. The problem is still related to the source edge but not in the way I thought: the source edge inserted in the stack is not the right one.

Hope that this really fix the problem.

@@ -25,6 +25,7 @@
 #include <boost/parameter.hpp>
 #include <boost/concept/assert.hpp>
 #include <boost/tti/has_member_function.hpp>
+#include <boost/utility.hpp>
 
 #include <vector>
 #include <utility>
@@ -143,8 +144,8 @@
           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(src_e, std::make_pair(boost::next(ei), ei_end))));
             src_e = *ei;
-            stack.push_back(std::make_pair(u, std::make_pair(src_e, std::make_pair(++ei, ei_end))));
             u = v;
             put(color, u, Color::gray());
             vis.discover_vertex(u, g);

The outputs of the test code attached below makes more sense:

Finish vertex: 3
Finish edge: (1,3)
Finish vertex: 1
Finish edge: (0,1)
Finish edge: (2,3)
Finish vertex: 2
Finish edge: (0,2)
Finish vertex: 0