{"id":26420,"date":"2017-10-26T22:07:38","date_gmt":"2017-10-26T16:37:38","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26420"},"modified":"2017-10-26T22:07:38","modified_gmt":"2017-10-26T16:37:38","slug":"python-algorithm-find-maximum-number-edge-disjoint-paths-two-vertices","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-algorithm-find-maximum-number-edge-disjoint-paths-two-vertices\/","title":{"rendered":"Python Algorithm – Find maximum number of edge disjoint paths between two vertices"},"content":{"rendered":"

Given a directed graph and two vertices in it, source \u2018s\u2019 and destination \u2018t\u2019, find out the maximum number of edge disjoint paths from s to t.<\/span> Two paths are said edge disjoint if they don\u2019t share any edge.<\/p>\n

 <\/p>\n

There can be maximum two edge disjoint paths from source 0 to destination 7 in the above graph. Two edge disjoint paths are highlighted below in red and blue colors are 0-2-6-7 and 0-3-6-5-7.<\/p>\n

 <\/p>\n

Note that the paths may be different, but the maximum number is same. For example, in the above diagram, another possible set of paths is 0-1-2-6-7 and 0-3-6-5-7 respectively.<\/p>\n

This problem can be solved by reducing it to maximum flow problem<\/a>. Following are steps.
\n1)<\/strong> Consider the given source and destination as source and sink in flow network. Assign unit capacity to each edge.
\n2)<\/strong> Run Ford-Fulkerson algorithm to find the maximum flow from source to sink.
\n3)<\/strong> The maximum flow is equal to the maximum number of edge-disjoint paths.<\/p>\n

When we run Ford-Fulkerson, we reduce the capacity by a unit. Therefore, the edge can not be used again. So the maximum flow is equal to the maximum number of edge-disjoint paths.<\/p>\n[ad type=”banner”]\n

Following is C++ implementation of the above algorithm. Most of the code is taken from here<\/a>.<\/p>\n

Python Programming:<\/strong><\/p>\n

<\/div> 
# Python program to find maximum number of edge disjoint paths# 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. ROW = len(graph)               '''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 maximum number of edge-disjoint paths from     #s to t in the given graph    def findDisjointPaths(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]         return max_flow   # Create a graph given in the above diagram graph = [[0, 1, 1, 1, 0, 0, 0, 0],        [0, 0, 1, 0, 0, 0, 0, 0],        [0, 0, 0, 1, 0, 0, 1, 0],        [0, 0, 0, 0, 0, 0, 1, 0],        [0, 0, 1, 0, 0, 0, 0, 1],        [0, 1, 0, 0, 0, 0, 0, 1],        [0, 0, 0, 0, 0, 1, 0, 1],        [0, 0, 0, 0, 0, 0, 0, 0]]   g = Graph(graph) source = 0; sink = 7  print ("There can be maximum %d edge-disjoint paths from %d to %d" %            (g.findDisjointPaths(source, sink), source, sink))  #This code is contributed by Neelam Yadav<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
There can be maximum 2 edge-disjoint paths from 0 to 7<\/pre>\n
Time Complexity: <\/strong>Same as time complexity of Edmonds-Karp implementation of Ford-Fulkerson<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Python Algorithm – Find maximum number of edge disjoint paths between two vertices – Graph Algorithm – Given a directed graph and two vertices in it, source<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,73906,78429,4148],"tags":[78743,78742,78746,78741,78738,78745,78747,78736,78740,78739,78748],"class_list":["post-26420","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-graph-algorithms","category-maximum-flow","category-python","tag-disjoint-paths-in-a-network","tag-edge-disjoint-definition","tag-edge-disjoint-path-definition","tag-edge-disjoint-paths-example","tag-edge-disjoint-paths-undirected-graph","tag-edge-disjoint-subgraph","tag-node-disjoint-path","tag-vertex-disjoint-path","tag-vertex-disjoint-path-problem","tag-vertex-disjoint-paths-max-flow","tag-what-is-edge-disjoint-path"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26420","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=26420"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26420\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26420"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26420"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26420"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}