Re: [Boost-users] performance issue with graph edge removal

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-07-25 16:55:28

On Jul 24, 2005, at 1:59 AM, Feldman, Yulik wrote:

> I’ve also noticed that when in/out edge lists are stored in an 
> associative container and the parallel edges are allowed, i.e multiset 
> is used, the functions remove_edge()/clear_vertex() do not work as 
> efficient as they could. The calls to these functions (in my case) 
> result in the following sequence of calls:
> [snip code]
> The complexity of the search operation is linear, so multiset doesn’t 
> provide a performance advantage over containers such as vector or set. 
> However, the function erase_if_dispatch() could use multiset’s 
> equal_range() member function, which would result in O(log n) 
> complexity of the search. I understand that the reason 
> erase_if_dispatch() is written in the way it is written, is probably 
> that the function is generic with regard to the predicate and doesn’t 
> do assumptions on it. However, in the case erase_if_dispatch() is 
> called from erase_from_incidence_list(), where the predicate is set, 
> the function (its special specialization) could make assumption that 
> the predicate is actually the same as the predicate used to sort the 
> in/out edge list itself (the target vertex), and therefore could use 
> equal_range() to boost the performance of the function.

We did some work in this area for 1.33.0, but we didn't fix this 
particular performance problem. It seems that erase_from_incidence_list 
should really look at the selector for the edge list to determine if we 
should (1) erase one element quickly, (2) erase an element range 
quickly, or (3) step through the list linearly erasing elements.

Would you be able to supply a patch to do this? I'll be happy to review 
it and put it in for the next (post-1.33.0) Boost release.

        Doug