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