[Lemon-user] Trouble with Preflow

[Kovács Péter]

Hi Allen,

Unfortunately, it seems to be a real and critical bug. For some node 
pairs, Preflow gets in an infinite loop. The default Elevator 
implementation (which is used in Preflow) seems to be faulty, it 
sometimes does not deactive a node even if deactive() was called.

Until the bug is fixed, I suggest to use LinkedElevator instead of 
Elevator for Preflow. They are different implementations of a data 
structure which is required by the algorithm. LinkedElevator could be 
slightly slower, but it works properly for your input.

Use the following lines in your code for creating the pf object.

   lemon::Preflow<lemon::SmartDigraph,
       lemon::SmartDigraph::ArcMap<__int64> >
     ::SetStandardElevator<lemon::LinkedElevator<lemon::SmartDigraph,
       lemon::SmartDigraph::Node> >
     ::Create pf(g, cap, nIt1, nIt2);

I created a bug report ticket about the problem:
http://lemon.cs.elte.hu/trac/lemon/ticket/372

Best regards,
Peter


2010.06.23. 17:03 keltezéssel, Allen Brookes írta:
> Hi,
> I'm having trouble using the Preflow class with some inputs. The
> following code demonstrates the problem with the attached .lgf file.
>
> int
>
> TestMaxFlow(const char* digraphFile)
>
> {
>
> lemon::SmartDigraph g;
>
> lemon::SmartDigraph::ArcMap<
>
> __int64> cap(g);
>
> lemon::SmartDigraph::NodeMap<
>
> int> lab(g);
>
> lemon::SmartDigraph::Node s, t;
>
> try {
>
> digraphReader(g, digraphFile).
>
> arcMap(
>
> "capacity", cap).
>
> nodeMap(
>
> "label", lab).
>
> run();
>
> }
>
> catch (lemon::Exception& error) {
>
> std::cerr <<
>
> "Error: " << error.what() << std::endl;
>
> return -1;
>
> }
>
> for (lemon::SmartDigraph::NodeIt nIt1(g); nIt1 != lemon::INVALID; ++nIt1)
>
> {
>
> std::cout <<
>
> "Processing node: " << g.id <http://g.id>(nIt1) << " label: " <<
> lab[nIt1] << std::endl;
>
> for (lemon::SmartDigraph::NodeIt nIt2(g); nIt2 != lemon::INVALID; ++nIt2)
>
> {
>
> if (nIt1 != nIt2 && g.id <http://g.id>(nIt1)) {
>
> std::cout <<
>
> " processing node: " << g.id <http://g.id>(nIt1) << " label: " <<
> lab[nIt1] << " inner node:" << g.id <http://g.id>(nIt2) << " label: " <<
> lab[nIt2] << std::endl;
>
> lemon::Preflow<lemon::SmartDigraph, lemon::SmartDigraph::ArcMap<
>
> __int64> > pf(g, cap, nIt1, nIt2);
>
> pf.run();
>
> }
>
> }
>
> }
>
> return 0;
>
> }
>
> For certain source/target pairs, the code hangs or crashes. I found
> early on that it would crash if source and target were the same node, so
> I exclude this case. Are there other cases I need to exclude? Also, the
> results seem to depend on the capacity values of the arcs. For some
> values, the same set of nodes will run fine.
>
> Allen
>