[Boost-bugs] [Boost C++ Libraries] #13489: boykov_kolmogorov_max_flow produces incorrect residual edge capacity

Subject: [Boost-bugs] [Boost C++ Libraries] #13489: boykov_kolmogorov_max_flow produces incorrect residual edge capacity
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2018-03-22 16:26:50

#13489: boykov_kolmogorov_max_flow produces incorrect residual edge capacity
--------------------------------+-------------------------------
 Reporter:  Nate Bird <nate@…>  |      Owner:  Jeremiah Willcock
     Type:  Bugs                |     Status:  new
Milestone:  To Be Determined    |  Component:  graph
  Version:  Boost 1.67.0        |   Severity:  Problem
 Keywords:                      |
--------------------------------+-------------------------------
 Greetings,

 With some graphs, the boykov_kolmogorov_max_flow algorithm creates
 residual edge capacity maps with larger values than the graph edge
 capacities should allow.

 I have attached code that creates a small graph to demonstrate this issue
 and the GraphViz plot of the automatically-generated .dot graph file for
 easy visual inspection of the results.

 In the attached GraphViz 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.

 I have run this test in Boost 1.54, 1.66, and 1.67.

-- 
Ticket URL: <https://svn.boost.org/trac10/ticket/13489>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.