EdmondsKarp.java

packagecom.jwetherell.algorithms.graph;


importjava.util.ArrayDeque;
importjava.util.Queue;

/**
 * In computer science, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for 
 * computing the maximum flow in a flow network in O(V*E^2) time.
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm">Edmonds-Karp Algorithm (Wikipedia)</a>
 * <br>
 * @author Mateusz Cianciara <e.cianciara@gmail.com>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
publicclassEdmondsKarp {

privatelong[][] flow; //max flow beetween i and j verticles
privatelong[][] capacity; // edge capacity
privateint[] parent; //parent
privateboolean[] visited; //just for checking if visited
@SuppressWarnings("unused")
privateintn, m;

publicEdmondsKarp(intnumOfVerticles, intnumOfEdges) {
this.n = numOfVerticles;
this.m = numOfEdges;
this.flow = newlong[n][n];
this.capacity = newlong[n][n];
this.parent = newint[n];
this.visited = newboolean[n];
 }

publicvoidaddEdge(intfrom, intto, longcapacity) {
assertcapacity >= 0;
this.capacity[from][to] += capacity;
 }

/**
 * Get maximum flow.
 * 
 * @param s source
 * @param t target
 * @return maximum flow
 */
publiclonggetMaxFlow(ints, intt) {
while (true) {
finalQueue<Integer> Q = newArrayDeque<Integer>();
Q.add(s);

for (inti = 0; i < this.n; ++i)
visited[i] = false;
visited[s] = true;

booleancheck = false;
intcurrent;
while (!Q.isEmpty()) {
current = Q.peek();
if (current == t) {
check = true;
break;
 }
Q.remove();
for (inti = 0; i < n; ++i) {
if (!visited[i] && capacity[current][i] > flow[current][i]) {
visited[i] = true;
Q.add(i);
parent[i] = current;
 }
 }
 }
if (check == false) 
break;

longtemp = capacity[parent[t]][t] - flow[parent[t]][t];
for (inti = t; i != s; i = parent[i])
temp = Math.min(temp, (capacity[parent[i]][i] - flow[parent[i]][i]));

for (inti = t; i != s; i = parent[i]) {
flow[parent[i]][i] += temp;
flow[i][parent[i]] -= temp;
 }
 }

longresult = 0;
for (inti = 0; i < n; ++i)
result += flow[s][i];
returnresult;
 }
}