https://svn.boost.org/trac10/ticket/7728 <p> The BK flow algorithm is supposed to return a maximum flow, but sometimes pushes less flow than other flow algorithms (i.e., push_relabel_max_flow). This seems to happen more often with large graphs. </p> <p> An example input is provided: running the test program with the graph in err.dat gives a BK flow of 100 but a Push-Relabel flow of 102. If you also examine the datastructures at the end of the BK flow, there are edges with positive residual capacity from nodes in the source/sink search trees to gray nodes, which should not happen. </p> <p> The problem seems to be in the adopt subroutine. When a node becomes an orphan, all its neighbors need to become active. The patchfile provided fixes some conditionals to make sure that the correct nodes become active. With the changes, the BK flow algorithm gives the correct answer on the graph provided. </p> <p> Note: this may be the same as bug <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/3468" title="#3468: Bugs: kolmogorov_max_flow doesn't always find the maximum flow (closed: fixed)">#3468</a>, but it's been open for 3 years, and it's unclear if it's the same issue. I did borrow my example file from that bug-report, as it was much smaller than the (rather large) graph that I initially found the problem for. </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/7728 Trac 1.4.3 Alex Fix <afix@…> Thu, 22 Nov 2012 20:57:30 GMT https://svn.boost.org/trac10/ticket/7728 https://svn.boost.org/trac10/ticket/7728 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">test-flow.cxx</span> </li> </ul> Ticket Alex Fix <afix@…> Thu, 22 Nov 2012 20:57:46 GMT https://svn.boost.org/trac10/ticket/7728 https://svn.boost.org/trac10/ticket/7728 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">err.dat</span> </li> </ul> Ticket Alex Fix <afix@…> Thu, 22 Nov 2012 20:58:02 GMT https://svn.boost.org/trac10/ticket/7728 https://svn.boost.org/trac10/ticket/7728 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">patchfile.patch</span> </li> </ul> Ticket Jeremiah Willcock Sun, 25 Nov 2012 20:13:27 GMT https://svn.boost.org/trac10/ticket/7728#comment:1 https://svn.boost.org/trac10/ticket/7728#comment:1 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> </ul> <p> (In <a class="changeset" href="https://svn.boost.org/trac10/changeset/81536" title="Applied patch from #7728 to fix B-K max-flow bug; fixes #7728; fixes #3468">[81536]</a>) Applied patch from <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/7728" title="#7728: Bugs: boykov_kolmogorov_max_flow does not always compute a max flow (closed: fixed)">#7728</a> to fix B-K max-flow bug; fixes <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/7728" title="#7728: Bugs: boykov_kolmogorov_max_flow does not always compute a max flow (closed: fixed)">#7728</a>; fixes <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/3468" title="#3468: Bugs: kolmogorov_max_flow doesn't always find the maximum flow (closed: fixed)">#3468</a> </p> Ticket