[Boost-bugs] [Boost C++ Libraries] #4793: copy_component does not work for graphs with edges.

Subject: [Boost-bugs] [Boost C++ Libraries] #4793: copy_component does not work for graphs with edges.
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2010-10-26 17:40:13

#4793: copy_component does not work for graphs with edges.
-----------------------------------------------------+----------------------
 Reporter:  Christopher Alfeld <calfeld@…>           |       Owner:  asutton
     Type:  Bugs                                     |      Status:  new    
Milestone:  To Be Determined                         |   Component:  graph  
  Version:  Boost 1.44.0                             |    Severity:  Problem
 Keywords:                                           |  
-----------------------------------------------------+----------------------
 copy_component operates via a BFS visitor.  The visitor adds vertices in
 examine_vertex and edges in examine_edge.  The examine_edge routine
 assumes that examine_vertex has already been called for both sides of the
 edges, i.e., that both the source and target vertex have already been
 added to the copy graph.  However, the BFS algorithm calls examine_edge
 *before* calling examine_vertex for its target.  As a result, the target
 of the added edge is incorrect.

 Concretely, in 1.44, graph/copy.hpp, line 365, the result of
 get(orig2copy, target(e,g_in)) will not be defined.  I'll attach a simple
 program that attempts to copy a graph with 2 vertices and 1 edge before
 them and ends up with the wrong result.

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