[Boost-users] [BGL] Stoer–Wagner min-cut algorithm

Subject: [Boost-users] [BGL] Stoer–Wagner min-cut algorithm
From: Daniel Trebbien (dtrebbien_at_[hidden])
Date: 2010-06-19 21:08:37

> The usual idiom for that in BGL algorithms is to use an
> iterator_property_map on the graph's vertices, built using a vector and
> indexed by the vertex_index property map of the graph.  You can also use a
> shared_array_property_map, which manages its storage internally.  If you
> are doing a generic algorithm, the logic to manage these maps correctly is
> somewhat difficult.  One place to look for a template of what to do is the
> distance map handling at the bottom of
> <boost/graph/dijkstra_shortest_paths.hpp>, particularly
> dijkstra_shortest_paths() and detail::dijkstra_dispatch1().  The basic
> logic is to look at the named parameter structure that the user passes is
> and see if there is an assignment map there.  If so, use it; otherwise,
> look for a vertex_index map in the named parameter structure, defaulting
> to get(vertex_index, g), then use the found vertex_index map to create an
> iterator_property_map or shared_array_property_map.  Now that compilers
> are more compliant, there are probably simpler ways to implement the logic
> than to use multiple dispatch functions, but the approach in
> dijkstra_shortest_paths.hpp is known to work.
>
> When you get this algorithm done, you may want to contribute it to BGL to
> be added to Boost.  We are always interested in new algorithms.
>
> -- Jeremiah Willcock

Hello Jeremiah,

I would very much like to contribute my implementation of the
Stoer–Wagner min-cut algorithm to BGL. In preparation for this, I have
attached a "pre-release" version to this e-mail which has everything
needed to build the test case with g++ and GNU Make.

Before I add in all of the template code to support "default" template
parameters and other niceties, I figured that it would be good to have
a review of the code to make sure that I am headed in the right
direction. Also, I have tested my code against the example from Stoer
& Wagner (1997). It appears to be working correctly, but there might
be bugs. I think that it would be good to have more testing.

Would someone please review my code? Also, is anyone aware of good
examples for testing min-cut implementations?

Daniel