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

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://lists.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: [phone]
------------------------------------------------------------------------ 
-----------------