
Boost : 
From: Alan Stokes (alan_at_[hidden])
Date: 20040130 06:25:26
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:choosinggraphtype.)
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk