Skip to content

Commit e1d8b6f

Browse files
alxkmalxkm
authored
refactor: FordFulkerson (TheAlgorithms#5384)
1 parent e5c0e4b commit e1d8b6f

File tree

2 files changed

+128
-56
lines changed

2 files changed

+128
-56
lines changed

‎src/main/java/com/thealgorithms/dynamicprogramming/FordFulkerson.java‎

Lines changed: 34 additions & 56 deletions
Original file line numberDiff line numberDiff line change
@@ -2,76 +2,54 @@
22

33
import java.util.LinkedList;
44
import java.util.Queue;
5-
import java.util.Vector;
65

76
public final class FordFulkerson {
8-
private FordFulkerson() {
9-
}
10-
11-
static final int INF = 987654321;
12-
// edges
13-
static int vertexCount;
14-
static int[][] capacity;
15-
static int[][] flow;
7+
private static final int INF = Integer.MAX_VALUE;
168

17-
public static void main(String[] args) {
18-
System.out.println("Vertex Count : 6");
19-
vertexCount = 6;
20-
capacity = new int[vertexCount][vertexCount];
21-
22-
capacity[0][1] = 12;
23-
capacity[0][3] = 13;
24-
capacity[1][2] = 10;
25-
capacity[2][3] = 13;
26-
capacity[2][4] = 3;
27-
capacity[2][5] = 15;
28-
capacity[3][2] = 7;
29-
capacity[3][4] = 15;
30-
capacity[4][5] = 17;
31-
32-
System.out.println("Max capacity in networkFlow : " + networkFlow(0, 5));
9+
private FordFulkerson() {
3310
}
3411

35-
private static int networkFlow(int source, int sink) {
36-
flow = new int[vertexCount][vertexCount];
12+
public static int networkFlow(int vertexCount, int[][] capacity, int[][] flow, int source, int sink) {
3713
int totalFlow = 0;
14+
3815
while (true) {
39-
Vector<Integer> parent = new Vector<>(vertexCount);
40-
for (int i = 0; i < vertexCount; i++) {
41-
parent.add(-1);
42-
}
43-
Queue<Integer> q = new LinkedList<>();
44-
parent.set(source, source);
45-
q.add(source);
46-
while (!q.isEmpty() && parent.get(sink) == -1) {
47-
int here = q.peek();
48-
q.poll();
49-
for (int there = 0; there < vertexCount; ++there) {
50-
if (capacity[here][there] - flow[here][there] > 0 && parent.get(there) == -1) {
51-
q.add(there);
52-
parent.set(there, here);
16+
int[] parent = new int[vertexCount];
17+
boolean[] visited = new boolean[vertexCount];
18+
Queue<Integer> queue = new LinkedList<>();
19+
20+
queue.add(source);
21+
visited[source] = true;
22+
parent[source] = -1;
23+
24+
while (!queue.isEmpty() && !visited[sink]) {
25+
int current = queue.poll();
26+
27+
for (int next = 0; next < vertexCount; next++) {
28+
if (!visited[next] && capacity[current][next] - flow[current][next] > 0) {
29+
queue.add(next);
30+
visited[next] = true;
31+
parent[next] = current;
5332
}
5433
}
5534
}
56-
if (parent.get(sink) == -1) {
57-
break;
35+
36+
if (!visited[sink]) {
37+
break; // No more augmenting paths
5838
}
5939

60-
int amount = INF;
61-
String printer = "path : ";
62-
StringBuilder sb = new StringBuilder();
63-
for (int p = sink; p != source; p = parent.get(p)) {
64-
amount = Math.min(capacity[parent.get(p)][p] - flow[parent.get(p)][p], amount);
65-
sb.append(p + "-");
40+
int pathFlow = INF;
41+
for (int v = sink; v != source; v = parent[v]) {
42+
int u = parent[v];
43+
pathFlow = Math.min(pathFlow, capacity[u][v] - flow[u][v]);
6644
}
67-
sb.append(source);
68-
for (int p = sink; p != source; p = parent.get(p)) {
69-
flow[parent.get(p)][p] += amount;
70-
flow[p][parent.get(p)] -= amount;
45+
46+
for (int v = sink; v != source; v = parent[v]) {
47+
int u = parent[v];
48+
flow[u][v] += pathFlow;
49+
flow[v][u] -= pathFlow;
7150
}
72-
totalFlow += amount;
73-
printer += sb.reverse() + " / max flow : " + totalFlow;
74-
System.out.println(printer);
51+
52+
totalFlow += pathFlow;
7553
}
7654

7755
return totalFlow;

‎src/test/java/com/thealgorithms/dynamicprogramming/FordFulkersonTest.java‎

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
package com.thealgorithms.dynamicprogramming;
2+
3+
import static org.junit.jupiter.api.Assertions.assertEquals;
4+
5+
import org.junit.jupiter.api.Test;
6+
7+
public class FordFulkersonTest {
8+
@Test
9+
public void testMaxFlow() {
10+
int vertexCount = 6;
11+
int[][] capacity = new int[vertexCount][vertexCount];
12+
int[][] flow = new int[vertexCount][vertexCount];
13+
14+
// Setting up the capacity graph
15+
capacity[0][1] = 12;
16+
capacity[0][3] = 13;
17+
capacity[1][2] = 10;
18+
capacity[2][3] = 13;
19+
capacity[2][4] = 3;
20+
capacity[2][5] = 15;
21+
capacity[3][2] = 7;
22+
capacity[3][4] = 15;
23+
capacity[4][5] = 17;
24+
25+
int maxFlow = FordFulkerson.networkFlow(vertexCount, capacity, flow, 0, 5);
26+
assertEquals(23, maxFlow);
27+
}
28+
29+
@Test
30+
public void testNoFlow() {
31+
int vertexCount = 6;
32+
int[][] capacity = new int[vertexCount][vertexCount];
33+
int[][] flow = new int[vertexCount][vertexCount];
34+
35+
// No connections between source and sink
36+
capacity[0][1] = 10;
37+
capacity[2][3] = 10;
38+
39+
int maxFlow = FordFulkerson.networkFlow(vertexCount, capacity, flow, 1, 4);
40+
assertEquals(0, maxFlow);
41+
}
42+
43+
@Test
44+
public void testSinglePath() {
45+
int vertexCount = 6;
46+
int[][] capacity = new int[vertexCount][vertexCount];
47+
int[][] flow = new int[vertexCount][vertexCount];
48+
49+
// Setting up a single path from source to sink
50+
capacity[0][1] = 5;
51+
capacity[1][2] = 5;
52+
capacity[2][3] = 5;
53+
capacity[3][4] = 5;
54+
capacity[4][5] = 5;
55+
56+
int maxFlow = FordFulkerson.networkFlow(vertexCount, capacity, flow, 0, 5);
57+
assertEquals(5, maxFlow);
58+
}
59+
60+
@Test
61+
public void testParallelPaths() {
62+
int vertexCount = 4;
63+
int[][] capacity = new int[vertexCount][vertexCount];
64+
int[][] flow = new int[vertexCount][vertexCount];
65+
66+
// Setting up parallel paths from source to sink
67+
capacity[0][1] = 10;
68+
capacity[0][2] = 10;
69+
capacity[1][3] = 10;
70+
capacity[2][3] = 10;
71+
72+
int maxFlow = FordFulkerson.networkFlow(vertexCount, capacity, flow, 0, 3);
73+
assertEquals(20, maxFlow);
74+
}
75+
76+
@Test
77+
public void testComplexNetwork() {
78+
int vertexCount = 5;
79+
int[][] capacity = new int[vertexCount][vertexCount];
80+
int[][] flow = new int[vertexCount][vertexCount];
81+
82+
// Complex network
83+
capacity[0][1] = 10;
84+
capacity[0][2] = 10;
85+
capacity[1][3] = 4;
86+
capacity[1][4] = 8;
87+
capacity[2][4] = 9;
88+
capacity[3][2] = 6;
89+
capacity[3][4] = 10;
90+
91+
int maxFlow = FordFulkerson.networkFlow(vertexCount, capacity, flow, 0, 4);
92+
assertEquals(19, maxFlow);
93+
}
94+
}

0 commit comments

Comments
 (0)