BGL bidirectional adjacancy_list problem
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. ii) removing properties from the edges changes nothing, a container of no_property's is still maintained. As I am not too familiar with the adjacancy_list implementation, can anyone confirm this? Hugo
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
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
Doug, Many thanks for dealing with this! On Mon, 25 Oct 2004 Doug Gregor wrote:
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.
It is somewhat improved. The speed isn't completely what it was (to be expected), but I have not yet convinced myself that there is no memory leak. I have been testing with a pre-mpl update cvs version with your latest graph changes. Sorry to be imprecise, but I'd like to test with a self consistent boost version which will probably take until next week. Having said that, if it passes the regression tests it is definitely a speed improvement.
Unfortunately, adjacency_list is broken in this area and we aren't going to fix it for release.
It would also be nice to have a specialisation for the no edge property case. Many thanks. Hugo
On Oct 28, 2004, at 4:37 AM, Hugo Duncan wrote:
It would also be nice to have a specialisation for the no edge property case.
That turns out to be a bit complicated because removing the underlying edge list entirely makes parallel edges indistinguishable. I think I know how to reimplement that part of adjacency_list more efficiently, but it can't happen for this release. Doug
On Thu, 28 Oct 2004 Doug Gregor wrote:
That turns out to be a bit complicated because removing the underlying edge list entirely makes parallel edges indistinguishable.
Only a problem if you have parallel edges :-) (does this imply that the use of parallel edges has a perfrmance trade-off?)
I think I know how to reimplement that part of adjacency_list more efficiently, but it can't happen for this release.
I'd be happy if it makes it into the library at any point. Hugo
participants (2)
-
Doug Gregor -
Hugo Duncan