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