Modify

Ticket #7863 (closed Bugs: wontfix)

Opened 16 months ago

Last modified 15 months ago

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

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

Description

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

graphing.cpp Download (4.2 KB) - added by anonymous 16 months ago.

Change History

Changed 16 months ago by anonymous

comment:1 Changed 15 months ago by jewillco

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 15 months 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 15 months ago by jewillco

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 15 months ago by jewillco

(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 15 months 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 15 months ago by jewillco

  • Status changed from new to closed
  • Resolution set to wontfix

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.

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.