From: Jeremy Siek (jsiek_at_[hidden])
Date: 2004-01-21 13:52:38
Hi Alan,
Hmm, I'm not sure that's the right solution. I'll look into it.
-Jeremy
On Jan 21, 2004, at 10:59 AM, Alan Stokes wrote:
> 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
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://listarchives.boost.org/mailman/listinfo.cgi/boost
>
------------------------------------------------------------------------
-----------------
Jeremy Siek http://php.indiana.edu/~jsiek/
Ph.D. Student, Indiana Univ. B'ton email: jsiek_at_[hidden]
C++ Booster (http://www.boost.org) office phone: (812) 856-1820
------------------------------------------------------------------------
-----------------