Modify

Ticket #4793 (closed Bugs: fixed)

Opened 3 years ago

Last modified 3 years ago

copy_component does not work for graphs with edges.

Reported by: Christopher Alfeld <calfeld@…> Owned by: jewillco
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

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

Change History

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

Simple test.

comment:1 Changed 3 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 3 years ago by jewillco

  • Owner changed from asutton to jewillco
  • Status changed from new to assigned

comment:3 Changed 3 years ago by jewillco

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 3 years ago by Christopher Alfeld <calfeld@…>

Great! Thank you for the incredibly rapid response.

comment:5 Changed 3 years ago by jewillco

  • Status changed from assigned to closed
  • Resolution set to fixed

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

comment:6 Changed 3 years ago by jewillco

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 3 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 3 years ago by jewillco

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

comment:9 Changed 3 years ago by jewillco

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

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
The resolution will be deleted. Next status will be 'reopened'
Author


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

 
Note: See TracTickets for help on using tickets.