[Boost-bugs] [Boost C++ Libraries] #7728: boykov_kolmogorov_max_flow does not always compute a max flow

Subject: [Boost-bugs] [Boost C++ Libraries] #7728: boykov_kolmogorov_max_flow does not always compute a max flow
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2012-11-22 20:57:00

#7728: boykov_kolmogorov_max_flow does not always compute a max flow
--------------------------------------------+-------------------------------
 Reporter:  Alex Fix <afix@…>               |       Owner:  jewillco
     Type:  Bugs                            |      Status:  new     
Milestone:  To Be Determined                |   Component:  graph   
  Version:  Boost Development Trunk         |    Severity:  Problem 
 Keywords:                                  |  
--------------------------------------------+-------------------------------
 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.

 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.

 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.

 Note: this may be the same as bug #3468, 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.

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