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
> 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
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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk