Re: [boost] BGL bidirectional adjacancy_list problem

From: Doug Gregor (dgregor_at_[hidden])
Date: 2004-10-25 20:11:45

On Oct 24, 2004, at 9:14 PM, Doug Gregor wrote:
> On Oct 21, 2004, at 6:22 PM, Hugo Duncan wrote:
>> We just updated to a recent cvs version of boost, and an algorithm 
>> that was taking three minutes
>> is now running for over an hour.  I think there are two problems, but 
>> am not at all sure of the
>> analysis:
>>
>> The proximate cause seems to be the correction of the remove_edge 
>> function for bidirectional
>> adjacancy_list based graphs in around June.  Trying to see how to 
>> speed things up, I have run
>> into these problems
>>
>> i) remove_edge is now O(E), due to the edge properties being stored 
>> on the graph rather than
>>    on a vertex.
>
> Ouch! Yep, we're doing a linear search to find the edge property to 
> remove.
> [snip]
> Anyway, I'm on it. Expect a performance fix for 1.32.0.

Fixed when EdgeListS has stable iterators (e.g., when it uses the 
default listS). Hugo, I would appreciate if you could verify that the 
horrible performance you were getting is improved by this patch.

Unfortunately, adjacency_list is broken in this area and we aren't 
going to fix it for release. If this patch works out for Hugo, I'll 
move it into the branch immediately and will update the documentation 
to reflect the limitations (i.e., don't remove edges if you use 
EdgeList=vecS). Compile the attached test case under some debugging STL
(-D_GLIBCXX_DEBUG for GCC 3.4 or Apple GCC 3.3) to see the problem: I 
don't have a solution yet.

        Doug