# Algorithm Implementation/Graphs/Maximum flow/Edmonds-Karp

Jump to navigation Jump to search

## Java

```/*
* Java Implementation of Edmonds-Karp Algorithm *
* By: Pedro Contipelli                          *

Input Format:                                     (Sample Input)

N , E         | (N total nodes , E total edges) |  4 5
u1 , v1 , c1  |                                 |  0 1 1000
u2 , v2 , c2  | Each line u , v , c represents  |  1 2 1
u3 , v3 , c3  | an edge in the graph from node  |  0 2 1000
...          | u to node v with capacity C     |  1 3 1000
uE , vE , cE  |                                 |  2 3 1000

Nodes 0 and N-1 are assumed to be the source and sink (respectively).
*/

import java.util.*;
public class EdmondsKarp {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);

int nodes = scan.nextInt();
int edges = scan.nextInt();
int source = 0;
int sink = nodes - 1;

Node[] graph = new Node[nodes];

// Initialize each node
for (int i = 0; i < nodes; i++)
graph[i] = new Node();

// Initialize each edge
for (int i = 0; i < edges; i++) {
int u = scan.nextInt();
int v = scan.nextInt();
int c = scan.nextInt();

// Note edge "b" is not actually in the input graph
// It is a construct that allows us to solve the problem
Edge a = new Edge(u , v , 0 , c);
Edge b = new Edge(v , u , 0 , 0);

// Set pointer from each edge "a" to
// its reverse edge "b" and vice versa
a.setReverse(b);
b.setReverse(a);

graph[u].edges.add(a);
graph[v].edges.add(b);
}

int maxFlow = 0;

while (true) {
// Parent array used for storing path
// (parent[i] stores edge used to get to node i)
Edge[] parent = new Edge[nodes];

ArrayList<Node> q = new ArrayList<>();
q.add(graph[source]);

// BFS finding shortest augmenting path
while (!q.isEmpty()) {
Node curr = q.remove(0);

// Checks that edge has not yet been visited, and it doesn't
// point to the source, and it is possible to send flow through it.
for (Edge e : curr.edges)
if (parent[e.v] == null && e.v != source && e.capacity > e.flow) {
parent[e.v] = e;
q.add(graph[e.v]);
}
}

// If sink was NOT reached, no augmenting path was found.
// Algorithm terminates and prints out max flow.
if (parent[sink] == null)
break;

// If sink WAS reached, we will push more flow through the path
int pushFlow = Integer.MAX_VALUE;

// Finds maximum flow that can be pushed through given path
// by finding the minimum residual flow of every edge in the path
for (Edge e = parent[sink]; e != null; e = parent[e.u])
pushFlow = Math.min(pushFlow , e.capacity - e.flow);

// Adds to flow values and subtracts from reverse flow values in path
for (Edge e = parent[sink]; e != null; e = parent[e.u]) {
e.flow += pushFlow;
e.reverse.flow -= pushFlow;
}

maxFlow += pushFlow;
}

System.out.println("Max Flow: " + maxFlow);

scan.close();
}
}

// No explicit constructor is necessary :P

class Node {

// List of edges also includes reverse edges that
// are not in original given graph (for push-back flow)
ArrayList<Edge> edges = new ArrayList<>();

}

class Edge {

int u , v , flow , capacity;
Edge reverse;

public Edge(int u , int v , int flow , int capacity) {
this.u = u;
this.v = v;
this.flow = flow;
this.capacity = capacity;
}

public void setReverse(Edge e) {
reverse = e;
}

}
```

## MATLAB

This code is the direct transcription in MATLAB language of the pseudocode shown in the Wikipedia article of the Edmonds-Karp algorithm.

```function [f,F]=EdmondsKarp(C,E,s,t)

%Initial flow is 0
f=0;

imax=size(C,1);
F=zeros(imax);

while(1)
[m,P]=BreadthFirstSearch(C,E,s,t,F);

%The end is reached when the capacity of the returned path is 0
if(m==0)
break;
end

%The total flow is increased by m
f=f+m;

%The flow for every edge on the path is increased by m
v=t;
while(v~=s)
u=P(v);
F(u,v)=F(u,v)+m;
F(v,u)=F(v,u)-m;
v=u;
end
end

end

function [M,P]=BreadthFirstSearch(C,E,s,t,F)

n=size(C,1);
P=zeros(n,1);
M=zeros(n);
M(s)=Inf;

for u=1:n
P(u)=-1;
end
P(s)=-2;

%Q is used as a queue
Q=[];
Q=vertcat(Q,s);

while(isempty(Q)==0)
u=Q(1);
Q(1)='';

neighbors=E{u};
for i=1:length(neighbors)
v=neighbors(i);
if(C(u,v)-F(u,v)>0 && P(v)==-1)
P(v)=u;
M(v)=min(M(u),C(u,v)-F(u,v));
if(v~=t)
Q(length(Q)+1)=v;
else
M=M(t);
return;
end
end
end
end

M=0;

end
```