https://svn.boost.org/trac10/ticket/13489 <p> Greetings, </p> <p> With some graphs, the boykov_kolmogorov_max_flow algorithm creates residual edge capacity maps with larger values than the graph edge capacities should allow. </p> <p> I have attached code that creates a small graph to demonstrate this issue and the <a class="missing wiki">GraphViz</a> plot of the automatically-generated .dot graph file for easy visual inspection of the results. </p> <p> In the attached <a class="missing wiki">GraphViz</a> plot, each edge is labeled with (residual capacity)/(capacity). The residual capacity should never be greater than the capacity. Thus, the labels "1/0" and "101/100" are in error. </p> <p> I have run this test in Boost 1.54, 1.66, and 1.67. </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/13489 Trac 1.4.3 Nathaniel Bird <nate@…> Thu, 22 Mar 2018 16:28:05 GMT https://svn.boost.org/trac10/ticket/13489 https://svn.boost.org/trac10/ticket/13489 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">main.cpp</span> </li> </ul> <p> cpp file that demonstrates problem </p> Ticket Nathaniel Bird <nate@…> Thu, 22 Mar 2018 16:28:24 GMT https://svn.boost.org/trac10/ticket/13489 https://svn.boost.org/trac10/ticket/13489 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">CMakeLists.txt</span> </li> </ul> <p> CMake file </p> Ticket Nathaniel Bird <nate@…> Thu, 22 Mar 2018 16:29:00 GMT https://svn.boost.org/trac10/ticket/13489 https://svn.boost.org/trac10/ticket/13489 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">b-k_example_graph.dot</span> </li> </ul> <p> Generated output .dot file. </p> Ticket Nathaniel Bird <nate@…> Thu, 22 Mar 2018 16:29:27 GMT https://svn.boost.org/trac10/ticket/13489 https://svn.boost.org/trac10/ticket/13489 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">graph1.ps</span> </li> </ul> <p> <a class="missing wiki">GraphViz</a> visualization of the .dot file. </p> Ticket