Graph: edge(u,v,g) isn't O(log(E/V)) as promised
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-g....) 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. 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. [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.] - Alan
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 _______________________________________________
Jeremy Siek wrote:
On Jan 30, 2004, at 6:25 AM, Alan Stokes wrote:
As an aside, it's not that obvious from the documentation that adjacency_list supports edge(u, v, g).
It is there... in the Non-Member Functions section of the documentation for adjacency_list.
Ahh, I see it now. Except it says "Returns an edge connecting vertex u to vertex v in graph g." which isn't quite right - it returns a pair, and the edge is only valid if the bool is true. Cheers, Alan
participants (2)
-
Alan Stokes -
Jeremy Siek