BGL: remove_edge fails under certain circumstances
Hi, I noticed that with boost 1.32 under gcc 3.4.3 there are cases when remove_edge fails to remove the edge in question. I put this with all kinds of details on bugtracker under http://sourceforge.net/tracker/index.php?func=detail&aid=1166401&group_id=7586&atid=107586 In short the problem appears to be the use of std::equal_range in the code for remove_edge. With a certain order of the vertex and edge creation it happens that equal_range returns an (end_of_list,end_of_list) pair instead of the range that includes the edge in question. I believe this is due to the list not being ordered according to the same "<" operator that std::equal_range invokes. So equal_ranges logic doesn't find the proper range, and remove_edge simply returns without warning and without removing the edge in question. There is more detail in the bug report mentioned above. I am just wondering about a good workaround. Currently I am considering to replace the equal_range call in my copy of the source but there may be a better way. ? Jean -- Jean Utke Argonne National Lab./MCS utke@mcs.anl.gov phone: 630 252 4552 cell: 630 363 5753
On Mar 19, 2005, at 6:47 PM, Jean Utke wrote:
In short the problem appears to be the use of std::equal_range in the code for remove_edge. With a certain order of the vertex and edge creation it happens that equal_range returns an (end_of_list,end_of_list) pair instead of the range that includes the edge in question. I believe this is due to the list not being ordered according to the same "<" operator that std::equal_range invokes. So equal_ranges logic doesn't find the proper range, and remove_edge simply returns without warning and without removing the edge in question. There is more detail in the bug report mentioned above.
The use of equal_range here is clearly wrong. We ran into this bug ourselves a few months ago, and there is an attempt at a fix in Boost CVS. It _should_ solve the problem for you.
I am just wondering about a good workaround. Currently I am considering to replace the equal_range call in my copy of the source but there may be a better way. ?
A quick fix might be to replace edge_range(...) with out_edges, e.g., to initialize "rng" like this: std::pair<out_edge_iterator, out_edge_iterator> rng = out_edges(u, g); The changes to the CVS version of this code use edge_range when it will work (e.g., when we're using setS or multisetS) but falls back to out_edges() otherwise. Doug
Doug Gregor wrote:
The use of equal_range here is clearly wrong. We ran into this bug ourselves a few months ago, and there is an attempt at a fix in Boost CVS. It _should_ solve the problem for you.
Hi Doug, Thanks for the reply. The fix you mentioned works. I can't really afford using CVS/HEAD all the time because that is a moving target. (When I tried to build my stuff with boost head I had to make some unrelated code changes to make it compile for the current HEAD version already). With some rather fundamental stuff like remove_edge failing in 1.32, do you have an idea when you will pack these fixes into a minor release? Jean -- Jean Utke Argonne National Lab./MCS utke@mcs.anl.gov phone: 630 252 4552 cell: 630 363 5753
On Mar 22, 2005, at 12:57 PM, Jean Utke wrote:
With some rather fundamental stuff like remove_edge failing in 1.32, do you have an idea when you will pack these fixes into a minor release?
We've never actually done that with the BGL, but it's a good idea. I'll *try* to do it within the next week or so. Doug
participants (1)
-
Doug Gregor -
Jean Utke