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:
// O(E/V)
template
void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
allow_parallel_edge_tag)
{
boost::graph_detail::erase_if(el,
detail::target_is(v));
}
Then:
template
void erase_if(Container& c, Predicate p)
{
erase_if_dispatch(c, p, container_category(c),
iterator_stability(c));
}
Then:
template
void erase_if_dispatch(AssociativeContainer& c, Predicate p,
associative_container_tag, stable_tag)
{
typename AssociativeContainer::iterator i, next;
for (i = next = c.begin(); next != c.end(); i = next) {
++next;
if (p(*i))
c.erase(i);
}
}
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.
--Yulik.
