On 2010-06-19, Daniel Trebbien wrote:

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.

(Added a new test case against my own example. See the new `test.cpp` that is attached.)

On Sat, 19 Jun 2010, Daniel Trebbien wrote:

...

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 , 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?

I skimmed through your code, and saw couple of little things to change: - Boost code doesn't use tabs (URL:http://www.boost.org/community/policy.html#tabs) - I don't think you need to use BOOST_DEDUCED_TYPENAME; I just use "typename" myself and haven't had any problems. I think it might be a workaround for compilers that are not used anymore. - Your header guard should start with BOOST_GRAPH_ to avoid conflicts with other header files. - You can replace "c.size() > 0" by "!c.empty()"; this is likely to be faster for many containers. - Your non-detail code should be in the "boost" namespace. - From a superficial look, it seems like maxAdjSearchList might be implementable as a heap (or some other priority queue) rather than as a multiset. Am I mistaken on that? - Operations on graphs and property maps (but not on tuples) need to use unqualified names (such as "get" and "target") in order for ADL to work on user-defined graph types that are not in the boost namespace. Calls to "tie", however, must be qualified (I had to fix many of those yesterday because unqualified calls to tie break C++0x compilers). - Is there a reason that you do not handle parallel edges? Is it just a simplification in the code? - It looks like the code handling sOutEdges and tOutEdges is unnecessarily complicated. Are you just intersecting the two lists of out edges? If so, you can use lookup_edge (from ) to allow edge lookups in constant time for adjacency matrices (however, unlike the map-based implementation, lookup_edge takes linear time when it must actually do a search). - You may want to use the macros in to simplify your code. Those macros replace explicit declarations of iterators and tie operations when you are doing a simple iteration through vertices, out edges, etc. If you use them, please include at the end of your file. - Property maps are passed by copy; they are intended to be lightweight and using copies allows temporary property maps to be passed in. - Are users always going to pass in all of the parameters you have in your algorithm? If not, overloads or named parameters may be worthwhile to add. - As you stated, your code needs a license banner. - You will eventually need a documentation file, preferably in HTML that is styled like the existing BGL documentation. - I think you can just attach the header file to your emails, since the test code is in a separate email anyway. Also, it would make my life easier if you wrote your code/tests as if your header was in boost/graph/, since that is where it will end up eventually. If you do that, I will test it in place there as well. -- Jeremiah Willcock