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
O(n)?
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 adjacency list.