Re: [boost] [BGL] Stoer–Wagner min-cut algorithm

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
`libs/graph/doc/graph_theory_review.html`.

(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
version.)