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