Re: [boost] BGL bidirectional adjacancy_list problem

From: Doug Gregor (dgregor_at_[hidden])
Date: 2004-10-24 23:14:09

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.

> ii) removing properties from the edges changes nothing, a container of 
> no_property's is still
>     maintained.

It looks like the no-property version for bidirectional was never 
actually implemented (most likely due to issues with property 
stability), so we're stuck with this for at least this release cycle.

> As I am not too familiar with the adjacancy_list implementation, can 
> anyone confirm this?

O(|E|) bound and the bug it was intended to fix have been confirmed.

Anyway, I'm on it. Expect a performance fix for 1.32.0.

        Doug