java - Issues in Implementing Karger's Min Cut Algorithm using Union-Find -

i've implemented karger's algorithm using union-find datastructure using path-compression heuristics , union rank i've run couple of issues

what i've done is, run algorithm nnlog(n) time estimate of answer. however, don't answer mincut. pick random edge each time has 2 members source 's' , destination 'd'. if parents not equal, merge them , reduce count of vertices, 'vcnt' equal original number of vertices. process continues until number of vertices left 2. finally, find parent of source , destination of each edge , if ont equal, increase mincut count. repeats nnlog(n) times.

i've tried running code lot of test data don't seem getting mincut value, large data.

could me out? also, performance improvement suggestions welcome. here code:

import java.io.bufferedreader; import java.io.fileinputstream; import java.io.ioexception; import java.io.inputstreamreader; import java.util.arraylist;  class kragersmincut {     static int n=200;//number of vertices     static int[] u=new int[n];     static int[]rank =new int[n];      static class edge //edge hols source , destination     {         int s,d;//source,destination         edge(int s,int d)         {             this.s=s;             this.d=d;         }     }      private static void initializeunionfinddata()     {         for(int i=0;i<n;i++)         {             u[i]=i;             rank[i]=1;         }     }      private static int find(int xx) //finding parent using path-compression heuristics     {         if(u[xx]!=u[u[xx]])         {             u[xx]=find(u[xx]);         }         return u[xx];     }      private static boolean union(int x,int y) //union order-by-rank create evenly balanced search trees     {     int px=find(x),py=find(y);     if(rank[px]>rank[py])     {         int temp=px;         px=py;         py=temp;     }     else if(rank[px]==rank[py])         rank[py]++;      u[px]=py;     return true;     }       public static void main(string[] args) throws ioexception     {         bufferedreader br=new bufferedreader(new inputstreamreader(system.in));         arraylist<edge> edgelist=new arraylist<edge>();         for(int i=0;i<n;i++)         {             string x=br.readline();             arraylist<integer>al=new arraylist<integer>();             for(int j=0;j<x.length();j++) //this loop parsing input format             {                 if(x.charat(j)<48 || x.charat(j)>57)                     continue;                  int p=j;                 string input="";                 while(p!=x.length()&&(x.charat(p)>=48 && x.charat(p)<=57))                 {                     input+=(x.charat(p));                     p++;                 }                 j=p;                 al.add(integer.parseint(input.trim())-1);             }             for(int j=1;j<al.size();j++)             {                 edgelist.add(new edge(al.get(0),al.get(j)));//source,destination             }         }         //edge list ready         int mincut=integer.max_value;         for(int q=0;q<(n*n)*math.log(n);q++)//running theta(n^2*ln(n)) times estimate. runs in 20 secs         {             int vcnt=n;//essentially n             initializeunionfinddata();             while(vcnt>2)             {                 edge x=edgelist.get((int)(math.random()*(edgelist.size()-1)+1));//obtaining random valued element @ index edgelist                 int s=x.s,d=x.d;                 int ps=find(s),pd=find(d);                 if(ps!=pd)//contracting. making parents equal                 {                     union(s,d);                     vcnt--;                 }             }             int currmincutvalue=0;             for(edge i:edgelist)             {                 int px=find(i.s),py=find(i.d);                 if(px!=py)//since belong different vertices                 {                     currmincutvalue++;                 }             }             mincut=math.min(mincut,currmincutvalue);//finding minimum cut of random runs         }         system.out.println(mincut);     } }     

testdata: (source vertex-> connected vertices)

1 2 3 4 7

2 1 3 4

3 1 2 4

4 1 2 3 5

5 4 6 7 8

6 5 7 8

7 1 5 6 8

8 5 6 7

answer: 4 | expected answer: 2

link: http://ideone.com/qp62fn

thanks

the algorithm suggests every edge equally selected merging.

but code never selects edge @ index 0.

so modify line:

edge x=edgelist.get((int)(math.random()*(edgelist.size()-1)+1)); 

to this:

edge x=edgelist.get((int)(math.random()*(edgelist.size()))); 

also because every edge listed twice in edge list:

you should print following

system.out.println(mincut/2); 

now should work.