Opened 10 years ago

Closed 9 years ago

#1622 closed Bugs (fixed)

Adjacency list needs to handle self-edges correctly

Reported by: Aaron Windsor Owned by: Andrew Sutton
Milestone: Boost 1.36.0 Component: graph
Version: Boost 1.34.1 Severity: Problem
Keywords: Cc:


The following short program crashes as of boost 1.35:

#include <boost/graph/adjacency_list.hpp>

int main() {

using namespace boost; typedef adjacency_list<vecS, vecS, undirectedS > graph_t; graph_t g(5); add_edge(2, 2, g); remove_edge(2, 2, g);


The problem is that (2,2) is stored once in the list of edges in the graph and twice in the list of adjacent edges to the vertex 2. When remove_edge is called, the global graph edge (2,2) is deleted twice, causing a segfault. This problem is discussed in the following thread:

Attachments (0)

Change History (3)

comment:1 Changed 10 years ago by Aaron Windsor

Status: newassigned

comment:2 Changed 9 years ago by Andrew Sutton

Owner: changed from Aaron Windsor to Andrew Sutton
Status: assignednew

Removing the loop using remove_edge(e, g) does not seem to trigger the same segfault.

comment:3 Changed 9 years ago by Andrew Sutton

Resolution: fixed
Status: newclosed

(In [50206]) Fixed #1622. A viable solution relies on the fact that incident edges in a loop are stored adjacently in the out edge list of the vertex. A simple modification of the global edge erasing loop for undirected graphs will skip the next iterator if both the current and next contain the same iterator.

Modify Ticket

Change Properties
Set your email in Preferences
as closed The owner will remain Andrew Sutton.
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.