Re: [boost] Graph: edge(u,v,g) isn't O(log(E/V)) as promised

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2004-01-30 09:35:26

Hi Alan,

On Jan 30, 2004, at 6:25 AM, Alan Stokes wrote:

> For an adjaceny_list which uses sets for its edges, edge(u, v, g) is  
> supposed to be O(log(E/V)), as you would expect for a lookup in a set.  
> (See  
> http://www.boost.org/libs/graph/doc/using_adjacency_list.html#sec: 
> choosing-graph-type.)
>
> But in fact it is linear in the number of out edges.
>
> This is because in graph/detail/adjacency_list.hpp (line 1325 in  
> revision 1.113), in the edge_dispatch function that handles the  
> disallow_parallel_edge_tag case, the code reads:
>    i = std::find(g.out_edge_list(u).begin(),
>                  g.out_edge_list(u).end(), StoredEdge(v)),
> when it should probably be:
>    i = g.out_edge_list(u).find(StoredEdge(v)),
> as it was in revisions 1.59 and previous.
>

Hmm, I wonder why that change was made... the cvs log just mentions  
fixes for SGI MIPS Pro and STLport.
Oh well. I'll change it back.

> As an aside, it's not that obvious from the documentation that  
> adjacency_list supports edge(u, v, g). AFAICT it's defined only in the  
> AdjacencyMatrix concept, which adjacency_list is not documented as  
> being a model of.

It is there... in the Non-Member Functions section of the documentation  
for adjacency_list.

> [This is a repost - the original was in message 31695 on the 21st of  
> January. But I foolishly reported two different problems with the same  
> subject & in the same thread, only one of which was addressed. I'm  
> assuming the other one was overlooked and so repeating it. I apologise  
> if this assumption is incorrect.]

Yes, I missed this. It does help to separate things out.

Cheers,
Jeremy

_______________________________________________
Jeremy Siek <jsiek_at_[hidden]>
http://www.osl.iu.edu.edu/~jsiek
Ph.D. Student, Indiana University Bloomington
C++ Booster (http://www.boost.org)
Office phone: [phone]
_______________________________________________