Karger’s algorithm for finding minimum graph cut

Karger’s algorithm is used for finding the minimum cut in a graph, i.e it cuts the graph into two halves such that the number of crossing edges across the two halves is minimum.

Karger Algorithm is given as:
1) Initialize contracted graph G as copy of original graph
2) While there are more than 2 vertices.
a) Pick a random edge (u, v) in the contracted graph.
b) Merge (or contract) u and v into a single vertex (update
the contracted graph).
c) Remove self-loops
3) Return cut represented by two vertices.

Question is:
The file contains the adjacency list representation of a simple undirected graph. There are 200 vertices labeled 1 to 200. The first column in the file represents the vertex label, and the particular row (other entries except the first column) tells all the vertices that the vertex is adjacent to. So for example, the 6th row looks like : “6 155 56 52 120 ……”. This just means that the vertex with label 6 is adjacent to (i.e., shares an edge with) the vertices with labels 155,56,52,120,……,etc

Your task is to code up and run the randomized contraction algorithm for the min cut problem and use it on the above graph to compute the min cut. (HINT: Note that you’ll have to figure out an implementation of edge contractions. Initially, you might want to do this naively, creating a new graph from the old every time there’s an edge contraction. But you should also think about more efficient implementations.) (Please make sure to run the algorithm many times with different random seeds, and remember the smallest cut that you ever find.) Write your numeric answer in the space provided. So e.g., if your answer is 5, just type 5 in the space provided.

Solution:

My rough work for MinCut

First how would you represent a node in the graph?
See Node.java below:


package kargerMinCut;

import java.util.ArrayList;

public class Node {

// node id can be a list of integers
// single node would have only one value in the ArrayList, combined nodes
// would have list of all combined node ids
ArrayList id = new ArrayList<>();

public Node() {
}

public Node(int singeNodeId) {
id.add(singeNodeId);
}

public Node(ArrayList nodes) {
id.addAll(nodes);
}

@Override
public String toString() {

return id.toString();
}

@Override
public boolean equals(Object other) {

if (!(other instanceof Node)) {
return false;
}
Node otherNode = (Node) other;
return this.id.equals(otherNode.id);
}

@Override
public int hashCode() {

int hashCode = 1;
hashCode = hashCode * 37 + this.id.hashCode();
return hashCode;
}

public ArrayList getId() {

return id;
}
}

Secondly, how would you represent a graph? We use Adjacency lists.
See Graph.java below:

package kargerMinCut;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;

import javax.naming.spi.DirStateFactory.Result;

public class Graph {

HashMap<Node, ArrayList> adjMap = new HashMap<Node, ArrayList>();

public Graph(HashMap<Node, ArrayList> adjMap) {
this.adjMap = adjMap;
}

public Graph() {
// TODO Auto-generated constructor stub
}

// Prints entire graph
@Override
public String toString() {

StringBuilder result = new StringBuilder();
for (Entry<Node, ArrayList> entry : adjMap.entrySet()) {
String pair = new String(entry.getKey().toString() + "=>" + entry.getValue().toString() + "\n");
result.append(pair);
}
return result.toString();
}

public void add(Graph secondGraph) {

this.adjMap.putAll(secondGraph.adjMap);
}
}

Main.java contains the main() java method:

package kargerMinCut;

import java.io.BufferedReader;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.HashMap;

public class Main {

public static void main(String[] args) {

// Below you can use a runtime argument instead of a hardcoded path
/*
* String path = args[0]; Path path = Paths.get(args[0]);
*/
String inputPath = "/home/ninad/workspace/java_personal/karger1.txt";
Path path = Paths.get(inputPath);
// HashMap contains Adjacency list mapping of each vertex to it's
// adjacent vertices
// Key Point: Parallel edges between vertices are denoted by duplicate
// node in the ArrayList
HashMap<Node, ArrayList> adjMap = new HashMap<Node, ArrayList>();
try {
BufferedReader reader = Files.newBufferedReader(path);
String line = null;
while ((line = reader.readLine()) != null) {
if (line.isEmpty() || line.trim().equals("") || line.trim().equals("\n")) {
continue;
}
String[] nodesInLine = line.split("\\s");
ArrayList adjacentNodes = new ArrayList();
for (int i = 1; i < nodesInLine.length; i++) { Node n = new Node(Integer.parseInt(nodesInLine[i])); adjacentNodes.add(n); } Node node = new Node(Integer.parseInt(nodesInLine[0])); adjMap.put(node, adjacentNodes); } } catch (IOException e) { e.printStackTrace(); } Graph graph = new Graph(adjMap); System.out.println("Input Graph is: " + "\n" + graph.toString()); int minCut = KargerMinCut.kargerMinCut(graph); System.out.println("Karger's minCut is: " + minCut); } } 

KargerMinCut.java computes the minCut with Karger’s algorithm given a graph:

 package kargerMinCut; import java.util.ArrayList; import java.util.Iterator; import java.util.Map; import java.util.Map.Entry; import java.util.Random; public class KargerMinCut { /* * Karger Algorithm: * 1) Initialize contracted graph G as copy of original * graph * 2) While there are more than 2 vertices. * a) Pick a random edge (u,v) in the contracted graph. * b) Merge (or contract) u and v into a single vertex (update the contracted graph). * c) Remove self-loops * 3) Return cut represented by two vertices. */ public static int kargerMinCut(Graph graph) { while (getNumOfVertices(graph) > 2) {
/*
* To pick a random edge, we will pick a random key i.e vertex and
* then iterate over the value and pick a random node So our
* (vertex,node) will be the random edge selected
*/
Node[] randomEdge = getRandomEdge(graph);
// System.out.println("Random Edge is: " + randomEdge[0].toString()
// + ", " + randomEdge[1].toString());
contract(graph, randomEdge);
removeSelfLoops(graph);
// System.out.println("Contracted graph is: " + "\n" +
// graph.toString());
}
return minCut(graph);
}

public static int minCut(Graph graph) {

// Means graph already has less than two vertices, number of adjacent
// nodes is equal to minCut
Map.Entry<Node, ArrayList> entry = graph.adjMap.entrySet().iterator().next();
// Now find number of values in entry
return entry.getValue().size();
}

public static Node[] getRandomEdge(Graph graph) {

Node[] edge = new Node[2];
Random rand = new Random();
int randomIndex = rand.nextInt(graph.adjMap.keySet().size());
int i = 0;
// **iterate over the graph keys(vertices) until i == randomIndex**
for (Node n : graph.adjMap.keySet()) {
if (i == randomIndex) {
edge[0] = n;
}
i++;
}
ArrayList rndNodeValues = graph.adjMap.get(edge[0]);
int randomIndex2 = rand.nextInt(rndNodeValues.size());
edge[1] = rndNodeValues.get(randomIndex2);
return edge;
}

public static void contract(Graph graph, Node[] edge) {

ArrayList startVertexAdjList = new ArrayList(graph.adjMap.get(edge[0]));
ArrayList endVertexAdjList = new ArrayList(graph.adjMap.get(edge[1]));
// For contraction: Remove edge[1] from startVertexAdjList and edge[0]
// from endVertexAdjList and take union of remaining values
ArrayList startVertexAdjListMod = removeVertex(startVertexAdjList, edge[1]);
ArrayList endVertexAdjListMod = removeVertex(endVertexAdjList, edge[0]);
// merge above two modified lists into one super list
ArrayList mergedAdjList = new ArrayList();
mergedAdjList.addAll(startVertexAdjListMod);
mergedAdjList.addAll(endVertexAdjListMod);
ArrayList superNodeList = new ArrayList();
superNodeList.addAll(edge[0].getId());
superNodeList.addAll(edge[1].getId());
Node superNode = new Node(superNodeList);
// remove original edge vertices and add superNode
graph.adjMap.remove(edge[0]);
graph.adjMap.remove(edge[1]);
graph.adjMap.put(superNode, mergedAdjList);
// the superNode needs to replace each occurrence of original nodes in
// the graph
replaceWithSuperNode(graph, edge, superNode);
}

public static void replaceWithSuperNode(Graph graph, Node[] edge, Node superNode) {

// Replace all occurrences of original two edge nodes with superNode
Iterator<Map.Entry<Node, ArrayList>> iter = graph.adjMap.entrySet().iterator();
Graph newGraph = new Graph();
while (iter.hasNext()) {
Map.Entry<Node, ArrayList> entry = iter.next();
// Find edge nodes in the graph's values and replace them with
// superNode
Node key = entry.getKey();
ArrayList nodeValues = entry.getValue();
// while condition returns true if the list nodeValues was modified,
// if true, add the superNode each time an edge point is removed
while (nodeValues.remove(edge[0])) {
nodeValues.add(superNode);
}
while (nodeValues.remove(edge[1])) {
nodeValues.add(superNode);
}
iter.remove();
// put back the same key but with the modified values containing
// supernode in newGraph
newGraph.adjMap.put(key, nodeValues);
}
// Add newGraph i.e modified graph back to the original graph
graph.add(newGraph);
}

public static void removeSelfLoops(Graph graph) {

// If key is same as value then it is self loop
for (Entry<Node, ArrayList> entry : graph.adjMap.entrySet()) {
Node key = entry.getKey();
ArrayList value = entry.getValue();
if (value.contains(key) && value.size() == 1) {
graph.adjMap.remove(key);
}
}
}

public static ArrayList removeVertex(ArrayList nodeList, Node deleteNode) {

ArrayList modifiednodeList = new ArrayList();
for (Node n : nodeList) {
if (!(n.equals(deleteNode))) {
modifiednodeList.add(n);
}
}
return modifiednodeList;
}

public static int getNumOfVertices(Graph g) {

// number of vertices = total number of keys in G
return g.adjMap.size();
}
}

Make sure to run the algorithm multiple times to get the correct number of minimum cuts.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s