[Boost-users] [graph] set of edges

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
<andrew.n.sutton_at_[hidden]> wrote:
>> 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
> :)

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.

Thanks,

--Michael Fawcett

P.S. sorry for the subject line mess up.