Message Boards Message Boards

Find a minimum source-destination min cut in a graph?

GROUPS:

I want to find a minimum s-t cut in a graph. According to the max-flow-min-cut theorem, from a maximum flow, I can find min cut. I didn't find built-in function to calculate the min-cut, only built-in function to calculate a max flow. Using the 'FindMaximumFlow' property 'ResidualGraph' and BFS, it is possible to find edges in min cut, but I have some issue with this property. Any suggestion how to calculate s-t min-cut?

POSTED BY: Kiril Dan
Answer
2 months ago

I have implemented the s-t min-cut in a directed graph(using the explanation from this site). The code is below

Graph creation:

 checkGrap = 
   Graph[{1 \[DirectedEdge] 2, 1 \[DirectedEdge] 3, 
   3 \[DirectedEdge] 1, 2 \[DirectedEdge] 3, 4 \[DirectedEdge] 2, 
   3 \[DirectedEdge] 4, 5 \[DirectedEdge] 1, 5 \[DirectedEdge] 3, 
   2 \[DirectedEdge] 6, 4 \[DirectedEdge] 6}, VertexLabels -> "Name"];
   weighsToEdgesVT = {12, 10, 4, 9, 7, 14, 16, 13, 20, 4};

  testGrapWe = 
  Graph[VertexList[checkGrap], EdgeList[checkGrap], 
   EdgeWeight -> weighsToEdgesVT, VertexLabels -> "Name"]

Residual graph calculation:

flowData = FindMaximumFlow[checkGrap, 5, 6, "OptimumFlowData", EdgeCapacity -> weithsToEdgesVT];
flowMAtrix = flowData["FlowMatrix"];
originalMatrix = WeightedAdjacencyMatrix[testGrapWe];
residualMatrix = (N[originalMatrix - flowMAtrix]);
mc = SparseArray[ ArrayRules[residualMatrix] /. {0. -> Infinity}, 
Dimensions[residualMatrix]];

Nodes reachable from source:

residualGraph = WeightedAdjacencyGraph[mc, VertexLabels -> "Name"];
nodes = Reap[BreadthFirstScan[residualGraph,5, {"DiscoverVertex" - 
(Sow[#1] &)}]][[2, 1]]

The cut

 cut = EdgeList[checkGrap, 
  DirectedEdge[Alternatives @@ nodes, 
   Alternatives @@ 
    Complement[VertexOutComponent[checkGrap, nodes], nodes]]]

Any suggestion how to speed up the code ( I want to run it on a graph with ~30000 nodes and ~100000 edges)

POSTED BY: Kiril Dan
Answer
2 months ago

FindEdgeCut should be doing this, but it returns an incorrect result for your graph (it seems to ignore weights with the s-t syntax). Yet another broken Graph function.

POSTED BY: Szabolcs Horvát
Answer
2 months ago

Group Abstract Group Abstract