[Boost-bugs] [Boost C++ Libraries] #3152: Obtaining a minimum s-t cut edge set

Subject: [Boost-bugs] [Boost C++ Libraries] #3152: Obtaining a minimum s-t cut edge set
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2009-06-09 07:17:55

#3152: Obtaining a minimum s-t cut edge set
-------------------------------+--------------------------------------------
 Reporter:  nowozin_at_[hidden]  |       Owner:  dgregor
     Type:  Feature Requests   |      Status:  new    
Milestone:  Boost 1.40.0       |   Component:  graph  
  Version:  Boost 1.39.0       |    Severity:  Problem
 Keywords:                     |  
-------------------------------+--------------------------------------------
 The boost graph library offers a set of algorithms to solve linear max-
 flow problems, among them push-relabel and kolmogorov max-flow algorithms.

 Often, the application of the max-flow algorithm is in order to solve for
 a minimum edge cut set separating nodes s and t.  Right now, obtaining a
 minimum edge cut set is not supported in the boost graph library.  Thus
 one of the main applications of solving max flow problems is not catered
 for by boost graph.

 Limited support for this functionality is available in the
 kolmogorov_max_flow algorithm by means of a color map mapping vertices to
 black, white and gray states.  However, this is specific to the kolmogorov
 max flow algorithm whereas the general feature to obtain the minimum cut
 set is so important such that it should be an own feature supported by all
 max flow algorithms in the library.

 Additionally, the documentation or code of the colormap in the kolmogorov
 max flow algorithm is wrong; there are connected but undecided states
 (gray) and applying the white-nonwhite or black-nonblack separation
 suggested in the documentation does not always yield a minimum cut set.

 Thanks for considering.

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