#4793 closed Bugs (fixed)
copy_component does not work for graphs with edges.
| Reported by: | Owned by: | Jeremiah Willcock | |
|---|---|---|---|
| Milestone: | To Be Determined | Component: | graph |
| Version: | Boost 1.44.0 | Severity: | Problem |
| Keywords: | Cc: |
Description
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)
Change History (10)
by , 12 years ago
| Attachment: | copy_component_kaput.cpp added |
|---|
comment:1 by , 12 years ago
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 by , 12 years ago
| Owner: | changed from to |
|---|---|
| Status: | new → assigned |
comment:3 by , 12 years ago
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:5 by , 12 years ago
| Resolution: | → fixed |
|---|---|
| Status: | assigned → closed |
comment:6 by , 12 years ago
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 by , 12 years ago
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.
Simple test.