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