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.)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk