Re: [boost] Graph cut questions

Subject: Re: [boost] Graph cut questions
From: Sebastian Nowozin (nowozin_at_[hidden])
Date: 2009-09-16 13:25:23

Hi David,

David Doria wrote:

> 1) If I do this: (with any of the max_flow algorithms, kolmogorov is just
> used as an example)
> 
> double flow = kolmogorov_max_flow(g, SourceNode, SinkNode);
> 
> I get the value of the max flow, but how do I tell which nodes of g belong
> to the "source side" of the graph and which nodes belong to the "sink side"?
> (thinking of it as a min cut rather than a max flow problem)

This is not as trivial as it sounds and a common problem I myself raised
at least two times on this mailing list.  The short answer is: in the
current state of the boost graph library there is no easy correct way to
obtain a minimum cut from the max-flow solution, which is a pitty.

  The kolmogorov_max_flow supports a colormap with colors
"black","white","gray" which should support this.  A min-cut can be
constructed, according to the documentation by all the edges from
"white" to "gray"+"black", another one by all edges from "white"+"gray"
to "black".  This would be an easy method and "seems to work" for some
graphs, but there are cases where the graph constructed either way is
not a valid min-cut, i.e. the sum of edge weights in the cut is above
the max-flow solution.  The other max-flow codes do not support this
feature at all and kolmogorov_max_flow is not maintained anymore, so
there is no working bug-free solution.  The demo-code originally
supplied with kolmogorov_max_flow (for image segmentation) does not care
and simply uses such cut constructed, even if its not maximal.

  It would be really nice if a s-t min cut interface would be defined,
as this must be one of the very common practical problems one would want
to use a graph library for.

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

> 3) The max_flow functions seem to require a source and sink to be specified.
> Shouldn't you be able to find the minimum cut that partitions the graph into
> two parts even without specifying a source/sink?

This is a different problem.  The "min-cut" is not the minimum cut among
all possible pairs but actually only an "s-t min-cut".  Afaik there is
no code in boost to obtain the min-cut among all pairs.

> 4) Currently you must use a bidirectional graph, and specify an
> edge_reverse_t in the graph traits, then set the reverse edge for every
> edge. a) this is pretty complicated for someone who is unfamiliar with
> generic programming. b) If an undirected graph is used, the algorithm should
> automatically take care of adding these reverse edges if they are required
> for the cut to be performed.

Further optimization for undirected graphs would be possible, yes.
However, the current overhead is pretty small.

Kind regards,
Sebastian