Boost Users :
Subject: [Boost-users] [graph] set of edges
From: Michael Fawcett (michael.fawcett_at_[hidden])
Date: 2009-03-17 12:01:58
On Tue, Mar 17, 2009 at 11:56 AM, Andrew Sutton
>> 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
I'll keep that in mind, thanks.
> 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.
Looking forward to this. We subclassed adjacency_list and made our
own undirected_graph, but I'd like to stop using it and use yours.
>> 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.
Luckily our graphs are immutable, so I'll continue to use vecS for
OutEdgeList and start using it for EdgeList as well.
P.S. sorry for the subject line mess up.
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