Links from class:
Ford-Fulkerson algorithm for solving maximum flow problems
In class today we discussed two algorithms for computing the maximum flow of a network graph: Ford-Fulkerson and Edmonds-Karp. Both are the same in implementaion except for that Ford-Fulkerson uses DFS to find augmenting paths whereas Edmonds-Karp uses BFS.
Below is an implementation of Edmonds-Karp you may use for any max flow problems you encounter!
class MaxFlow {
/**
* MAX FLOW - Edmonds Karp algorithm
*/
private final static int NN = 256; // max number of nodes
private int[][] cap = new int[NN][NN];
private int[][] fnet = new int[NN][NN];
// BFS
private int[] q = new int[NN];
private int[] prev = new int[NN];
private int qf, qb;
private int edmondsKarp(int n, int s, int t) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
fnet[i][j] = 0;
}
}
int flow = 0;
while (true) {
// find an augmenting path
for (int i = 0; i < n; i++) {
prev[i] = -1;
}
qf = qb = 0;
prev[s] = -2;
q[qb++] = s;
while (qb > qf && prev[t] == -1) {
int u = q[qf++];
int v = 0;
while (v < n) {
if (prev[v] == -1 && fnet[u][v] - fnet[v][u] < cap[u][v]) {
prev[v] = u;
q[qb++] = v;
}
v++;
}
}
// see if we are done
if (prev[t] == -1)
break;
// get the bottleneck capacity
int bot = Integer.MAX_VALUE;
int v = t;
int u = prev[v];
while (u >= 0) {
bot = Math.min(bot, cap[u][v] - fnet[u][v] + fnet[v][u]);
v = u;
u = prev[v];
}
// update the flow network
v = t;
u = prev[v];
while (u >= 0) {
fnet[u][v] += bot;
v = u;
u = prev[v];
}
flow += bot;
}
return flow;
}
private void addEdge(int u, int v, int cp) {
cap[u][v] += cp;
}
private void addEdgeUndirected(int u, int v, int cp) {
addEdge(u, v, cp);
addEdge(v, u, cp);
}
/* Max Flow example usage (UVa 820 sample network) */
private void maxFlowExample() {
int n = 4;
/* CLEAR - add source/sink if needed */
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cap[i][j] = 0;
}
}
addEdgeUndirected(0, 1, 20);
addEdgeUndirected(0, 2, 10);
addEdgeUndirected(1, 2, 5);
addEdgeUndirected(1, 3, 10);
addEdgeUndirected(2, 3, 20);
int s = 0, t = 3;
int flow = edmondsKarp(n, s, t);
System.out.println("Flow: " + flow);
}
public static void main(String args[]) {
MaxFlow mf = new MaxFlow();
mf.maxFlowExample();
}
}
Sieve of Eratosthenes
We also talked in class about generating all the primes between 2 and N. Below an implementation of the Sieve of Eratosthenes you may use to generate prime numbers.
/*
* Sieve of Eratosthenes
*/
private void sieve() {
int lim = (int) (Math.round(Math.sqrt(SIEVE_SIZE))) + 1;
nonPrimes[0] = true;
nonPrimes[1] = true;
for (int i = 4; i < SIEVE_SIZE; i += 2) {
nonPrimes[i] = true;
}
for (int i = 3; i <= lim; i += 2) {
if (!nonPrimes[i]) {
int tmp = i * i;
while (tmp < SIEVE_SIZE) {
nonPrimes[tmp] = true;
tmp += i << 1;
}
}
}
}
For next class
Assigned readings:
- Sections: 4.6 (max flow), 5 (read the first couple of sections, and dive deeper into topics that interest you)
Assigned exercises:
- Pick your final problem and email me by Saturday evening so I know that you’ve picked one.