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

Subject: Re: [boost] [BGL] Stoer–Wagner min-cut algorithm
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-07-04 16:23:45

On Sun, 4 Jul 2010, Daniel Trebbien wrote:

>> Attached is version 0.3 of my Stoer–Wagner algorithm implementation
>
> I cleaned up the list of includes in `stoer_wagner_mincut.hpp`, made a
> few, minor changes to comments, and replaced `*vertices(g).first` as
> the initial value of the default assignments map with
> `vertex_descriptor()`.
>
> Attached is a unified diff from v. 0.3 `stoer_wagner_mincut.hpp` to
> what I am calling v. 0.3.1 `stoer_wagner_mincut.hpp`.
>
> Lines 199 through 268 of v. 0.3 are now lines 194 through 263 of v. 0.3.1.

Here are my comments:

I appreciate that you changed to Boost naming conventions.  I was going to 
comment on that in the last version but you changed it before I commented 
on it.

Why do you have IndexInHeapMap as an input parameter to the algorithm?  Do 
you expect that a user would ever pass it in directly?

What is the difference between parity_map and vertex_parity_map, 
especially considering that you do not appear to use the second in your 
algorithm?  Will you ever use vertex_parity_map as a named parameter name? 
That is the only reason it should appear in the list of duplicate 
parameter names.  I think just having vertex_parity_map as an alias to 
parity_map is not enough of a reason to have it as a parameter name.

The code in <boost/graph/bipartite.hpp> uses a partition map to record its 
result, either passed in by the user or created internally.  Is it 
possible for you to use that name as well?  Or does it not make sense for 
your algorithm?  There is currently on named parameter for that, since the 
code in bipartite.hpp does not use named parameters; that could be added, 
though.

Your default for parity_map is dummy_property_map; did you mean instead to 
use the vertex_parity_map from the graph if it has one?

If vertex_assignment_map is a temporary for the user-exposed parts of your 
algorithm, it should not be an explicit parameter; it should be generated 
instead (like index_in_heap_map is for dijkstra_shortest_paths()).

BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS does not have a semicolon after 
the argument list.

I refactored the color_map_maker code in named_function_params.hpp so it 
would be more useful for you.  You should now just be able to write 
objects like make_color_map_from_arg_pack for the property maps that you 
need to create.  Note that if you have a different value type for each map 
that you are creating, you can leave off the second template argument to 
make_property_map_from_arg_pack_gen (and the default value from its 
constructor) and then pass the default value that you want into the 
generated class's operator()().

Switching to two-space indentation and K&R-style formatting in your code 
will make the lines shorter and make it fit better with existing BGL code.

Could you please use a Boost directory layout for your code?  In 
particular, the names test.cpp and index.html are not going to be the 
names that your files have eventually, and having spaces in file names is 
not allowed in Boost.  Is the .cpp file in your documentation directory 
meant to be an example?  If so, please move it into libs/graph/example in 
your tarball.  You do not need to create Jamfiles, but please note in a 
README or somewhere if any of your tests or examples need to be linked to 
any libraries or need any command line arguments.

Where do you think your function should go in the BGL table of contents? 
What name should I use for it and what section should it be under?

-- Jeremiah Willcock