[Lemon-user] Trouble with Preflow

[Allen Brookes]

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(nIt1) << " label: " << lab[nIt1] <<
std::endl;

for (lemon::SmartDigraph::NodeIt nIt2(g); nIt2 != lemon::INVALID; ++nIt2)

{

if (nIt1 != nIt2 && g.id(nIt1)) {

std::cout << " processing node: " << g.id(nIt1) << " label: " << lab[nIt1]
<< " inner node:" << 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100623/8dca032e/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: y2yedgesdiraltsub.lgf
Type: application/octet-stream
Size: 6848 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100623/8dca032e/attachment.obj>