[Lemon-user] Question related to preflow

[Alpár Jüttner]

Hi,

Just to confirm what Jacint said: I was wrong. Preflow indeed finds the
minimum cut with the _smallest_ number of nodes belonging to the
component of the source node.

Regards,
Alpar

On Sat, 2012-05-19 at 11:11 +0200, Jacint Szabo wrote:
> 
>  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
>         
>