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

From: Alan Stokes (alan_at_[hidden])
Date: 2004-01-21 06:59:19

I'm looking at boost/graph/detail/adjacency_list.hpp version 1.112, at around 
line 1330. There's a definition of edge_dispatch (which implements edge(u, v, 
g)) for adjacency list graphs where parallel edges are disallowed (i.e. the edge 
list is a set). There's a comment saying that the performance is O(log(E/V)), 
which is what you would expect for a set lookup.

But the actual code calls std::find() on the edge list, which would make it 
O(E/V). Before revision 1.60 the code instead called out_edge_list.find(), which 
would give the specified performance; it's not particularly obvious why the 
change was made in 1.60.

Could this be fixed? It's very useful to be able to efficiently determine if an 
edge is present.

(I think a workaround that would give O(log(E/V)) performance would be to call 
add_edge, then immediately remove the edge if the result indicates it wasn't 
there before. But that seems absurd.)

- Alan