[Lemon-user] Question related to preflow

[Jacint Szabo]

 Hi All,

Preflow also finds the minimum mincut, and this is available after the
first phase. So you can reverse the arcs, run the first phase of preflow
from t, and take the complement of the minimum mincut.

Best regards, Jacint

On Thu, May 17, 2012 at 8:53 AM, Alpár Jüttner <alpar at cs.elte.hu> wrote:

> Hi,
>
> > > I want to compute the (unique) inclusion-wise maximal minimum s-t cut
> > > in a network.
>
> I'm pretty sure that Preflow finds exactly this cut. You don't even need
> to run the full preflow, the first phase is enough (e.g. use
> pre.runMinCut();, which is just a shortcut to
> pre.init();pre.startFirstPhase();)
>
> In the first phase preflow performs "push" operations only, therefore it
> forwards the flow as far from the source as possible. (The second phase
> created a proper flow from the obtained preflow by "pulling back" the
> excess that cannot be moved through the the min cut.)
>
> It would be nice if someone confirmed that I'm right. Then we can add
> this info to the doc of Preflow::runMinCut().
>
> Regards,
> Alpar
>
> > >
> > > I found the following solution:
> > >
> > > //Find a maximum flow:
> > >   lemon::Preflow< Graph, typename Graph::template ArcMap<double> >
> > > pre(auxG,auxCap,src,trg);
> > >   pre.run();
> > > //Take the residual graph
> > >   typedef lemon::ResidualDigraph<const  Graph, const typename
> > > Graph::template ArcMap<double>  >  ResDigraph;
> > >   ResDigraph res(auxG,auxCap,pre.flowMap());
> > >  //Reverse its edges
> > >   lemon::ReverseDigraph< ResDigraph > revRes(res);
> > > //Take a Bfs in it
> > >   lemon::Bfs< lemon::ReverseDigraph< ResDigraph > > befes(revRes);
> > >   befes.run(trg);
> > >
> > > The non-reached nodes are the ones I need.
> > >
> > > Is there a simpler solution for this problem?
> > >
> > > Thanks in advance.
> > >
> > > Attila
> > _______________________________________________
> > Lemon-user mailing list
> > Lemon-user at lemon.cs.elte.hu
> > http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
> >
>
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20120519/299dc69b/attachment.html>