For those who are interested, a C++11 implementation of highest-label push relabel maximum flow algorithm. Style and format is taken from here.
Uses just gap relabeling heuristic. Global relabeling heuristic was implemented but removed because of poor performance.
/*
Implementation of highest-label push-relabel maximum flow
with gap relabeling heuristic.
Running time:
O(|V|^2|E|^{1/2})
Usage:
- add edges by AddEdge()
- GetMaxFlow(s, t) returns the maximum flow from s to t
Input:
- graph, constructed using AddEdge()
- (s, t), (source, sink)
Output:
- maximum flow value
Todo:
- implement Phase II (flow network from preflow network)
- implement GetMinCut()
*/
template <class T> struct Edge {
int from, to, index;
T cap, flow;
Edge(int from, int to, T cap, T flow, int index): from(from), to(to), cap(cap), flow(flow), index(index) {}
};
template <class T> struct PushRelabel {
int n;
vector <vector <Edge <T>>> adj;
vector <T> excess;
vector <int> dist, count;
vector <bool> active;
vector <vector <int>> B;
int b;
queue <int> Q;
PushRelabel (int n): n(n), adj(n) {}
void AddEdge (int from, int to, int cap) {
adj[from].push_back(Edge <T>(from, to, cap, 0, adj[to].size()));
if (from == to) {
adj[from].back().index++;
}
adj[to].push_back(Edge <T>(to, from, 0, 0, adj[from].size() - 1));
}
void Enqueue (int v) {
if (!active[v] && excess[v] > 0 && dist[v] < n) {
active[v] = true;
B[dist[v]].push_back(v);
b = max(b, dist[v]);
}
}
void Push (Edge <T> &e) {
T amt = min(excess[e.from], e.cap - e.flow);
if (dist[e.from] == dist[e.to] + 1 && amt > T(0)) {
e.flow += amt;
adj[e.to][e.index].flow -= amt;
excess[e.to] += amt;
excess[e.from] -= amt;
Enqueue(e.to);
}
}
void Gap (int k) {
for (int v = 0; v < n; v++) if (dist[v] >= k) {
count[dist[v]]--;
dist[v] = max(dist[v], n);
count[dist[v]]++;
Enqueue(v);
}
}
void Relabel (int v) {
count[dist[v]]--;
dist[v] = n;
for (auto e: adj[v]) if (e.cap - e.flow > 0) {
dist[v] = min(dist[v], dist[e.to] + 1);
}
count[dist[v]]++;
Enqueue(v);
}
void Discharge(int v) {
for (auto &e: adj[v]) {
if (excess[v] > 0) {
Push(e);
} else {
break;
}
}
if (excess[v] > 0) {
if (count[dist[v]] == 1) {
Gap(dist[v]);
} else {
Relabel(v);
}
}
}
T GetMaxFlow (int s, int t) {
dist = vector <int>(n, 0), excess = vector<T>(n, 0), count = vector <int>(n + 1, 0), active = vector <bool>(n, false), B = vector <vector <int>>(n), b = 0;
for (auto &e: adj[s]) {
excess[s] += e.cap;
}
count[0] = n;
Enqueue(s);
active[t] = true;
while (b >= 0) {
if (!B[b].empty()) {
int v = B[b].back();
B[b].pop_back();
active[v] = false;
Discharge(v);
} else {
b--;
}
}
return excess[t];
}
T GetMinCut (int s, int t, vector <int> &cut);
};
I read a lot of articles about push-relabel algorithm, I'm still not able to understand it :(
http://infolab.stanford.edu/pub/cstr/reports/cs/tr/94/1523/CS-TR-94-1523.pdf
The TopCoder one is pretty good save for one or two of the proof explanations later on. The basis for the algorithm is the operations themselves (push, relabel) and a few key properties that hold throughout the entire algorithm, the most important of which being that a residual edge implies a height restriction. For me, I had trouble understanding it on the large scale, so I worked through each individual part and understood how they fit together for the bigger algorithm. Although I still have some trouble understanding why the whole algorithm works intuitively, I understand each individual part, which is helpful when actually implementing the algorithm. If you have any questions regarding the individual parts, I'm sure I or someone else in the community could explain it. Also, if someone could post a larger scale explanation or motivation for the algorithm that would be very beneficial.
Although Ford-Fulkerson method with shortest augment implementation has complexity O(V2E), it is in practice faster than push-relabel method, and also easy to implement(about 15 lines for a recursive version, and 25 lines for a non-recursive one). That bound looks like not possible to reach, however complexity of push-relabel might be a tight bound.
I think FF method will get TLE if the graph of some data is special. I used to choose Dinic algorithm to solve network flow.
It is usually called Edmonds-Karp algorithm.
That's wrong, there are many problems even on the programming contests about networks with unit capacities where E-K works significantly slower than Dinic algorithm or preflow-push algorithm.
That's also wrong, there are algorithms that are faster. The fastest known is Orlin's algorithm, it has a running time of O(nm) that is believed to be a tight bound for the maximum flow problem in general case (though the tightness is not proven).
Relevant
if you want to check if an edge from node u to node v is part of the minimum cut you can add this function
I'd be curious about how you concluded that the global relabeling heuristics exhibits poor performance.