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-05 08:10:10

> [snip]
>> 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).

There's no particular reason. I was just trying to emulate what I
perceived to be the convention of creating an alias for parameter
names that might be confused.

> [snip]
>> 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?

I don't know for sure. Personally I think that I would always want to
know, but maybe someone does not.

In my view it's kind of like the `comp` map of `connected_components`.
It is a required parameter, but there were a couple of cases where I
just needed to know whether a graph was connected, so I was only
interested in the return value.

> [snip]
> 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?

I don't think that a section on min-cuts should go *in* the section on
maximum flow algorithms because although the two are related, a
min-cut algorithm does not need to exploit the duality of maximum
flow/weight of minimum cut. In fact, the Stoer–Wagner algorithm does
not, and a number of recent algorithms do not.

It makes sense to me that a user would expect the section on min-cut
algorithms to immediately follow the section on maximum flow
algorithms because historically, maximum flow was seen as *the*
solution to finding min-cuts for a long time. (Karger & Stein (1996).
"A new approach to the minimum cut problem".) Today, the relationship
of minimum cuts to maximum flow problems is mentioned more for
historical context.

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

I think that 1.44 is too soon. Perhaps the next release  :)