Boost logo

Boost :

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,

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at