Boost Users :
Subject: Re: [Boost-users] [graph] set of edges
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-03-17 11:56:24
> So what's the recommendation? The Known Bugs page says that anything
> other than listS is not guaranteed to work for EdgeList, but if
> std::list has O(n) size(), then num_edges()/num_vertices() becomes
> Or were you talking about OutEdgeList?
Both. Any selector of listS will cause corresponding functions that use
size() to be linear. I'm just giving a reminder since it's bitten me before
On a side note, there are two new graph classes in trunk
([un]directed_graph) that wrap listS selected adjacency lisst and provide
O(1) num_* and *degree functions. They also provide builtin index maps and
functinality for renumbering vertices/edges. They aren't really documented
yet and certainly won't be part of the release for a while.
> Are there *known* cases where vecS is bug-free when used for the
> EdgeList? In my case, I know the total number of edges ahead of time,
> and no edges or vertices will ever be removed.
I think the general rule is that if you don't need to remove anything, you
can use vecS wherever you want. It's the removals that really kill the
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net