Boost logo

Boost :

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,

Boost list run by bdawes at, gregod at, cpdaniel at, john at