Opened 8 years ago

Closed 8 years ago

Last modified 8 years ago

#4793 closed Bugs (fixed)

copy_component does not work for graphs with edges.

Reported by: Christopher Alfeld <calfeld@…> Owned by: Jeremiah Willcock
Milestone: To Be Determined Component: graph
Version: Boost 1.44.0 Severity: Problem
Keywords: Cc:


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.

Attachments (1)

copy_component_kaput.cpp (519 bytes) - added by Christopher Alfeld <calfeld@…> 8 years ago.
Simple test.

Download all attachments as: .zip

Change History (10)

Changed 8 years ago by Christopher Alfeld <calfeld@…>

Attachment: copy_component_kaput.cpp added

Simple test.

comment:1 Changed 8 years ago by Christopher Alfeld <calfeld@…>

One possibly fix would be to have tree_edge(e,g) create a vertex for target(e,g) and the edge for e, and have non_tree_edge(e,g) create an edge for e using the already existing target(e,g).

comment:2 Changed 8 years ago by Jeremiah Willcock

Owner: changed from Andrew Sutton to Jeremiah Willcock
Status: newassigned

comment:3 Changed 8 years ago by Jeremiah Willcock

With the method you suggested, you only need to specifically copy the source vertex since every other vertex in the component is the target of some tree or non-tree edge. Thus, your approach actually simplifies the code further by removing the examine_vertex hook. I am working on fixing this bug the way you suggested.

comment:4 Changed 8 years ago by Christopher Alfeld <calfeld@…>

Great! Thank you for the incredibly rapid response.

comment:5 Changed 8 years ago by Jeremiah Willcock

Resolution: fixed
Status: assignedclosed

(In [66203]) Repaired copy_component() using suggestion from Christopher Alfeld; fixes #4793

comment:6 Changed 8 years ago by Jeremiah Willcock

Could you please try your code again with the version I just committed to the trunk? Please try valgrind on it as well if you have a platform that supports it.

comment:7 Changed 8 years ago by Christopher Alfeld <calfeld@…>

Code does not compile. On line 404, you call copy_one_vertex with a single argument, when it takes two.

After fixing that error (adding g_in as the second argument) code runs correctly and valgrind reports no errors.

comment:8 Changed 8 years ago by Jeremiah Willcock

(In [66204]) Fixed signature of copy_one_vertex(); refs #4793

comment:9 Changed 8 years ago by Jeremiah Willcock

(In [66206]) Merged r66203 and r66204 from trunk; refs #4793

Modify Ticket

Change Properties
Set your email in Preferences
as closed The owner will remain Jeremiah Willcock.
The resolution will be deleted.

Add Comment

E-mail address and name can be saved in the Preferences.

Note: See TracTickets for help on using tickets.