# Java Program to Find the Minimum Cut of a Graph using Karger’s Algorithm

This is a java program to find global min cut of the graph. In computer science and graph theory, Karger’s algorithm is a randomized algorithm to compute a minimum cut of a connected graph.

Here is the source code of the Java Program to Implement an Algorithm to Find the Global min Cut in a Graph. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

1. ` `
2. `package com.sanfoundry.graph;`
3. ` `
4. `import java.io.BufferedReader;`
5. `import java.io.FileReader;`
6. `import java.util.ArrayList;`
7. `import java.util.Comparator;`
8. `import java.util.HashSet;`
9. `import java.util.Iterator;`
10. `import java.util.LinkedHashMap;`
11. `import java.util.List;`
12. `import java.util.Map;`
13. `import java.util.Random;`
14. `import java.util.Set;`
15. `import java.util.TreeMap;`
16. ` `
17. `public class GlobalMinCut`
18. `{`
19. `    private static class Graph`
20. `    {`
21. `        private final Map<Integer, Vertex> vertices = new TreeMap<Integer, Vertex>(`
22. `                new Comparator<Integer>()`
23. `                {`
24. `                    @Override`
25. `                    public int compare(Integer arg0, Integer arg1)`
26. `                    {`
27. `                        return arg0.compareTo(arg1);`
28. `                    }`
29. `                });`
30. `        private final List<Edge> edges = new ArrayList<Edge>();`
31. ` `
32. `        public void addVertex(Vertex v)`
33. `        {`
34. `            vertices.put(v.lbl, v);`
35. `        }`
36. ` `
37. `        public Vertex getVertex(int lbl)`
38. `        {`
39. `            Vertex v;`
40. `            if ((v = vertices.get(lbl)) == null)`
41. `            {`
42. `                v = new Vertex(lbl);`
43. `                addVertex(v);`
44. `            }`
45. `            return v;`
46. `        }`
47. `    }`
48. ` `
49. `    private static class Vertex`
50. `    {`
51. `        private final int lbl;`
52. `        private final Set<Edge> edges = new HashSet<Edge>();`
53. ` `
54. `        public Vertex(int lbl)`
55. `        {`
56. `            this.lbl = lbl;`
57. `        }`
58. ` `
59. `        public void addEdge(Edge edge)`
60. `        {`
61. `            edges.add(edge);`
62. `        }`
63. ` `
64. `        public Edge getEdgeTo(Vertex v2)`
65. `        {`
66. `            for (Edge edge : edges)`
67. `            {`
68. `                if (edge.contains(this, v2))`
69. `                    return edge;`
70. `            }`
71. `            return null;`
72. `        }`
73. `    }`
74. ` `
75. `    private static class Edge`
76. `    {`
77. `        private final List<Vertex> ends = new ArrayList<Vertex>();`
78. ` `
79. `        public Edge(Vertex fst, Vertex snd)`
80. `        {`
81. `            if (fst == null || snd == null)`
82. `            {`
83. `                throw new IllegalArgumentException("Both vertices are required");`
84. `            }`
85. `            ends.add(fst);`
86. `            ends.add(snd);`
87. `        }`
88. ` `
89. `        public boolean contains(Vertex v1, Vertex v2)`
90. `        {`
91. `            return ends.contains(v1) && ends.contains(v2);`
92. `        }`
93. ` `
94. `        public Vertex getOppositeVertex(Vertex v)`
95. `        {`
96. `            if (!ends.contains(v))`
97. `            {`
98. `                throw new IllegalArgumentException("Vertex " + v.lbl);`
99. `            }`
100. `            return ends.get(1 - ends.indexOf(v));`
101. `        }`
102. ` `
103. `        public void replaceVertex(Vertex oldV, Vertex newV)`
104. `        {`
105. `            if (!ends.contains(oldV))`
106. `            {`
107. `                throw new IllegalArgumentException("Vertex " + oldV.lbl);`
108. `            }`
109. `            ends.remove(oldV);`
110. `            ends.add(newV);`
111. `        }`
112. `    }`
113. ` `
114. `    public static int minCut(Graph gr)`
115. `    {`
116. `        Random rnd = new Random();`
117. `        while (gr.vertices.size() > 2)`
118. `        {`
119. `            Edge edge = gr.edges.remove(rnd.nextInt(gr.edges.size()));`
120. `            Vertex v1 = cleanVertex(gr, edge.ends.get(0), edge);`
121. `            Vertex v2 = cleanVertex(gr, edge.ends.get(1), edge);`
122. `            // contract`
123. `            Vertex mergedVertex = new Vertex(v1.lbl);`
124. `            redirectEdges(gr, v1, mergedVertex);`
125. `            redirectEdges(gr, v2, mergedVertex);`
126. `            gr.addVertex(mergedVertex);`
127. `        }`
128. `        return gr.edges.size();`
129. `    }`
130. ` `
131. `    private static Vertex cleanVertex(Graph gr, Vertex v, Edge e)`
132. `    {`
133. `        gr.vertices.remove(v.lbl);`
134. `        v.edges.remove(e);`
135. `        return v;`
136. `    }`
137. ` `
138. `    private static void redirectEdges(Graph gr, Vertex fromV, Vertex toV)`
139. `    {`
140. `        for (Iterator<Edge> it = fromV.edges.iterator(); it.hasNext();)`
141. `        {`
142. `            Edge edge = it.next();`
143. `            it.remove();`
144. `            if (edge.getOppositeVertex(fromV) == toV)`
145. `            {`
146. `                // remove self-loop`
147. `                toV.edges.remove(edge);`
148. `                gr.edges.remove(edge);`
149. `            }`
150. `            else`
151. `            {`
152. `                edge.replaceVertex(fromV, toV);`
153. `                toV.addEdge(edge);`
154. `            }`
155. `        }`
156. `    }`
157. ` `
158. `    public static int[][] getArray(String relPath)`
159. `    {`
160. `        Map<Integer, List<Integer>> vertices = new LinkedHashMap<Integer, List<Integer>>();`
161. `        FileReader fr;`
162. `        try`
163. `        {`
164. `            fr = new FileReader(relPath);`
165. `            BufferedReader br = new BufferedReader(fr);`
166. `            String line;`
167. `            while ((line = br.readLine()) != null)`
168. `            {`
169. `                String[] split = line.trim().split("(\\s)+");`
170. `                List<Integer> adjList = new ArrayList<Integer>();`
171. `                for (int i = 1; i < split.length; i++)`
172. `                {`
173. `                    adjList.add(Integer.parseInt(split[i]) - 1);`
174. `                }`
175. `                vertices.put(Integer.parseInt(split[0]) - 1, adjList);`
176. `            }`
177. `            fr.close();`
178. `        }`
179. `        catch (Exception e)`
180. `        {`
181. `            e.printStackTrace();`
182. `        }`
183. `        int[][] array = new int[vertices.size()][];`
184. `        for (Map.Entry<Integer, List<Integer>> entry : vertices.entrySet())`
185. `        {`
186. `            List<Integer> adjList = entry.getValue();`
187. `            int[] adj = new int[adjList.size()];`
188. `            for (int i = 0; i < adj.length; i++)`
189. `            {`
190. `                adj[i] = adjList.get(i);`
191. `            }`
192. `            array[entry.getKey()] = adj;`
193. `        }`
194. `        return array;`
195. `    }`
196. ` `
197. `    private static Graph createGraph(int[][] array)`
198. `    {`
199. `        Graph gr = new Graph();`
200. `        for (int i = 0; i < array.length; i++)`
201. `        {`
202. `            Vertex v = gr.getVertex(i);`
203. `            for (int edgeTo : array[i])`
204. `            {`
205. `                Vertex v2 = gr.getVertex(edgeTo);`
206. `                Edge e;`
207. `                if ((e = v2.getEdgeTo(v)) == null)`
208. `                {`
209. `                    e = new Edge(v, v2);`
210. `                    gr.edges.add(e);`
211. `                    v.addEdge(e);`
212. `                    v2.addEdge(e);`
213. `                }`
214. `            }`
215. `        }`
216. `        return gr;`
217. `    }`
218. ` `
219. `    /**`
220. `     * @param args`
221. `     */`
222. `    public static void main(String[] args)`
223. `    {`
224. `        int[][] arr = getArray("GlobalMinCut.txt");`
225. `        Map<Integer, Integer> statistics = new LinkedHashMap<Integer, Integer>();`
226. `        int min = arr.length;`
227. `        int iter = arr.length * arr.length;`
228. `        Graph g = createGraph(arr);`
229. `        printGraph(g);`
230. `        for (int i = 0; i < iter; i++)`
231. `        {`
232. `            Graph gr = createGraph(arr);`
233. `            int currMin = minCut(gr);`
234. `            min = Math.min(min, currMin);`
235. `            Integer counter;`
236. `            if ((counter = statistics.get(currMin)) == null)`
237. `            {`
238. `                counter = 0;`
239. `            }`
240. `            statistics.put(currMin, counter + 1);`
241. `        }`
242. `        System.out.println("Min: " + min + " stat: "`
243. `                + (statistics.get(min) * 100 / iter) + "%");`
244. `    }`
245. ` `
246. `    private static void printGraph(Graph gr)`
247. `    {`
248. `        System.out.println("Printing graph");`
249. `        for (Vertex v : gr.vertices.values())`
250. `        {`
251. `            System.out.print(v.lbl + ":");`
252. `            for (Edge edge : v.edges)`
253. `            {`
254. `                System.out.print(" " + edge.getOppositeVertex(v).lbl);`
255. `            }`
256. `            System.out.println();`
257. `        }`
258. `    }`
259. `}`

Output:

```\$ javac GlobalMinCut.java
\$ java GlobalMinCut

Printing graph
0: 35 38 17 18 14 22
1: 35 8 17 3 25 22
2: 34 15 5 10
3: 23 1 17 22
4: 7 20 13 28
5: 2 33 15 34
6: 32 27 37 29
7: 13 11 30 4 28
8: 38 16 12 1 9 19
9: 28 8 11 13 19
10: 15 32 2 25 29
11: 19 13 7 9
12: 8 23 38 19
13: 11 7 9 4
14: 18 35 25 0
15: 34 31 2 10 29 16 5
16: 8 15 39 37 27 31
17: 0 38 23 1 3
18: 14 25 0 26
19: 11 12 8 9
20: 28 4 24 36
21: 31 33 39 34
22: 35 0 1 3
23: 3 17 12 38
24: 30 28 36 20
25: 26 18 14 10 1 30
26: 25 36 28 30 18
27: 31 6 37 16
28: 9 26 20 24 7 4
29: 36 15 32 6 10
30: 7 24 26 25 36
31: 15 21 27 39 16
32: 6 10 29 37
33: 21 5 39 34
34: 15 2 21 5 33
35: 0 1 14 22
36: 29 26 24 30 20
37: 39 16 6 27 32
38: 0 8 17 12 23
39: 37 31 21 16 33
Min: 3 stat: 6%```

Sanfoundry Global Education & Learning Series – 1000 Java Programs.