{"id":26452,"date":"2017-12-20T21:12:15","date_gmt":"2017-12-20T15:42:15","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26452"},"modified":"2018-10-30T16:32:55","modified_gmt":"2018-10-30T11:02:55","slug":"python-algorithm-find-minimum-s-t-cut-flow-network","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-algorithm-find-minimum-s-t-cut-flow-network\/","title":{"rendered":"Find minimum s-t cut in a flow network"},"content":{"rendered":"

Find minimum s-t cut in a flow network:<\/span><\/h3>\n

In a flow network, an s-t cut<\/strong> is a cut that requires the source \u2018s<\/strong>\u2019 and the sink \u2018t\u2019<\/strong> to be in different subsets, and it consists of edges going from the source\u2019s side to the sink\u2019s side. <\/span>The capacity of an s-t cut is defined by the sum of capacity of each edge in the cut-set. (Source: Wiki<\/a>)
\nThe problem discussed here is to find minimum capacity s-t cut of the given network.<\/strong> Expected output is all edges of the minimum cut.<\/p>\n

For example<\/strong>, in the following flow network, example s-t cuts are {{0 ,1}, {0, 2}}, {{0, 2}, {1, 2}, {1, 3}}, etc. The minimum s-t cut is {{1, 3}, {4, 3}, {4 5}} which has capacity as 12+7+4 = 23.<\/p>\n[ad type=”banner”]\n

Minimum Cut and Maximum Flow<\/strong><\/span><\/h3>\n

Like Maximum Bipartite Matching<\/a>, this is another problem which can solved using Ford-Fulkerson Algorithm<\/a>. This is based on max-flow min-cut theorem.<\/p>\n

The max-flow min-cut theorem<\/a> states that in a flow network, the amount of maximum flow is equal to capacity of the minimum cut. See CLRS book<\/a> for proof of this theorem.<\/p>\n

From Ford-Fulkerson, we get capacity of minimum cut. How to print all edges that form the minimum cut? The idea is to use residual graph.<\/p>\n

Following are steps to print all edges of minimum cut:<\/strong><\/span><\/p>\n

1)<\/strong> Run Ford-Fulkerson algorithm<\/strong> and consider the final residual graph<\/a>.<\/p>\n

2)<\/strong> Find the set of vertices<\/strong> that are reachable from source in the residual graph.<\/p>\n

3)<\/strong> All edges which are from a reachable vertex to non-reachable vertex are minimum cut edges.<\/strong> Print all such edges.<\/p>\n

Following is python<\/a> implementation of the above approach:<\/p>\n

Python Programming:<\/strong><\/span><\/h3>\n
<\/div> 
# Python program for finding min-cut in the given graph# Complexity : (E*(V^3))# Total augmenting path = VE and BFS with adj matrix takes :V^2 times from collections import defaultdict # This class represents a directed graph using adjacency matrix representationclass Graph:     def __init__(self,graph):        self.graph = graph # residual graph        self.org_graph = [i[:] for i in graph]        self. ROW = len(graph)        self.COL = len(graph[0])      '''Returns true if there is a path from source 's' to sink 't' in    residual graph. Also fills parent[] to store the path '''    def BFS(self,s, t, parent):         # Mark all the vertices as not visited        visited =[False]*(self.ROW)         # Create a queue for BFS        queue=[]         # Mark the source node as visited and enqueue it        queue.append(s)        visited[s] = True          # Standard BFS Loop        while queue:             #Dequeue a vertex from queue and print it            u = queue.pop(0)             # Get all adjacent vertices of the dequeued vertex u            # If a adjacent has not been visited, then mark it            # visited and enqueue it            for ind, val in enumerate(self.graph[u]):                if visited[ind] == False and val > 0 :                    queue.append(ind)                    visited[ind] = True                    parent[ind] = u         # If we reached sink in BFS starting from source, then return        # true, else false        return True if visited[t] else False      # Returns tne min-cut of the given graph    def minCut(self, source, sink):         # This array is filled by BFS and to store path        parent = [-1]*(self.ROW)         max_flow = 0 # There is no flow initially         # Augment the flow while there is path from source to sink        while self.BFS(source, sink, parent) :             # Find minimum residual capacity of the edges along the            # path filled by BFS. Or we can say find the maximum flow            # through the path found.            path_flow = float("Inf")            s = sink            while(s !=  source):                path_flow = min (path_flow, self.graph[parent[s]][s])                s = parent[s]             # Add path flow to overall flow            max_flow +=  path_flow             # update residual capacities of the edges and reverse edges            # along the path            v = sink            while(v !=  source):                u = parent[v]                self.graph[u][v] -= path_flow                self.graph[v][u] += path_flow                v = parent[v]         # print the edges which initially had weights        # but now have 0 weight        for i in range(self.ROW):            for j in range(self.COL):                if self.graph[i][j] == 0 and self.org_graph[i][j] > 0:                    print str(i) + " - " + str(j)  # Create a graph given in the above diagramgraph = [[0, 16, 13, 0, 0, 0],        [0, 0, 10, 12, 0, 0],        [0, 4, 0, 0, 14, 0],        [0, 0, 9, 0, 0, 20],        [0, 0, 0, 7, 0, 4],        [0, 0, 0, 0, 0, 0]] g = Graph(graph) source = 0; sink = 5 g.minCut(source, sink) # This code is contributed by Neelam Yadav<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
Output:<\/strong><\/span><\/h3>\n
1 - 3\r\n4 - 3\r\n4 - 5<\/pre>\n","protected":false},"excerpt":{"rendered":"
Python Algorithm – Find minimum s-t cut in a flow network –  Graph Algorithm – In a flow network, an s-t cut is a cut that requires the source \u2018s\u2019 <\/p>\n","protected":false},"author":1,"featured_media":31259,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73906,78429],"tags":[78844,78840,78852,78843,78837,78845,78841,78849,78850,78842,78838,78839,78848,78851],"class_list":["post-26452","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-graph-algorithms","category-maximum-flow","tag-explain-max-flow-min-cut-theorem-with-example","tag-ford-fulkerson-algorithm-for-maximum-flow-problem","tag-global-min-cut","tag-how-to-find-min-cut-of-a-graph","tag-max-flow-min-cut-algorithm","tag-max-flow-min-cut-geeksforgeeks","tag-max-flow-min-cut-theorem-in-graph-theory","tag-max-flow-min-cut-theorem-proof","tag-maximum-flow-example","tag-min-cut-algorithm-example","tag-minimum-cut-algorithm","tag-randomized-min-cut-algorithm","tag-s-t-cut","tag-stoer-wagner-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26452","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26452"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26452\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31259"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26452"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26452"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26452"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}