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

C++ Programming:<\/strong><\/p>\n

<\/div> 
\/\/ C++ program to find maximum number of edge disjoint paths#include <iostream>#include <limits.h>#include <string.h>#include <queue>using namespace std; \/\/ Number of vertices in given graph#define V 8 \/* Returns true if there is a path from source 's' to sink 't' in  residual graph. Also fills parent[] to store the path *\/bool bfs(int rGraph[V][V], int s, int t, int parent[]){    \/\/ Create a visited array and mark all vertices as not visited    bool visited[V];    memset(visited, 0, sizeof(visited));     \/\/ Create a queue, enqueue source vertex and mark source vertex    \/\/ as visited    queue <int> q;    q.push(s);    visited[s] = true;    parent[s] = -1;     \/\/ Standard BFS Loop    while (!q.empty())    {        int u = q.front();        q.pop();         for (int v=0; v<V; v++)        {            if (visited[v]==false && rGraph[u][v] > 0)            {                q.push(v);                parent[v] = u;                visited[v] = true;            }        }    }     \/\/ If we reached sink in BFS starting from source, then return    \/\/ true, else false    return (visited[t] == true);} \/\/ Returns tne maximum number of edge-disjoint paths from s to t.\/\/ This function is copy of forFulkerson() discussed at http:\/\/goo.gl\/wtQ4Ksint findDisjointPaths(int graph[V][V], int s, int t){    int u, v;     \/\/ Create a residual graph and fill the residual graph with    \/\/ given capacities in the original graph as residual capacities    \/\/ in residual graph    int rGraph[V][V]; \/\/ Residual graph where rGraph[i][j] indicates                     \/\/ residual capacity of edge from i to j (if there                     \/\/ is an edge. If rGraph[i][j] is 0, then there is not)    for (u = 0; u < V; u++)        for (v = 0; v < V; v++)             rGraph[u][v] = graph[u][v];     int parent[V];  \/\/ This array is filled by BFS and to store path     int max_flow = 0;  \/\/ There is no flow initially     \/\/ Augment the flow while tere is path from source to sink    while (bfs(rGraph, s, t, 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.        int path_flow = INT_MAX;         for (v=t; v!=s; v=parent[v])        {            u = parent[v];            path_flow = min(path_flow, rGraph[u][v]);        }         \/\/ update residual capacities of the edges and reverse edges        \/\/ along the path        for (v=t; v != s; v=parent[v])        {            u = parent[v];            rGraph[u][v] -= path_flow;            rGraph[v][u] += path_flow;        }         \/\/ Add path flow to overall flow        max_flow += path_flow;    }     \/\/ Return the overall flow (max_flow is equal to maximum    \/\/ number of edge-disjoint paths)    return max_flow;} \/\/ Driver program to test above functionsint main(){    \/\/ Let us create a graph shown in the above example    int graph[V][V] = { {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}                      };     int s = 0;    int t = 7;    cout << "There can be maximum " << findDisjointPaths(graph, s, t)         << " edge-disjoint paths from " << s <<" to "<< t ;     return 0;}<\/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":"
C++ 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":[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}]}}