Minimum Cut by Karger MinCut Java Large Input Error

StackOverflow https://stackoverflow.com/questions/18924438

Question

I have been working & trying to fix this for a while now. It has been quite a few weeks actually but I ran out of possible solutions or modifications. So the algorithm is a Randomized Karger Minimum Cut Algorithm & my implementation is provided below:

Algorithm:

It is for undirected graph. Each vertex is stored as a key in hashmap & its adjacent vertices are stored as arraylist in values of hashmap so for e.g.

if the test case is:

1   2   6
2   1   3   4   5
3   2   4
4   2   3   5
5   2   4   6
6   1   5

where first column is keys & the numbers adjacent to them are its values (arraylist).

my algorithm is

  1. Pick a first occurring vertex called "i" having more than 2 adjacent vertices (2 in this case)
  2. While there are more than two numbers in "i"'s list
  3. Choose randomly an adjacent vertex which is called "U"
  4. Merge "U" with "i" (merging it with another vertex called "V" does not give correct answer)
  5. Now check if new "i"'s list consist of "i" itself & remove it. (Self Loop)
  6. Cross reference new "i"'s list to other vertices

  7. Remove "U" (key) for e.g if "U" was 6 the updated vertices would look like this:

    1   2   6   2
2   1   3   4   5   1   5
3   2   4
4   2   3   5
5   2   4   6   2

  8. Hence when "i" will have an unique number the algorithm will terminate (done by adding "i"'s list to Set). For e.g:

    2   6   6

6   2   2

So that is 2 minimum cuts for the given graph.

Code:

My code for above mentioned algorithm in java as follows:

package practice;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public class MinCut {
static Map <Integer,ArrayList <Integer>> vertices=new HashMap <Integer,ArrayList <Integer>>() ;
static Random random= new Random ();
static int SIZE=0;
static TreeSet <Integer> minSize= new TreeSet <Integer> ();
static int reps=0;
static ArrayList <Integer> uTracker= new ArrayList <Integer> ();
public static void main(String[] args) {

    int reps2=0;
    for (int i=0;i<=10;i++){
        minCutCalc();
        TreeSet <Integer> trackSet= new TreeSet <Integer> ();
        if (!uTracker.isEmpty()){
            Collections.sort(uTracker);
            for (int o=0;o<uTracker.size();o++){
                System.out.println("uTracker: "+uTracker.get(o));
                if (!trackSet.add(uTracker.get(o))){
                    reps2++;
                }
            }
            //to check "U"s in every run
            uTracker.clear();
        }
    }

    //prints the lowest number in the set hence the minimum cut
    System.out.println("The attempted minimum cut is: "+minSize.first());
    System.out.println("FINAL REPS: "+reps2);

}
private static void minCutCalc() {

    readMap();
    int i=0;

    i=selectVertex(1);

    //for testing purposes
    System.out.println(" \"i\" is: "+i);

    if (vertices.get(i) != null){
        Set <Integer> tempSet= new LinkedHashSet <Integer> ();


        while (vertices.get(i).size()>2){
            /*to remove any instances of "i" copied into list from other vertices
             * to avoid getting "i" selected as "U" in random numbers as then "U"
             * will be deleted hence showing result as "null"
             */
            for (int l=0;l<vertices.get(i).size();l++){
                for (int c=0;c<vertices.get(i).size();c++){
                    if (vertices.get(i).get(c)==i){
                        int index=vertices.get(i).indexOf(i);
                        System.out.println("Yes it contains "+i+": "+vertices.get(i).get(index));
                        vertices.get(i).remove(index);
                    }
                }

            }

            //for testing purposes
            System.out.println("\"i\" is: "+i);
            for (int j=0;j<vertices.get(i).size();j++){
                System.out.println("\n"+"LIST DISPLAY: "+vertices.get(i).get(j));
            }

            if (!tempSet.isEmpty()){
                tempSet.clear();
            }
            tempSet.addAll(vertices.get(i));

            //if there is only one occurrence of a number in the list
            if (tempSet.size()==1){
                break;
            }

            int U=selectRandom(i,vertices);

            //for testing purposes
            System.out.println("PRINT u: "+U);
            //to check if unique "U"s are selected each time
            uTracker.add(U);
            for (int n=0;n<vertices.get(U).size();n++){
                System.out.println("\"U\" List: "+vertices.get(U).get(n));
            }

            //merging "U"'s vertices to "i"
            if (vertices.containsKey(U)){
                vertices.get(i).addAll(vertices.get(U));
                for (int y=0;y<vertices.get(U).size();y++){
                    System.out.println(vertices.get(U).get(y));

                    //cross referencing "i" to rest of the vertices in "U"'s list
                    if (vertices.get(U).get(y)!=i){
                        vertices.get(vertices.get(U).get(y)).add(i);
                    }

                }
            }

            vertices.remove(U);

            //if any of the vertices consists of "U" as its edge it will be deleted
            for (int t=1;t<=SIZE;t++){
                if (vertices.containsKey(t)){
                    for (int y=0;y<vertices.get(t).size();y++){
                        for (int z=0;z<vertices.get(t).size();z++){
                            if (vertices.get(t).get(z)==U){
                                int index=vertices.get(t).indexOf(U);
                                vertices.get(t).remove(index);
                            }

                        }
                    }
                }
            }

            //for testing purposes
            System.out.println("\"i\" is: "+i);
            for (int j=0;j<vertices.get(i).size();j++){
                System.out.println("LIST \"AFTER\" DISPLAY: "+vertices.get(i).get(j));
            }

            //null check
            if (vertices.get(i)==null){
                System.out.println("This is null: "+i);
                break;
            }
        }
    }

    //to check the final result
    for (int o=1;o<=SIZE;o++){
        System.out.println(" SHOW at "+o+" index: "+vertices.get(o));
        if (vertices.get(o)!=null){
            //minimum cuts (size of current list) are added to a set
            minSize.add(vertices.get(o).size());
        }
    }

    System.out.println("Total Number of Repititions: "+reps);
}

private static void readMap() {
    try {
        FileReader file= new FileReader("C:\\xyz\\Desktop\\testMinCut.txt");
        BufferedReader reader= new BufferedReader(file);
        String line="";

        while ((line=reader.readLine())!=null){
            String [] lineArr;
            lineArr=line.split("\t");

            int vert1=Integer.parseInt(lineArr[0]);

            vertices.put(vert1,new ArrayList <Integer> ());

            for (int p=1;p<lineArr.length;p++){
                int vert2=Integer.parseInt(lineArr[p]);
                vertices.get(vert1).add(vert2);
            }
        }
        SIZE=vertices.size();
    } catch (FileNotFoundException e) {
        System.err.println(e.toString());
    } catch (IOException e) {
        System.err.println(e.toString());
    }

}
private static int selectVertex(int i) {
    LinkedHashSet <Integer> storer= new LinkedHashSet <Integer> ();

    for (int s=1;s<=SIZE;s++){
        if (vertices.get(s)!=null){
            if (!storer.isEmpty()){
                storer.clear();
            }
            storer.addAll(vertices.get(s));
            if (storer.size()>2){
                i=s;
                break;
            }
            else {
                i=0;
            }
        }

    }

    return i;
}

private static int selectRandom(int i, Map<Integer, ArrayList<Integer>> vertices) {

    int u;
    int U = 0;

    LinkedHashSet <Integer> tempSet2= new LinkedHashSet <Integer> ();
    tempSet2.addAll(vertices.get(i));

    u=random.nextInt(tempSet2.size());

    Set <Integer> uSet=new HashSet <Integer> ();
    Set <Integer> uSet2=new HashSet <Integer> ();

    //to reassure unique "u" is selected each time
    if (!uSet.isEmpty() && uSet.contains(u)){
        u=random.nextInt(tempSet2.size());
        reps++;
    }

    uSet.add(u);

    U=vertices.get(i).get(u);
    //ensuring unique "U" is selected
    if (uSet2.contains(U)){
        u=random.nextInt(tempSet2.size());
        U=vertices.get(i).get(u);
        reps++;
    }

    uSet2.add(U);

    tempSet2.clear();

    return U;
}

}

Problem:

The problem I am facing is that this algorithm works perfectly fine for almost all the test cases I came across except for one very large test case consisting of 200 vertices. The correct answer should be 17 however I keep on getting my answer as "20". I kept track of all the "U"s selected. Apparently they are all unique without any repetitions & I keep getting the answer "20". Any advice please? Thanks once again. The link to test case is:

http://spark-public.s3.amazonaws.com/algo1/programming_prob/kargerMinCut.txt

N.B:

This is not a homework it is rather a practice question which I am working on which I saw in an online course (Algorithm Design and Analysis) at coursera. The course is over now. Thank you very much in advance. I am asking this question again as I could not get an answer the first time. I would appreciate any help offered as I said this question is taking a toll on me since I have been working on it for quite some time.

Was it helpful?

Solution

So I managed to make it work & get the correct answer. The problem was in random edge selection. Since I was first selecting a vertex (which had more than 2 edges) & then an edge from that vertex which was the wrong approach since not all edges are distributed evenly among vertices. So here is my improved algorithm:

Keep a list for all the edges in a Set

  1. While are there more than 2 edges left in the edges list
  2. Pick a random edge from the edges list & call it V
  3. Then pick another random edge from V's (since my implementation is a HashMap so get values which is an arraylist for key value, "V") list & call it "U"
  4. Combine U & V to make a combined edge
  5. Remove U from the edges list (since I combined U's list meaning its edges to V therefore combined edge was just V, so after merging U & V became a super edge called just "V")

Hopefully that would be helpful to someone.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top