Subject: Re: [boost] [BGL] StoerâWagner min-cut algorithm
From: Daniel Trebbien (dtrebbien_at_[hidden])
Date: 2010-07-06 19:32:17
> Why do you need to get the "distances" (values) from the heap itself
> rather than from a separate distance map? The heap itself does not store
> distances, after all; it needs a separate data structure (or function) to
> get the distance to any given vertex. In fact, the fact that there is a
> distance map at all is a convenience/performance optimization in
> d_ary_heap; the Boost mutable_queue doesn't use a property map for
> distances at all (other than through indirect_cmp). What are you using
> the keys() map for? Maybe there is another way to do the same thing.
I liked your idea of making the heap/max-priority queue an optional
parameter, so I started work on allowing this.
The "phase" routine of the StoerâWagner algorithm is very similar to
the algorithms of Dijkstra and Prim. There is a priority queue that is
used to iteratively retrieve the vertex with the highest
key/"distance"/wA. I need access to the wA values of vertices because
the wA of the vertex that is removed last is the weight of a minimum
s-t cut that was computed by the phase.
I just finished a batch of changes that allow the optional
max-priority queue, and I uploaded the archive of this new version to
the Vault: http://www.boostpro.com/vault/index.php?action=downloadfile&filename=stoer_wagner_min_cut-0.5.tar.bz2&directory=BGL
It requires a patch to `named_function_params.hpp` which I have
attached to this e-mail.
The v. 0.5 archive includes a modified
(BTW, I skipped to 0.5 as the version number because I have a version
which I am calling "version 0.4", but this is an intermediary
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk