Modify

Ticket #1622 (closed Bugs: fixed)

Opened 6 years ago

Last modified 5 years ago

Adjacency list needs to handle self-edges correctly

Reported by: aaron_windsor Owned by: asutton
Milestone: Boost 1.36.0 Component: graph
Version: Boost 1.34.1 Severity: Problem
Keywords: Cc:

Description

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:  http://lists.boost.org/Archives/boost/2007/02/116547.php.

Attachments

Change History

comment:1 Changed 6 years ago by aaron_windsor

  • Status changed from new to assigned

comment:2 Changed 5 years ago by asutton

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

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

comment:3 Changed 5 years ago by asutton

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

(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.

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.