karger

import java.io.*;
import java.util.*;
import java.util.Map.Entry;

public class KragerMinCut {

  public static int lineCount = 1;
	public static int prevMinSize = 100;

	public static void main(String[] args) throws IOException {
	
		for(int cray=0; cray<100; cray++) {
			lineCount = 1;
			BufferedReader br;
			Map<Integer, List<Integer>> humanLike = new HashMap<Integer,List<Integer>>();
			
			try {
				String line;
				br = new BufferedReader(new FileReader("/Users/jsemko/Desktop/karger.txt"));
				
				while ((line = br.readLine()) != null) {
					
					//for every line we want to add all of the numbers to the first dimension of the array
					//for line 1 we will add list[i][cycle through j]
					String[] input = line.split("\\s+");
					
					//convert to Integer because I'm cool like that
					Integer[] ints = new Integer[input.length-1];
					
					//start at 1 so we don't grab the first number, that is taken care of
					//by the index of the array list.
					for(int i=1; i<input.length; i++) {
						ints[i-1] = Integer.parseInt(input[i]);
					}
					
					List<Integer> a = Arrays.asList(ints);
					List<Integer> b = new ArrayList<Integer>(a);
					
					humanLike.put(lineCount, b);
					lineCount++;
				}
				br.close();
				
			} catch (FileNotFoundException e) {}
			
			KragerMinCut krag = new KragerMinCut();
			
			int currentMinSize = krag.makeMeSomething(humanLike);
			if(currentMinSize < prevMinSize) {
				prevMinSize = currentMinSize;
			}
		}
		
		System.out.println("MIN SIZE: " + prevMinSize);
	}
	
	public int makeMeSomething(Map<Integer, List<Integer>> godlike) {
		//so now godlike has x amount of lines with y amount of #s associated with it		
		//Choose a random number >= length of array
		//When number is chosen select that index from the array (subtract 1?)
		//Get random number inside of index i
			
			Random r = new Random();
			
			//While array is larger than 2 (we are done when two points are left)
			while(godlike.size() > 2) {
				
				//Pick a random number, but start it off at -1 and cycle until a random number is found that 
				//matches a remaining index
				int i = -1;
				while(!godlike.containsKey(i)) {
					i = r.nextInt(lineCount);		
				}
				
				//cache the degrees for i
				//vDegrees is the size of the ith arrayList
				int vDegrees = godlike.get(i).size();
				
				//Get a random number between 0 and the size of i-1
				//we dont want i and j to equal the same (cannot pick same point)
				int j = i;
				while(i == j) {
					j = r.nextInt(vDegrees-1);
					j = godlike.get(i).get(j);
				}
			
				//find index j and add on all of the numbers from i
				for(int k = 0; k < vDegrees; k++) {
					int addMe = (int) godlike.get(i).get(k);
					godlike.get(j).add(addMe);
				}
				
				//remove i from the list
				godlike.remove(i);
				
				//replace all i with j everywhere
				for(Entry<Integer, List<Integer>> s : godlike.entrySet()) {
					for(int k=0; k<s.getValue().size(); k++) {
						if(s.getValue().get(k).equals(i)) {
							s.getValue().set(k, j);
						}
					}
				}				
				
				//remove all self loops
				for(Entry<Integer, List<Integer>> s : godlike.entrySet()) {
					int indexOfLoop = s.getKey();
					for(int k=0; k<s.getValue().size(); k++) {
						if(indexOfLoop == s.getValue().get(k)) {
							s.getValue().remove(k);
							k = k-1;
						}
					}
				}
			}
			
			//calculate the min size
			int size = 100;
			for(Entry<Integer, List<Integer>> s : godlike.entrySet()) {
				size = s.getValue().size();
			}
			return size;
		
		}
	}