Boost Graph Library: parallel edge removal problem
Hello.
I believe I found a bug in the remove_edge function, when the graph is
directed and allows parallel edges. Sometimes an edge simply isn't
removed. I think the problem is that remove_edge uses edge_range
internally, but this function needs an ordered EdgeList (such as
multisetS), and doesn't work properly when it's something like listS.
The attached file shows the problem. It builds a simple graph with a
loop, adds a parallel edge, and tries to remove it. The output of the
program is:
number of edges before removal: 5
number of edges after removal: 5
When EdgeList is changed from listS to multisetS, it works as it should:
number of edges before removal: 5
number of edges after removal: 4
I'm using Boost 1.32.0, with GCC 3.4.3 on GNU/Linux.
Thanks.
--
Tiago de Paula Peixoto
On Nov 20, 2004, at 11:11 PM, Tiago de Paula Peixoto wrote:
I believe I found a bug in the remove_edge function, when the graph is directed and allows parallel edges. Sometimes an edge simply isn't removed. I think the problem is that remove_edge uses edge_range internally, but this function needs an ordered EdgeList (such as multisetS), and doesn't work properly when it's something like listS.
The attached file shows the problem. It builds a simple graph with a loop, adds a parallel edge, and tries to remove it.
Thanks for the perfect test case! The problem was a relatively simple one (misuse of edge_range, unfortunately), but I've just checked the fix into CVS. Doug
participants (2)
-
Doug Gregor -
Tiago de Paula Peixoto