[boost] Re: Bug? adjacency_list: edge takes linear not logarithmic time

From: Alan Stokes (alan_at_[hidden])
Date: 2004-01-21 10:59:09

Another performance issue, not directly related to the last one:

I have a bidirectional adjacency list where edges are held in a set (and 
vertices in a list). The vertices have a property, the edges don't.

By experiment, calling remove_edge(e, g) (where e is an edge descriptor) ends up 
calling bidirectional_graph_helper_with_property::remove_edge, which is O(E/V) - 
it does a linear search of the in edges and out edges. But removing an edge from 
a set ought to be O(log(N).

In fact that's why I'm using a set for the edge list - 
http://www.boost.org/libs/graph/doc/using_adjacency_list.html#sec:choosing-graph-type 
says "remove_edge() ... For set-based EdgeList types this is implemented with 
the erase() member function, which has average time log(E/V). ".

Rather oddly, remove_edge(u, v, g) for the same graph does have log time - it 
has an extra layer that dispatches on the allow/disallow parallel edges trait.

I suspect a fix would be to change remove_edge(e, g) from this:
     template <class EdgeOrIter, class Config>
     inline void
     remove_edge(EdgeOrIter e,
                 bidirectional_graph_helper_with_property<Config>& g_)
     {
       g_.remove_edge(e);
     }

to this:
     template <class EdgeOrIter, class Config>
     inline void
     remove_edge(EdgeOrIter e,
                 bidirectional_graph_helper_with_property<Config>& g_)
     {
       remove_edge(source(e, g), target(e g), g);
     }

(This is lines 1069 onwards in revision 1.112 of 
boost/graph/detail/adjacency_list.hpp)

- Alan