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

From: Feldman, Yulik (yulik.feldman_at_[hidden])
Date: 2005-07-24 01:59:04

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 <class EdgeList, class vertex_descriptor>

    void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,

                                   allow_parallel_edge_tag)

    {

      boost::graph_detail::erase_if(el,
detail::target_is<vertex_descriptor>(v));

    }

 

Then:

 

template <class Container, class Predicate>

  void erase_if(Container& c, Predicate p)

  {

    erase_if_dispatch(c, p, container_category(c),
iterator_stability(c));

  }

 

Then:

 

template <class AssociativeContainer, class Predicate>

  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.