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

Posted 5 months ago
492 Views
|
2 Replies
|
1 Total Likes
|
 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?
2 Replies
Sort By:
Posted 5 months ago
 I have implemented the s-t min-cut in a directed graph(using the explanation from this site). The code is belowGraph 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)
 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.