{"id":26415,"date":"2017-10-26T22:08:36","date_gmt":"2017-10-26T16:38:36","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26415"},"modified":"2017-10-26T22:08:36","modified_gmt":"2017-10-26T16:38:36","slug":"c-algorithm-find-maximum-number-edge-disjoint-paths-two-vertices-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-algorithm-find-maximum-number-edge-disjoint-paths-two-vertices-2\/","title":{"rendered":"Cpp Algorithm &#8211; Find maximum number of edge disjoint paths between two vertices"},"content":{"rendered":"<p>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 id=\"more-123305\"><\/span> Two paths are said edge disjoint if they don\u2019t share any edge.<\/p>\n<p>\u00a0<\/p>\n<p>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>\u00a0<\/p>\n<p>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<p>This problem can be solved by reducing it to <a href=\"http:\/\/www.geeksforgeeks.org\/ford-fulkerson-algorithm-for-maximum-flow-problem\/\" target=\"_blank\" rel=\"noopener noreferrer\">maximum flow problem<\/a>. Following are steps.<br \/>\n<strong>1)<\/strong> Consider the given source and destination as source and sink in flow network. Assign unit capacity to each edge.<br \/>\n<strong>2)<\/strong> Run Ford-Fulkerson algorithm to find the maximum flow from source to sink.<br \/>\n<strong>3)<\/strong> The maximum flow is equal to the maximum number of edge-disjoint paths.<\/p>\n<p>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<p>Following is C++ implementation of the above algorithm. Most of the code is taken from <a href=\"http:\/\/www.geeksforgeeks.org\/ford-fulkerson-algorithm-for-maximum-flow-problem\/\" target=\"_blank\" rel=\"noopener noreferrer\">here<\/a>.<\/p>\n<p><strong>C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20find%20maximum%20number%20of%20edge%20disjoint%20paths%0A%23include%20%3Ciostream%3E%0A%23include%20%3Climits.h%3E%0A%23include%20%3Cstring.h%3E%0A%23include%20%3Cqueue%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Number%20of%20vertices%20in%20given%20graph%0A%23define%20V%208%0A%20%0A%2F*%20Returns%20true%20if%20there%20is%20a%20path%20from%20source%20\u2019s\u2019%20to%20sink%20\u2019t\u2019%20in%0A%20%20residual%20graph.%20Also%20fills%20parent%5B%5D%20to%20store%20the%20path%20*%2F%0Abool%20bfs(int%20rGraph%5BV%5D%5BV%5D%2C%20int%20s%2C%20int%20t%2C%20int%20parent%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20visited%20array%20and%20mark%20all%20vertices%20as%20not%20visited%0A%20%20%20%20bool%20visited%5BV%5D%3B%0A%20%20%20%20memset(visited%2C%200%2C%20sizeof(visited))%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20a%20queue%2C%20enqueue%20source%20vertex%20and%20mark%20source%20vertex%0A%20%20%20%20%2F%2F%20as%20visited%0A%20%20%20%20queue%20%3Cint%3E%20q%3B%0A%20%20%20%20q.push(s)%3B%0A%20%20%20%20visited%5Bs%5D%20%3D%20true%3B%0A%20%20%20%20parent%5Bs%5D%20%3D%20-1%3B%0A%20%0A%20%20%20%20%2F%2F%20Standard%20BFS%20Loop%0A%20%20%20%20while%20(!q.empty())%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20u%20%3D%20q.front()%3B%0A%20%20%20%20%20%20%20%20q.pop()%3B%0A%20%0A%20%20%20%20%20%20%20%20for%20(int%20v%3D0%3B%20v%3CV%3B%20v%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(visited%5Bv%5D%3D%3Dfalse%20%26%26%20rGraph%5Bu%5D%5Bv%5D%20%3E%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20q.push(v)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bv%5D%20%3D%20u%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20visited%5Bv%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20If%20we%20reached%20sink%20in%20BFS%20starting%20from%20source%2C%20then%20return%0A%20%20%20%20%2F%2F%20true%2C%20else%20false%0A%20%20%20%20return%20(visited%5Bt%5D%20%3D%3D%20true)%3B%0A%7D%0A%20%0A%2F%2F%20Returns%20tne%20maximum%20number%20of%20edge-disjoint%20paths%20from%20s%20to%20t.%0A%2F%2F%20This%20function%20is%20copy%20of%20forFulkerson()%20discussed%20at%20http%3A%2F%2Fgoo.gl%2FwtQ4Ks%0Aint%20findDisjointPaths(int%20graph%5BV%5D%5BV%5D%2C%20int%20s%2C%20int%20t)%0A%7B%0A%20%20%20%20int%20u%2C%20v%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20a%20residual%20graph%20and%20fill%20the%20residual%20graph%20with%0A%20%20%20%20%2F%2F%20given%20capacities%20in%20the%20original%20graph%20as%20residual%20capacities%0A%20%20%20%20%2F%2F%20in%20residual%20graph%0A%20%20%20%20int%20rGraph%5BV%5D%5BV%5D%3B%20%2F%2F%20Residual%20graph%20where%20rGraph%5Bi%5D%5Bj%5D%20indicates%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20residual%20capacity%20of%20edge%20from%20i%20to%20j%20(if%20there%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20is%20an%20edge.%20If%20rGraph%5Bi%5D%5Bj%5D%20is%200%2C%20then%20there%20is%20not)%0A%20%20%20%20for%20(u%20%3D%200%3B%20u%20%3C%20V%3B%20u%2B%2B)%0A%20%20%20%20%20%20%20%20for%20(v%20%3D%200%3B%20v%20%3C%20V%3B%20v%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20rGraph%5Bu%5D%5Bv%5D%20%3D%20graph%5Bu%5D%5Bv%5D%3B%0A%20%0A%20%20%20%20int%20parent%5BV%5D%3B%20%20%2F%2F%20This%20array%20is%20filled%20by%20BFS%20and%20to%20store%20path%0A%20%0A%20%20%20%20int%20max_flow%20%3D%200%3B%20%20%2F%2F%20There%20is%20no%20flow%20initially%0A%20%0A%20%20%20%20%2F%2F%20Augment%20the%20flow%20while%20tere%20is%20path%20from%20source%20to%20sink%0A%20%20%20%20while%20(bfs(rGraph%2C%20s%2C%20t%2C%20parent))%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20minimum%20residual%20capacity%20of%20the%20edges%20along%20the%0A%20%20%20%20%20%20%20%20%2F%2F%20path%20filled%20by%20BFS.%20Or%20we%20can%20say%20find%20the%20maximum%20flow%0A%20%20%20%20%20%20%20%20%2F%2F%20through%20the%20path%20found.%0A%20%20%20%20%20%20%20%20int%20path_flow%20%3D%20INT_MAX%3B%0A%20%0A%20%20%20%20%20%20%20%20for%20(v%3Dt%3B%20v!%3Ds%3B%20v%3Dparent%5Bv%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20u%20%3D%20parent%5Bv%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20path_flow%20%3D%20min(path_flow%2C%20rGraph%5Bu%5D%5Bv%5D)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20update%20residual%20capacities%20of%20the%20edges%20and%20reverse%20edges%0A%20%20%20%20%20%20%20%20%2F%2F%20along%20the%20path%0A%20%20%20%20%20%20%20%20for%20(v%3Dt%3B%20v%20!%3D%20s%3B%20v%3Dparent%5Bv%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20u%20%3D%20parent%5Bv%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20rGraph%5Bu%5D%5Bv%5D%20-%3D%20path_flow%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20rGraph%5Bv%5D%5Bu%5D%20%2B%3D%20path_flow%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Add%20path%20flow%20to%20overall%20flow%0A%20%20%20%20%20%20%20%20max_flow%20%2B%3D%20path_flow%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Return%20the%20overall%20flow%20(max_flow%20is%20equal%20to%20maximum%0A%20%20%20%20%2F%2F%20number%20of%20edge-disjoint%20paths)%0A%20%20%20%20return%20max_flow%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Let%20us%20create%20a%20graph%20shown%20in%20the%20above%20example%0A%20%20%20%20int%20graph%5BV%5D%5BV%5D%20%3D%20%7B%20%7B0%2C%201%2C%201%2C%201%2C%200%2C%200%2C%200%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%201%2C%200%2C%200%2C%200%2C%200%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%200%2C%201%2C%200%2C%200%2C%201%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%200%2C%200%2C%200%2C%200%2C%201%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%201%2C%200%2C%200%2C%200%2C%200%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%201%2C%200%2C%200%2C%200%2C%200%2C%200%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%200%2C%200%2C%200%2C%201%2C%200%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%200%2C%200%2C%200%2C%200%2C%200%2C%200%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%3B%0A%20%0A%20%20%20%20int%20s%20%3D%200%3B%0A%20%20%20%20int%20t%20%3D%207%3B%0A%20%20%20%20cout%20%3C%3C%20%22There%20can%20be%20maximum%20%22%20%3C%3C%20findDisjointPaths(graph%2C%20s%2C%20t)%0A%20%20%20%20%20%20%20%20%20%3C%3C%20%22%20edge-disjoint%20paths%20from%20%22%20%3C%3C%20s%20%3C%3C%22%20to%20%22%3C%3C%20t%20%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>There can be maximum 2 edge-disjoint paths from 0 to 7<\/pre>\n<p><strong>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":"<p>C++ Algorithm &#8211; Find maximum number of edge disjoint paths between two vertices &#8211; Graph Algorithm &#8211; 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":[83515,1,73906,78429],"tags":[78743,78742,78744,78749,78737,78741,78738,78745,78747,78736,78740,78739,78748],"class_list":["post-26415","post","type-post","status-publish","format-standard","hentry","category-c-programming-3","category-coding","category-graph-algorithms","category-maximum-flow","tag-disjoint-paths-in-a-network","tag-edge-disjoint-definition","tag-edge-disjoint-meaning","tag-edge-disjoint-path-algorithm","tag-edge-disjoint-path-problem","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\/26415","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=26415"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26415\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26415"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26415"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26415"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}