-
Notifications
You must be signed in to change notification settings - Fork 2
/
l_fordfulkerson.h
76 lines (63 loc) · 1.66 KB
/
l_fordfulkerson.h
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
#ifndef _L_FORDFULKERSON_H
#define _L_FORDFULKERSON_H
#include "l.h"
#include "l_flownetwork.h"
class FordFulkerson{
vector<bool> marked;
vector<FlowEdge*> edgeTo;
double max_flow;
FlowNetwork* G;
// use bfs to find the shortest augmenting path
bool hasAugmentingPath(FlowNetwork*g, int s, int t) {
for (int v = 0; v < g->V(); ++v) {
marked[v] = false;
edgeTo[v] = NULL;
}
queue<int> queue;
marked[s] = true;
queue.push(s);
while (!queue.empty()) {
int v = queue.front();
queue.pop();
for (FlowEdge* e : g->adj(v)) {
int w = e->other(v);
if (!marked[w] && e->residualCapacityTo(w) > 0) {
edgeTo[w] = e;
marked[w] = true;
queue.push(w);
}
}
}
return marked[t];
}
public:
FordFulkerson(FlowNetwork* g, int s, int t): G(g) {
max_flow = 0.0;
for (int v = 0; v < g->V(); ++v) {
marked.push_back(false);
edgeTo.push_back(NULL);
}
while (hasAugmentingPath(g, s, t)) {
double bottle = numeric_limits<double>::max();
// find max residual flow
for (int v = t; v != s; v = edgeTo[v]->other(v)) bottle = min(bottle, edgeTo[v]->residualCapacityTo(v));
// add residual flow to each edge of augmenting path
for (int v = t; v != s; v = edgeTo[v]->other(v)) edgeTo[v]->addResidualFlowTo(v, bottle);
max_flow += bottle;
}
}
~FordFulkerson() {
}
double maxFlow() {
return max_flow;
}
vector<FlowEdge*> flowNetwork() {
vector<FlowEdge*> result;
for (int v = 0; v < G->V(); ++v) {
for (auto e : G->adj(v))
if (e->from() == v) result.push_back(e);
}
return result;
}
};
#endif // !_L_FORDFULKERSON_H