{"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

\u00a0<\/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

\u00a0<\/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=\u201dbanner\u201d]\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[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20find%20maximum%20number%20of%20edge%20disjoint%20paths%0A%23%20Complexity%20%3A%20(E*(V%5E3))%0A%23%20Total%20augmenting%20path%20%3D%20VE%20%0A%23%20and%20BFS%20with%20adj%20matrix%20takes%20%3AV%5E2%20times%0A%20%20%0Afrom%20collections%20import%20defaultdict%0A%20%20%0A%23This%20class%20represents%20a%20directed%20graph%20using%20%0A%23%20adjacency%20matrix%20representation%0Aclass%20Graph%3A%0A%20%20%0A%20%20%20%20def%20__init__(self%2Cgraph)%3A%0A%20%20%20%20%20%20%20%20self.graph%20%3D%20graph%20%23%20residual%20graph%0A%20%20%20%20%20%20%20%20self.%20ROW%20%3D%20len(graph)%0A%20%20%20%20%20%20%20%20%20%0A%20%20%0A%20%20%20%20\u201d\u2019Returns%20true%20if%20there%20is%20a%20path%20from%20source%20\u2019s\u2019%20to%20sink%20\u2019t\u2019%20in%0A%20%20%20%20residual%20graph.%20Also%20fills%20parent%5B%5D%20to%20store%20the%20path%20\u201d\u2019%0A%20%20%20%20def%20BFS(self%2Cs%2C%20t%2C%20parent)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%20Mark%20all%20the%20vertices%20as%20not%20visited%0A%20%20%20%20%20%20%20%20visited%20%3D%5BFalse%5D*(self.ROW)%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Create%20a%20queue%20for%20BFS%0A%20%20%20%20%20%20%20%20queue%3D%5B%5D%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Mark%20the%20source%20node%20as%20visited%20and%20enqueue%20it%0A%20%20%20%20%20%20%20%20queue.append(s)%0A%20%20%20%20%20%20%20%20visited%5Bs%5D%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Standard%20BFS%20Loop%0A%20%20%20%20%20%20%20%20while%20queue%3A%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23Dequeue%20a%20vertex%20from%20queue%20and%20print%20it%0A%20%20%20%20%20%20%20%20%20%20%20%20u%20%3D%20queue.pop(0)%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Get%20all%20adjacent%20vertices%20of%20the%20dequeued%20vertex%20u%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20a%20adjacent%20has%20not%20been%20visited%2C%20then%20mark%20it%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20visited%20and%20enqueue%20it%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20ind%2C%20val%20in%20enumerate(self.graph%5Bu%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20visited%5Bind%5D%20%3D%3D%20False%20and%20val%20%3E%200%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20queue.append(ind)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20visited%5Bind%5D%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bind%5D%20%3D%20u%0A%20%0A%20%20%20%20%20%20%20%20%23%20If%20we%20reached%20sink%20in%20BFS%20starting%20from%20source%2C%20then%20return%0A%20%20%20%20%20%20%20%20%23%20true%2C%20else%20false%0A%20%20%20%20%20%20%20%20return%20True%20if%20visited%5Bt%5D%20else%20False%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%0A%20%20%20%20%23%20Returns%20tne%20maximum%20number%20of%20edge-disjoint%20paths%20from%20%0A%20%20%20%20%23s%20to%20t%20in%20the%20given%20graph%0A%20%20%20%20def%20findDisjointPaths(self%2C%20source%2C%20sink)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%20This%20array%20is%20filled%20by%20BFS%20and%20to%20store%20path%0A%20%20%20%20%20%20%20%20parent%20%3D%20%5B-1%5D*(self.ROW)%0A%20%0A%20%20%20%20%20%20%20%20max_flow%20%3D%200%20%23%20There%20is%20no%20flow%20initially%0A%20%0A%20%20%20%20%20%20%20%20%23%20Augment%20the%20flow%20while%20there%20is%20path%20from%20source%20to%20sink%0A%20%20%20%20%20%20%20%20while%20self.BFS(source%2C%20sink%2C%20parent)%20%3A%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Find%20minimum%20residual%20capacity%20of%20the%20edges%20along%20the%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20path%20filled%20by%20BFS.%20Or%20we%20can%20say%20find%20the%20maximum%20flow%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20through%20the%20path%20found.%0A%20%20%20%20%20%20%20%20%20%20%20%20path_flow%20%3D%20float(%22Inf%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20s%20%3D%20sink%0A%20%20%20%20%20%20%20%20%20%20%20%20while(s%20!%3D%20%20source)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20path_flow%20%3D%20min%20(path_flow%2C%20self.graph%5Bparent%5Bs%5D%5D%5Bs%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20s%20%3D%20parent%5Bs%5D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Add%20path%20flow%20to%20overall%20flow%0A%20%20%20%20%20%20%20%20%20%20%20%20max_flow%20%2B%3D%20%20path_flow%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20update%20residual%20capacities%20of%20the%20edges%20and%20reverse%20edges%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20along%20the%20path%0A%20%20%20%20%20%20%20%20%20%20%20%20v%20%3D%20sink%0A%20%20%20%20%20%20%20%20%20%20%20%20while(v%20!%3D%20%20source)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20u%20%3D%20parent%5Bv%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.graph%5Bu%5D%5Bv%5D%20-%3D%20path_flow%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.graph%5Bv%5D%5Bu%5D%20%2B%3D%20path_flow%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20v%20%3D%20parent%5Bv%5D%0A%20%0A%20%20%20%20%20%20%20%20return%20max_flow%0A%20%0A%20%20%0A%23%20Create%20a%20graph%20given%20in%20the%20above%20diagram%0A%20%0Agraph%20%3D%20%5B%5B0%2C%201%2C%201%2C%201%2C%200%2C%200%2C%200%2C%200%5D%2C%0A%20%20%20%20%20%20%20%20%5B0%2C%200%2C%201%2C%200%2C%200%2C%200%2C%200%2C%200%5D%2C%0A%20%20%20%20%20%20%20%20%5B0%2C%200%2C%200%2C%201%2C%200%2C%200%2C%201%2C%200%5D%2C%0A%20%20%20%20%20%20%20%20%5B0%2C%200%2C%200%2C%200%2C%200%2C%200%2C%201%2C%200%5D%2C%0A%20%20%20%20%20%20%20%20%5B0%2C%200%2C%201%2C%200%2C%200%2C%200%2C%200%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%5B0%2C%201%2C%200%2C%200%2C%200%2C%200%2C%200%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%5B0%2C%200%2C%200%2C%200%2C%200%2C%201%2C%200%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%5B0%2C%200%2C%200%2C%200%2C%200%2C%200%2C%200%2C%200%5D%5D%0A%20%20%0A%20%0Ag%20%3D%20Graph(graph)%0A%20%0Asource%20%3D%200%3B%20sink%20%3D%207%0A%20%20%0Aprint%20(%22There%20can%20be%20maximum%20%25d%20edge-disjoint%20paths%20from%20%25d%20to%20%25d%22%20%25%0A%20%20%20%20%20%20%20%20%20%20%20%20(g.findDisjointPaths(source%2C%20sink)%2C%20source%2C%20sink))%0A%20%0A%20%0A%23This%20code%20is%20contributed%20by%20Neelam%20Yadav%0A\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\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=\u201dbanner\u201d]\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}]}}