Boost logo

Boost :

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

> 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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at