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
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
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.