[Boost-bugs] [Boost C++ Libraries] #9770: Finish_edge event misbehavior.

Subject: [Boost-bugs] [Boost C++ Libraries] #9770: Finish_edge event misbehavior.
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-03-11 14:20:04

#9770: Finish_edge event misbehavior.
------------------------------+----------------------
 Reporter:  edwin.carlinet@…  |      Owner:  jewillco
     Type:  Bugs              |     Status:  new
Milestone:  To Be Determined  |  Component:  graph
  Version:  Boost 1.55.0      |   Severity:  Problem
 Keywords:                    |
------------------------------+----------------------
 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());
 }}}

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/9770>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.