id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
9770,Finish_edge event misbehavior.,edwin.carlinet@…,Jeremiah Willcock,"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());
}}}










   
",Bugs,new,To Be Determined,graph,Boost 1.55.0,Problem,,,