Re: [boost] Graph cut questions

Subject: Re: [boost] Graph cut questions
From: David Doria (daviddoria+boost_at_[hidden])
Date: 2009-09-16 13:53:30

On Wed, Sep 16, 2009 at 1:25 PM, Sebastian Nowozin <nowozin_at_[hidden]>wrote:

>
> 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
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>

Sebastian,

Thanks for your response! Here are some follow up comments (using the same
numbering scheme):

1) I agree, an s-t min cut interface *really* should be defined.

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

3) I agree, this is indeed a different problem - but it would be nice to see
it added :)

4) The overhead may be small (especially if you could just copy and paste
from a simple example), but again, it is very confusing for people not
familiar with the generic programming concepts of boost.

Can these things be submitted as a formal feature request somewhere? Or is
the mailing list the only option? Is there any hope of them being added
relatively quickly (it seems like whoever wrote the max flow should be able
to provide a min cut interface VERY quickly)? Or should I continue my search
for a graph library elsewhere?

Thanks,

David