Algorithm-and-Data-Structure/AlgorithmCode/FordFulkersonMethod.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
importjava.io.*;
importjava.util.*;
importjava.util.LinkedList;

/**
 * NetworkFlow - MaxFlow : Ford Fulkerson method
 * This program is to find max flow in flow graph using Ford Fulkerson method
 * Time Complexity : O(Ef) E for Edge, f for flow
 *
 * @author Lemidia
 */

publicclassFordFulkersonMethod{

staticList<Edge>[] flowGraph; // AdjacenyList for flow graph
staticintvisited[]; // Visit check for dfs to prevent from making visit same node twice or more
staticintvisitedToken = 1; // Increasing token for duplicating visited node which used in dfs
staticintsource;
staticintsink;
staticintn; // The number of vertex
staticfinallongINF = Long.MAX_VALUE/2;

publicstaticvoidcreatGraph(){
visited = newint[n];
flowGraph = newArrayList[n];
for (inti = 0; i < n; i++) {
flowGraph[i] = newArrayList<>();
 }
 }

publicstaticvoidaddEdge(intfrom, intto, intcapacity){
Edgeforward = newEdge(from, to, 0, capacity);
Edgeresidual = newEdge(to, from, 0, 0);
forward.residual = residual; // pair forward and residual;
residual.residual = forward; // pair residual and forward;
flowGraph[from].add(forward);
flowGraph[to].add(residual);
 }

// Add a bottleneck flow to All edge in Augmenting path.
publicstaticvoidaugment(Edgee, longbottleNeck){
e.flow+=bottleNeck;
e.residual.flow-=bottleNeck;
 }

publicstaticlonggetMaxFlow(){
longmaxFlow = 0;
// Find Augmenting path
for (longf = dfs(source, INF); f!=0 ; f = dfs(source, INF)){
maxFlow+=f;
visitedToken++;
 }
returnmaxFlow;
 }

publicstaticlongremainingCapacity(Edgee){
returne.capacity - e.flow;
 }

publicstaticlongdfs(intnode, longflow){
if (node == sink)
returnflow;
visited[node] = visitedToken;
for (Edgee : flowGraph[node]){
if (remainingCapacity(e) > 0 && visited[e.to] != visitedToken){
longbottleNeck = dfs(e.to, min(flow, remainingCapacity(e)));
if (bottleNeck>0) {
augment(e, bottleNeck);
returnbottleNeck;
 }
 }
 }
return0;
 }

staticlongmin(longa, longb){
returna<b?a:b;
 }

staticinttransfer(chara){
if (a<='Z')
returna-'A';
return26+(a-'a');
 }

publicstaticvoidmain(String[] args) throwsIOException {
BufferedReaderbr = newBufferedReader(newInputStreamReader(System.in));
StringBuildersb = newStringBuilder();
StringTokenizerst;

n = 6;
source = n - 1;
sink = n - 2;
creatGraph();
// Source edges
addEdge(source, 0, 10);
addEdge(source, 1, 10);

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;
Edgeresidual;

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