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

Subject: Re: [boost] [Boost-users] [BGL] Stoer–Wagner min-cut algorithm
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-06-23 09:25:07

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

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 <boost/graph/lookup_edge.hpp>) 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 <boost/graph/iteration_macros.hpp> 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 
<boost/graph/iteration_macros_undef.hpp> 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