Algorithm-and-Data-Structure/AlgorithmCode/EdmondsKarp.java at master · lemidia/Algorithm-and-Data-Structure · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
importjava.io.BufferedReader;
importjava.io.IOException;
importjava.io.InputStreamReader;
importjava.util.*;
importjava.util.Queue;
importjava.util.LinkedList;

/**
 * NetworkFlow - MaxFlow - Edmonds Karp Algorithm
 * This program is to find max flow in flow graph using Edmonds Karp method
 * Time Complexity : O(E^2V) E for Edge, V for Vertex
 * This Code was inspired by William fiset
 *
 * @author Lemidia
 */

publicclassEdmondsKarp {

staticintn; // The number of vertex
staticintm; // The number of Edge
staticintsource;
staticintsink;
staticintmaxFlow;
staticfinalintINF = Integer.MAX_VALUE;
staticinttoken; // Increasing Token
staticintvisited[]; // Visited check
staticEdgeprev[]; // Augmenting path for flow propagation
staticList<Edge>[] flowGraph;

/**
 *
 * @param from Vertex where edge starts
 * @param to Vertex where edge ends
 * @param capacity Edge Capacity
 */

staticvoidaddEdge(intfrom, intto, intcapacity){
Edgee1 = newEdge(from, to, 0, capacity);
Edgee2 = newEdge(to, from, 0, 0); // Backward Edge
e1.backward = e2; // Connecting each other
e2.backward = e1;
flowGraph[from].add(e1);
flowGraph[to].add(e2);
 }

/**
 *
 * @param e Edge
 * @return Remaining capacity of the edge
 */

staticintremainingCapacity(Edgee){ // if > 0 then residual Edge
returne.capacity - e.flow;
 }

staticvoidaugment(Edgee, intbottleNeck){
e.flow+=bottleNeck;
e.backward.flow-=bottleNeck;
 }

staticvoidcreateFlowGraph(){
maxFlow = 0;
token = 0;
visited = newint[n];
prev = newEdge[n];
flowGraph = newArrayList[n];
for (inti = 0; i < n; i++) {
flowGraph[i] = newArrayList<>();
 }
 }


// Using Breath first search to find augmenting path
staticintgetMaxFlow(){
while (true){
intbottleNeck = INF;
prev[sink] = null;
token++;
Queue<Integer> queue = newLinkedList<>();
queue.offer(source);
visited[source] = token;
while (!queue.isEmpty()){
intnode = queue.poll();
if (node == sink) // Augmenting path exist!
break;
for (Edgee : flowGraph[node]){
if (remainingCapacity(e) > 0 && visited[e.to] != token){
queue.offer(e.to);
visited[e.to] = token;
prev[e.to] = e;
 }
 }
 }
if (prev[sink] == null) // If there is no augmenting path
break;

// Finding BottleNeck flow
for (Edgeedge = prev[sink] ; edge != null ; edge = prev[edge.from]){
intremainingCapacity = remainingCapacity(edge);
if (remainingCapacity < bottleNeck)
bottleNeck = remainingCapacity;
 }

// Propagating bottleNeck flow along the augmenting path
for (Edgeedge = prev[sink] ; edge != null ; edge = prev[edge.from]){
augment(edge, bottleNeck);
 }
maxFlow+=bottleNeck;
 }
returnmaxFlow;
 }

staticvoidprintEdge(Edgee){
System.out.println(e.to + " " + e.from + " " + e.flow);
 }

publicstaticvoidmain(String[] args) throwsIOException {
n = 6;
source = n - 1;
sink = n - 2;
createFlowGraph();
// Source edges
addEdge(source, 0, 10);
addEdge(source, 1, 10);

// Sink edges
addEdge(2, sink, 10);
addEdge(3, sink, 10);

// Middle edges
addEdge(0, 1, 2);
addEdge(0, 2, 4);
addEdge(0, 3, 8);
addEdge(1, 3, 9);
addEdge(3, 2, 6);

System.out.print(getMaxFlow());
 }
staticclassEdge{
intfrom;
intto;
intflow;
intcapacity;
Edgebackward;

publicEdge(intfrom, intto, intflow, intcapacity) {
this.from = from;
this.to = to;
this.flow = flow;
this.capacity = capacity;
 }
 }
}