Re: [boost] Graph cut questions

Subject: Re: [boost] Graph cut questions
From: Sebastian Nowozin (nowozin_at_[hidden])
Date: 2009-09-17 04:22:36

Dear David,

David Doria wrote:

>>> 2) Is it possible to tell the max flow algorithm to use multiple
>>> sources/sinks?
>> You have to add one global source and sink node and connect everything
>> else to it to achieve this effect.

> 2) I guess my phrasing wasn't very clear. Basically what it would be nice to
> do is specify a list of nodes that are definitely on one side of the cut,
> and a second list of nodes which are definitely on the other side of the
> cut. The cut would then be constrained so that these two sets indeed lie on
> different sides of the cuts. VERY simple examples (a graph with < 10 nodes)
> should be provided to demonstrate (1) and (2).

Actually, now that I thought about it more carefully, what I said before
is the correct way to exactly solve your problem.

Consider a weighted digraph and two non-empty disjoint subsets S, T of
the vertex set.  Then, you can solve for the minimum S-T min-cut by
adding two new vertices u, v, and connect u->s for all s in S, and t->v
for all t in T.  All these new edges receive a weight of positive
infinity, thus can never be saturated in a max-flow solution and never
be cut in a min-cut.  Then, solving for the u-t min-cut will also solve
for the S-T min-cut.

Sebastian