Min cut interface for BGL

[David Doria <daviddoria@…>]

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.

[Andrew Sutton]

I think that this is similar related to #3152, but expressed a little more explicitly. Addressing these issues will probably result in a new mincut/maxflow algorithm suite.