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