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

Subject: Re: [boost] [BGL] Stoer–Wagner min-cut algorithm
From: Daniel Trebbien (dtrebbien_at_[hidden])
Date: 2010-07-04 17:38:36

Hello Jeremiah,

I commented below.

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

I figured that I would allow it as an input parameter for the same
reason as why `assignments` and `wAs` are possible input parameters:
all three are utility maps that have meaningless values at algorithm
completion, so the temporary, underlying storage of the maps can be
created if not specified, but the user might not need to create a
`std::vector` backing for them because perhaps the per-vertex utility
values were made into vertex properties, or perhaps the user wishes to
use a container that is backed by a custom allocator.

Following similar reasoning, I was thinking about a HeapContainer
input parameter. What do you think?

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

Oh, my mistake. I meant to alias `vertex_assignment_map` and
`assignment_map` rather than `vertex_parity_map` and `parity_map`.

I was thinking about writing an implementation of a randomized min-cut
algorithm by Karger that merges edges rather than vertices. This might
require an `edge_assignment_map` and `vertex_assignment_map`. I'm not
sure. Perhaps this change can come later if I decide to implement this
algorithm.

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

I could use "black" and "white". That will work.

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

No, I figured that the user might not be interested in the vertex
parities, so the default `dummy_property_map` would throw away this
information.

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

Okay

> 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()().

I see it in Subversion, and will switch to using it. Thank you.

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

Sure, I'll switch the code to two spaces.

What style changes do I need to make to make it K&R style?

> Could you please use a Boost directory layout for your code?

Sure

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

In the "Algorithms" chapter, I think that a section titled "Min-Cut
Algorithms" should be added between "Maximum Flow and Matching
Algorithms" and "Sparse Matrix Ordering Algorithms" because min-cuts
are related to max-flow algorithms:
http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem