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.