[Boost-bugs] [Boost C++ Libraries] #3478: Min cut interface for BGL

Subject: [Boost-bugs] [Boost C++ Libraries] #3478: Min cut interface for BGL
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2009-09-22 14:00:57

#3478: Min cut interface for BGL
------------------------------------------------+---------------------------
 Reporter:  David Doria <daviddoria@…>          |       Owner:  asutton       
     Type:  Feature Requests                    |      Status:  new           
Milestone:  Boost 1.41.0                        |   Component:  graph         
  Version:  Boost 1.40.0                        |    Severity:  Not Applicable
 Keywords:                                      |  
------------------------------------------------+---------------------------
 1) The max flow can be obtained with: (any of the max_flow algorithms,
 kolmogorov is just used as an example)

 double flow = kolmogorov_max_flow(g, SourceNode, SinkNode);

 It would be nice to also interpret this max flow as a min cut. I.e. be
 able to tell which nodes of g belong to the "source side" of the graph and
 which nodes belong to the "sink side"? Maybe something like a
 std::vector<unsigned int> GetSourceSideNodes(); //return the IDs of the
 nodes on the source side
 std::vector<unsigned int> GetSinkSideNodes();//return the IDs of the nodes
 on the sink side
 std::vector<unsigned int> GetCutEdges(); // return the IDs of the edges
 which were cut

 2) Allow the min cut algorithm to accept multiple sources/sinks. The cut
 should simply be the minimum sum of edges that can be severed to split the
 graph so that all of the sinks are on one side of the cut and all of the
 sources are on the other side of the cut.

 3) Find the minimum cut that partitions the graph into two parts without
 specifying a source/sink? I.e. the minimum of all of the possible
 source/sink pairs minium cuts.

 4) Currently you must use a bidirectional graph, and specify an
 edge_reverse_t in the graph traits, then set the reverse edge for every
 edge. a) this is pretty complicated for someone who is unfamiliar with
 generic programming. b) If an undirected graph is used, the algorithm
 should automatically take care of adding these reverse edges if they are
 required for the cut to be performed.

 5) VERY simple examples (actually constructing a graph (not reading it
 from file) with < 10 nodes) should be provided to demonstrate all of these
 cases.

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