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-08 14:18:59

I have uploaded a new version, v. 0.5.1, of my Stoer–Wagner algorithm
implementation to the Vault:
http://www.boostpro.com/vault/index.php?action=downloadfile&filename=stoer_wagner_min_cut-0.5.1.tar.bz2&directory=Algorithms/graph

Changes in this revision include:

 1. In `boost::detail::stoer_wagner_phase`, the simple change to
obtaining `pq.keys()` once from obtaining `pq.keys()` each time has
dramatically improved the performance. On a randomly-generated graph
with 500 vertices and 62,864 edges, for example, the runtime went from
5.56 seconds to 1.82 seconds on a Pentium Dual Core.

 2. Documentation for the `UpdatableQueue` and `KeyedUpdatableQueue` concepts.

 3. Modification of a unit test to pass in a "custom" max-priority queue.

Attached are two patches for the current trunk sources, one to
`boost/graph/detail/d_ary_heap.hpp` and the other to
`boost/graph/named_function_params.hpp`. I changed both files for this
version, so if you have applied any of my previous patches, please
revert your local copy of these files and apply the new patches.

I found the `Algorithms/graph` directory in the Vault, which is
probably a better place for BGL archives. Thus, I have uploaded v.
0.5.1 to `Algorithms/graph` and will delete the v. 0.5 archive from
the `BGL` directory which I created.

Let me know if there are further changes that I should make.

Daniel