Skip to content

Commit df53edc

Browse files
thuva4thuva4
authored
Merge branch 'master' into GoHammingDistance
2 parents 7a49f80 + fecd20f commit df53edc

3 files changed

Lines changed: 201 additions & 0 deletions

File tree

‎CONTRIBUTING.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -137,4 +137,5 @@ Unfortunately, sometimes the bug can be only reproduced in your project or in yo
137137
- [SrGrace](https://github.com/SrGrace)
138138
- [d-grossman](https://github.com/d-grossman)
139139
- [javmonisu](https://github.com/javmonisu)
140+
- [lena15n](https://github.com/lena15n)
140141
- [stripedpajamas](https://github.com/stripedpajamas)

‎EdmondsKarp/Java/EdmondsKarp.java‎

Lines changed: 199 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,199 @@
1+
import java.util.*;
2+
3+
public class EdmondsKarp {
4+
public static void main(String[] args) {
5+
int verticesCount = 6;
6+
double[][] capacity = initCapacity(verticesCount);
7+
int s = 0;
8+
int t = verticesCount - 1;
9+
Map<Integer, List<Edge>> graphForwardEdges = initForwardGraphEdges();
10+
Map<Integer, List<Edge>> graphReverseEdges = initReverseGraphEdges();
11+
12+
double maxFlow = calculateMaxFlow(graphForwardEdges, graphReverseEdges, s, t, capacity);
13+
System.out.println(maxFlow);
14+
}
15+
16+
private static double calculateMaxFlow(Map<Integer, List<Edge>> graphForwardEdges,
17+
Map<Integer, List<Edge>> graphReverseEdges,
18+
int s, int t, double[][] capacity) {
19+
int verticesCount = graphForwardEdges.size();
20+
double[][] flow = new double[verticesCount][verticesCount];
21+
double maxFlow = 0.0;
22+
boolean isPathExist = true;
23+
Deque<Integer> queue = new ArrayDeque<>();
24+
25+
while (isPathExist) {
26+
Edge[] parent = new Edge[verticesCount];
27+
boolean[] visited = new boolean[verticesCount];
28+
queue.addLast(s);
29+
30+
// choose path from s to t
31+
while (!queue.isEmpty()) {
32+
int currentVertex = queue.pollFirst();
33+
visited[currentVertex] = true;
34+
List<Edge> outEdges = graphForwardEdges.get(currentVertex);
35+
36+
for (Edge edge : outEdges) {
37+
int to = edge.getTo();
38+
if (!visited[to]) {
39+
if (capacity[currentVertex][to] - flow[currentVertex][to] > 0 &&
40+
flow[currentVertex][to] >= 0) {
41+
parent[to] = edge;
42+
queue.addLast(to);
43+
}
44+
}
45+
}
46+
47+
List<Edge> inEdges = graphReverseEdges.get(currentVertex);
48+
for (Edge edge : inEdges) {
49+
int from = edge.getFrom();
50+
if (!visited[from]) {
51+
if (flow[from][currentVertex] > 0) {
52+
parent[from] = edge;
53+
queue.addLast(from);
54+
}
55+
}
56+
}
57+
}
58+
59+
isPathExist = visited[t];
60+
61+
// find max possible flow of the chosen path
62+
if (isPathExist) {
63+
int child = t;
64+
double bottleneck = Double.MAX_VALUE;
65+
66+
while (child != s) {
67+
Edge edge = parent[child];
68+
if (!edge.isReverse()) {
69+
bottleneck = Math.min(bottleneck, capacity[edge.getFrom()][edge.getTo()] -
70+
flow[edge.getFrom()][edge.getTo()]);
71+
} else {
72+
bottleneck = Math.min(bottleneck, flow[edge.getFrom()][edge.getTo()]);
73+
}
74+
75+
child = edge.isReverse() ? edge.getTo() : edge.getFrom();
76+
}
77+
78+
// update flow
79+
maxFlow += bottleneck;
80+
child = t;
81+
while (child != s) {
82+
Edge edge = parent[child];
83+
int from = (!edge.isReverse()) ? edge.getFrom() : edge.getTo();
84+
flow[from][child] += bottleneck;
85+
flow[child][from] -= bottleneck;
86+
child = (!edge.isReverse()) ? edge.getFrom() : edge.getTo();
87+
}
88+
}
89+
}
90+
91+
return maxFlow;
92+
}
93+
94+
private static double[][] initCapacity(int verticesCount) {
95+
double[][] capacity = new double[verticesCount][verticesCount];
96+
capacity[0][1] = 10;
97+
capacity[1][0] = 10;
98+
99+
capacity[0][3] = 10;
100+
capacity[3][0] = 10;
101+
102+
103+
capacity[1][2] = 4;
104+
capacity[2][1] = 4;
105+
106+
capacity[1][3] = 2;
107+
capacity[3][1] = 2;
108+
109+
capacity[1][4] = 8;
110+
capacity[4][1] = 8;
111+
112+
113+
capacity[2][5] = 10;
114+
capacity[5][2] = 10;
115+
116+
117+
capacity[3][4] = 9;
118+
capacity[4][3] = 9;
119+
120+
121+
capacity[4][2] = 6;
122+
capacity[2][4] = 6;
123+
124+
capacity[4][5] = 10;
125+
capacity[5][4] = 10;
126+
127+
return capacity;
128+
}
129+
130+
private static Map<Integer, List<Edge>> initForwardGraphEdges() {
131+
Map<Integer, List<Edge>> graph = new HashMap<>();
132+
graph.put(0, createForwardEdges(0, 1, 3));
133+
graph.put(1, createForwardEdges(1, 2, 3, 4));
134+
graph.put(2, createForwardEdges(2, 5));
135+
graph.put(3, createForwardEdges(3, 4));
136+
graph.put(4, createForwardEdges(4, 2, 5));
137+
graph.put(5, Collections.emptyList());
138+
139+
return graph;
140+
}
141+
142+
private static Map<Integer, List<Edge>> initReverseGraphEdges() {
143+
Map<Integer, List<Edge>> graph = new HashMap<>();
144+
graph.put(0, Collections.emptyList());
145+
graph.put(1, Collections.emptyList());
146+
graph.put(2, createReverseEdges(2, 1, 4));
147+
graph.put(3, createReverseEdges(3, 1));
148+
graph.put(4, createReverseEdges(4, 1, 3));
149+
graph.put(5, Collections.emptyList());
150+
151+
return graph;
152+
}
153+
154+
private static List<Edge> createForwardEdges(int from, Integer... toVertices) {
155+
List<Edge> edges = new ArrayList<>();
156+
157+
for (Integer to : toVertices) {
158+
Edge edge = new Edge(from, to, false);
159+
edges.add(edge);
160+
}
161+
162+
return edges;
163+
}
164+
165+
private static List<Edge> createReverseEdges(int to, Integer... fromVertices) {
166+
List<Edge> edges = new ArrayList<>();
167+
168+
for (Integer from : fromVertices) {
169+
Edge edge = new Edge(from, to, true);
170+
edges.add(edge);
171+
}
172+
173+
return edges;
174+
}
175+
176+
private static class Edge {
177+
private int from;
178+
private int to;
179+
private boolean isReverse;
180+
181+
Edge(int from, int to, boolean isReverse) {
182+
this.from = from;
183+
this.to = to;
184+
this.isReverse = isReverse;
185+
}
186+
187+
int getFrom() {
188+
return from;
189+
}
190+
191+
int getTo() {
192+
return to;
193+
}
194+
195+
boolean isReverse() {
196+
return isReverse;
197+
}
198+
}
199+
}

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@ DepthFirstSearch | :+1: | :+1: | | | :+1: | :+1: | | | |
2121
Dijkstra's | :+1: | :+1: | | | :+1: | | :+1: | | |
2222
Doomsday | :+1: | :+1: | | | | :+1: | | | | :+1: | :+1:
2323
EditDistance | | :+1: | | | :+1: | | | |
24+
Edmonds-Karp | :+1: | | | | | | | |
2425
ElevatorAlgorithm | :+1: | | | | | | | |
2526
Fast Fourier Transform | | | | | :+1: | | | |
2627
Fibonacci | :+1: | :+1: | | :+1: | :+1: | :+1: | | :+1: | :+1: | |

0 commit comments

Comments
 (0)