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 23:25:55

On Sun, 4 Jul 2010, Daniel Trebbien wrote:

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

Right now, Dijkstra's algorithm creates those structures internally in the 
normal case.  I'm fine with making the heap an optional parameter, but not 
the underlying storage.  I guess it makes sense to allow the 
index_in_heap_map to be a parameter; that could then be added to 
Dijkstra's algorithm as well.

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

OK.  Is there a reason that you need two names for that?  It is much 
simpler to have only one name for each parameter; that avoids having to 
use the duplicate name list (which is for parts of BGL that have aliased 
parameter names for backwards compatibility).

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

We can just add both of those now.

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

It's fine if the partition map has bool as its value type, so you don't 
need to change your code other than the name.

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

I thought that the parities were the (only) output of the algorithm.  Is 
there ever a case where the user would not want that?

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

It turns out that we actually use a two-space variant of the Java standard 
coding style (that you can find online).  I think 
<URL:http://osl.iu.edu/download/research/mtl/papers/code_stds.pdf> (see 
pages starting at 25) is still reasonably accurate, except for the 
formatting of the opening braces of functions.  Of course, anything that's 
explicitly specified in the Boost requirements takes precedence.

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

Thanks.  That will make testing and integrating it much easier.

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

Are you sure that you don't want me to add "min-cut" to the maximum flow 
section title and then put your code in there?  How related is your code 
to standard max-flow algorithms?

BTW, what is the timeframe that you expect to have this finished?  Are you 
targeting getting it into 1.44.0?  That would require a working version of 
the code by tomorrow (July 5), but that would not need documentation and 
would probably only require minimal tests.  It would be more pressure, 
though, and it is probably not too important to get it into the absolute 
next version.

-- Jeremiah Willcock