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.
package com.maixuanviet.graph; import java.io.BufferedReader; import java.io.FileReader; import java.util.ArrayList; import java.util.Comparator; import java.util.HashSet; import java.util.Iterator; import java.util.LinkedHashMap; import java.util.List; import java.util.Map; import java.util.Random; import java.util.Set; import java.util.TreeMap; public class GlobalMinCut { private static class Graph { private final Map<Integer, Vertex> vertices = new TreeMap<Integer, Vertex>( new Comparator<Integer>() { @Override public int compare(Integer arg0, Integer arg1) { return arg0.compareTo(arg1); } }); private final List<Edge> edges = new ArrayList<Edge>(); public void addVertex(Vertex v) { vertices.put(v.lbl, v); } public Vertex getVertex(int lbl) { Vertex v; if ((v = vertices.get(lbl)) == null) { v = new Vertex(lbl); addVertex(v); } return v; } } private static class Vertex { private final int lbl; private final Set<Edge> edges = new HashSet<Edge>(); public Vertex(int lbl) { this.lbl = lbl; } public void addEdge(Edge edge) { edges.add(edge); } public Edge getEdgeTo(Vertex v2) { for (Edge edge : edges) { if (edge.contains(this, v2)) return edge; } return null; } } private static class Edge { private final List<Vertex> ends = new ArrayList<Vertex>(); public Edge(Vertex fst, Vertex snd) { if (fst == null || snd == null) { throw new IllegalArgumentException("Both vertices are required"); } ends.add(fst); ends.add(snd); } public boolean contains(Vertex v1, Vertex v2) { return ends.contains(v1) && ends.contains(v2); } public Vertex getOppositeVertex(Vertex v) { if (!ends.contains(v)) { throw new IllegalArgumentException("Vertex " + v.lbl); } return ends.get(1 - ends.indexOf(v)); } public void replaceVertex(Vertex oldV, Vertex newV) { if (!ends.contains(oldV)) { throw new IllegalArgumentException("Vertex " + oldV.lbl); } ends.remove(oldV); ends.add(newV); } } public static int minCut(Graph gr) { Random rnd = new Random(); while (gr.vertices.size() > 2) { Edge edge = gr.edges.remove(rnd.nextInt(gr.edges.size())); Vertex v1 = cleanVertex(gr, edge.ends.get(0), edge); Vertex v2 = cleanVertex(gr, edge.ends.get(1), edge); // contract Vertex mergedVertex = new Vertex(v1.lbl); redirectEdges(gr, v1, mergedVertex); redirectEdges(gr, v2, mergedVertex); gr.addVertex(mergedVertex); } return gr.edges.size(); } private static Vertex cleanVertex(Graph gr, Vertex v, Edge e) { gr.vertices.remove(v.lbl); v.edges.remove(e); return v; } private static void redirectEdges(Graph gr, Vertex fromV, Vertex toV) { for (Iterator<Edge> it = fromV.edges.iterator(); it.hasNext();) { Edge edge = it.next(); it.remove(); if (edge.getOppositeVertex(fromV) == toV) { // remove self-loop toV.edges.remove(edge); gr.edges.remove(edge); } else { edge.replaceVertex(fromV, toV); toV.addEdge(edge); } } } public static int[][] getArray(String relPath) { Map<Integer, List<Integer>> vertices = new LinkedHashMap<Integer, List<Integer>>(); FileReader fr; try { fr = new FileReader(relPath); BufferedReader br = new BufferedReader(fr); String line; while ((line = br.readLine()) != null) { String[] split = line.trim().split("(\\s)+"); List<Integer> adjList = new ArrayList<Integer>(); for (int i = 1; i < split.length; i++) { adjList.add(Integer.parseInt(split[i]) - 1); } vertices.put(Integer.parseInt(split[0]) - 1, adjList); } fr.close(); } catch (Exception e) { e.printStackTrace(); } int[][] array = new int[vertices.size()][]; for (Map.Entry<Integer, List<Integer>> entry : vertices.entrySet()) { List<Integer> adjList = entry.getValue(); int[] adj = new int[adjList.size()]; for (int i = 0; i < adj.length; i++) { adj[i] = adjList.get(i); } array[entry.getKey()] = adj; } return array; } private static Graph createGraph(int[][] array) { Graph gr = new Graph(); for (int i = 0; i < array.length; i++) { Vertex v = gr.getVertex(i); for (int edgeTo : array[i]) { Vertex v2 = gr.getVertex(edgeTo); Edge e; if ((e = v2.getEdgeTo(v)) == null) { e = new Edge(v, v2); gr.edges.add(e); v.addEdge(e); v2.addEdge(e); } } } return gr; } /** * @param args */ public static void main(String[] args) { int[][] arr = getArray("GlobalMinCut.txt"); Map<Integer, Integer> statistics = new LinkedHashMap<Integer, Integer>(); int min = arr.length; int iter = arr.length * arr.length; Graph g = createGraph(arr); printGraph(g); for (int i = 0; i < iter; i++) { Graph gr = createGraph(arr); int currMin = minCut(gr); min = Math.min(min, currMin); Integer counter; if ((counter = statistics.get(currMin)) == null) { counter = 0; } statistics.put(currMin, counter + 1); } System.out.println("Min: " + min + " stat: " + (statistics.get(min) * 100 / iter) + "%"); } private static void printGraph(Graph gr) { System.out.println("Printing graph"); for (Vertex v : gr.vertices.values()) { System.out.print(v.lbl + ":"); for (Edge edge : v.edges) { System.out.print(" " + edge.getOppositeVertex(v).lbl); } System.out.println(); } } }
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%
Related posts:
Java – InputStream to Reader
ExecutorService – Waiting for Threads to Finish
Logging a Reactive Sequence
Introduction to Spring Cloud OpenFeign
Java Program to Implement Stack API
Dockerizing a Spring Boot Application
Spring Boot Application as a Service
Java Program to Emulate N Dice Roller
Java – Try with Resources
Setting a Request Timeout for a Spring REST API
Guide to the Java TransferQueue
Logout in an OAuth Secured Application
Sending Emails with Java
Java Program to Implement Sparse Array
Multipart Upload with HttpClient 4
Filtering a Stream of Optionals in Java
Spring Security 5 – OAuth2 Login
Java Program to Perform Stooge Sort
Guide to Guava Table
Consumer trong Java 8
Jackson – Marshall String to JsonNode
Deploy a Spring Boot App to Azure
Java Program to Find SSSP (Single Source Shortest Path) in DAG (Directed Acyclic Graphs)
Câu lệnh điều khiển vòng lặp trong Java (break, continue)
Java Program to Implement Hash Tables Chaining with Binary Trees
JPA/Hibernate Persistence Context
Java Program to Implement Range Tree
Java Program to Compute Discrete Fourier Transform Using Naive Approach
Xây dựng ứng dụng Client-Server với Socket trong Java
Java 8 Streams peek() API
Converting a List to String in Java
Java Web Services – Jersey JAX-RS – REST và sử dụng REST API testing tools với Postman