Subject: Re: [boost] Graph cut questions
From: Sebastian Nowozin (nowozin_at_[hidden])
Date: 2009-09-17 04:22:36
David Doria wrote:
>>> 2) Is it possible to tell the max flow algorithm to use multiple
>> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk