-
Notifications
You must be signed in to change notification settings - Fork 491
/
fordFulkerson.cpp
159 lines (112 loc) Β· 3.62 KB
/
fordFulkerson.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/*
** Ford -Fulkerson Algorithm Code
** For video explanation, refer to Youtube channel in the link below:
** https://www.youtube.com/channel/UCX6rLou1VXXPVsORMVkUryg/videos
**
** PLease star the repo if you find code useful
*/
#include <iostream>
#include <vector>
#include <queue>
#include <bits/stdc++.h>
#define vvi vector<vector<int>>
using namespace std;
//Bfs implementation to return the min_cap while traversing ,if present any
int bfs(int source, int sink, vvi &residualGraph, vector<int> &parent)
{
fill(parent.begin(), parent.end(), -1);
int V = residualGraph.size();
parent[source] = -2;
queue<pair<int, int>> Q;
Q.push({source, INT_MAX});
//Starting to traverse from front node
while (!Q.empty())
{
int src = Q.front().first;
int capacity = Q.front().second;
Q.pop();
for (int dest = 0; dest < V; dest++)
{
if (dest != src && parent[dest] == -1 && residualGraph[src][dest] != 0)
{
parent[dest] = src;
int min_cap = min(capacity, residualGraph[src][dest]);
if (dest == sink)
return min_cap;
Q.push({dest, min_cap});
}
}
}
return 0;
}
void printAugmentedPaths(vvi augmentedPaths){
for(auto c:augmentedPaths){
for(auto s:c){
cout<<s<<"->";
}
cout<<endl;
}
cout<<endl;
}
int ford_fulkerson(vvi &graph, int source, int sink)
{
int max_flow = 0, min_cap = 0;
//residual graph = total capacity - flow of material (graph)
vvi residualGraph = graph;
//To print the traversed augmented path -see definition if this does not make sense
vvi augmentedPaths;
//parent array for bfs operations
vector<int> parent(graph.size(), -1);
//while we get a min_cap in the graph i.e path from source to sink having min_cap
while (min_cap = bfs(source, sink, residualGraph, parent))
{
//We get the min_capacity
max_flow += min_cap;
int u = sink;
vector<int> currentAugmentedPath;
///Updating residual graph adding back and forward edges
while (u != source)
{
currentAugmentedPath.push_back(u);
int v = parent[u];
//backedge
residualGraph[u][v] += min_cap;
//Updating the edge
residualGraph[v][u] -= min_cap;
u = v;
}
//Becuse loop will terminate without adding source
currentAugmentedPath.push_back(source);
//WE push the nodes from sink to source so reverse is necessary
std::reverse(currentAugmentedPath.begin(),currentAugmentedPath.end());
augmentedPaths.push_back(currentAugmentedPath);
}
printAugmentedPaths(augmentedPaths);
return max_flow;
}
void addEdge(vvi &graph, int src, int dest, int cap)
{
graph[src][dest] = cap;
}
int main()
{
int V,E,u,v,w,src,sink;
cin>>V>>E;
cout<<"Enter Source & Sink Nodes"<<endl;
cin>>src>>sink;
//int V = 6;
vector<vector<int>> graph(V, vector<int>(V, 0));
while(E--){
cin>>u>>v>>w;
addEdge(graph, u, v, w);
}
// addEdge(graph, 0, 1, 4);
// addEdge(graph, 0, 3, 3);
// addEdge(graph, 1, 2, 4);
// addEdge(graph, 2, 3, 3);
// addEdge(graph, 2, 5, 2);
// addEdge(graph, 3, 4, 6);
// addEdge(graph, 4, 5, 6);
cout << "Flow: " << ford_fulkerson(graph, src,sink) << endl;
return 0;
}