[Lemon-user] Question related to preflow

[Alpár Jüttner]

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
>