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@osl.iu.edu> http://www.osl.iu.edu.edu/~jsiek Ph.D. Student, Indiana University Bloomington C++ Booster (http://www.boost.org) Office phone: (812) 856-1820 _______________________________________________