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.

advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
I’m Manish - Founder and CTO at Sanfoundry. I’ve been working in tech for over 25 years, with deep focus on Linux kernel, SAN technologies, Advanced C, Full Stack and Scalable website designs.

You can connect with me on LinkedIn, watch my Youtube Masterclasses, or join my Telegram tech discussions.

If you’re in your 40s–60s and exploring new directions in your career, I also offer mentoring. Learn more here.