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:
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk