Opened 5 years ago

Closed 5 years ago

#7863 closed Bugs (wontfix)

Bad graph after removing named vertex and then adding it again.

Reported by: colsebas@… Owned by: Jeremiah Willcock
Milestone: To Be Determined Component: graph
Version: Boost 1.52.0 Severity: Problem
Keywords: Cc:


Attached is a thin wrapper around boost::adjacency_list. Swapping lines 155 and 156 will switch between expected behavior and a corrupted graph Seems to be related to re-adding a vertex that was previously removed.

Attachments (1)

graphing.cpp (4.2 KB) - added by anonymous 5 years ago.

Download all attachments as: .zip

Change History (7)

Changed 5 years ago by anonymous

Attachment: graphing.cpp added

comment:1 Changed 5 years ago by Jeremiah Willcock

On lines 121 and 124, you are using *tv even after that vertex might have been deleted (on 121, it is known to have been deleted). Your comment about *fv being invalid after *tv has been removed is correct; in a graph with vecS vertex container, removing one vertex invalidates all other vertex descriptors.

comment:2 Changed 5 years ago by anonymous

A bug for sure on line 121, but on 124 the vertex would still be valid as it hasn't been removed. Either way those lines are there as I was trying to figure out what was wrong, and the bug reported stands whether none, either, or both lines 121, 124 are commented out.

Final tree when connect called after disconnect: b->d

Final tree when disconnect called after connect: c->b, a->b, c->d, b->d

comment:3 Changed 5 years ago by Jeremiah Willcock

It looks like you cannot use a vecS vertex container with a named_graph when you remove vertices; there is nothing that updates the name lookup table based on the new vertex descriptors. Because unrelated vertex descriptors might be invalidated by remove_vertex, the table might need to be entirely rebuilt in that case. Could you please try listS or setS as vertex container (the second template parameter to adjacency_list) instead of vecS?

comment:4 Changed 5 years ago by Jeremiah Willcock

(In [82498]) Added check to prevent use of remove_vertex on named adjacency list graphs with vecS vertex container (since it does not work and could not be made to work efficiently); refs #7863

comment:5 Changed 5 years ago by anonymous

I've since updated to listS and things work as I want...but the vecS was definitely doing things it shouldn't so reported it.

comment:6 Changed 5 years ago by Jeremiah Willcock

Resolution: wontfix
Status: newclosed

You were right to report the issue; I added a check now so that other users will not get the same kind of subtle run-time error that you experienced.

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.