Re: [Boost-users] BGL: remove_edge fails under certain circumstances

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-03-21 17:07:01

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