Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at