import java.util.*;
import java.io.*;

/*
   Implementation of the Ladders program
   November 15, 2004
   Greg Nichols
   Modified by Sriram Pemmaraju. 2/3/2007
   Modified again by Sriram Pemmaraju. 9/15/2007
   Modified again by Sriram Pemmaraju. 9/23/2007
*/

public class KateLadders{

	// returns true if the words are different by only one letter
	public static boolean differentByOne( String a, String b )
	{
		int diffCount = 0;

		// make sure the two strings are both 5 letters long
		if( a.length() != 5 || b.length() != 5 )
			return false;

		// check the letters of the strings
		for( int i = 0; i < a.length(); i++ )
		{
			if( a.charAt(i) != b.charAt(i) )
			if( ++diffCount > 1 )
				return false;
		}

		return (diffCount == 1);
	}
	
	public int size2components(String[] wordlist){
		int count = 0;
		int tempcount = 0;
		
		for(int i = 0; i < wordlist.length; i++)
		{
			for(int j = 1; j < wordlist.length; j++){
				if(wordlist[i] == wordlist[j]){
					tempcount++;
				}
			}
			if(tempcount <= 0)
				count++;
		}
		return count;
	}
	
	public static void main(String args[])
	{
		String[] wordList;
		myGraph mg;

		mg = new myGraph();
		wordList = new String[5800];
		int counter = 0;
		
		try
		{
			// This is one way to read from a file. The list of all 5-letter words
			// is in a file called words.dat
			BufferedReader in = new BufferedReader(new FileReader("words.dat"));
			String word;

        		// read all the words from the file                
			System.out.println( "Reading words.dat..." );
			while( (word = in.readLine()) != null )
			{
				// make a new vertex w/ this word
				mg.addVertex( word );

				// see what words it's one letter different from
				for( int i = 0; i < counter; i++ )
					if( differentByOne(word, wordList[i]))
						mg.addEdge( word, wordList[i]);

				wordList[counter++] = word;
			}
			in.close();
		}
		catch (IOException e) {}

		System.out.println("Done constructing the graph....");

                // Finding a vertex of maximum degree and minimum degree
                int maxIndex, maxDegree, minIndex, minDegree;
                //int currentDegree;
                maxDegree = -1;
                minDegree = counter;
                maxIndex = minIndex = -1;
                /*for(int i = 0; i < counter; i++)
                {
                        currentDegree = mg.degree(wordList[i]);
                        if(currentDegree > maxDegree)
                        {
                                maxDegree = currentDegree;
                                maxIndex = i;
                        }

                        if(currentDegree < minDegree)
                        {
                                minDegree = currentDegree;
                                minIndex = i;
                        }
                }*/
		
				//Find how many size two components of the graph (1 degree) there are
				// Sriram: replaced "string" by "String" in several places
				// Sriram: replaced "bool" by "boolean"
				int pairs = 0;
				int oneDegreeCount = 0;
				int currentDegree, currentDegree2;
				
				
				for(int i = 0; i < counter; i++){
					String[] temp = new String[1];
					currentDegree = mg.degree(wordList[i]);
					if(currentDegree == 1){
						// Sriram: replaced i by wordList[i]
						temp = mg.getNeighbors(wordList[i]);
						
						currentDegree2 = mg.degree(temp[0]);
						if((currentDegree2 == 1)&&(wordList[i].compareTo(temp[0]) < 0)){
							System.out.println(wordList[i] + " " + temp[0]);
							oneDegreeCount++;
						}
						
					}
				}
				//Print out number of 2 component (1 degree) nodes
				System.out.println("There were " + oneDegreeCount + " of size two connected components.");
/*
				
				//Find how many size three components of the graph (2 degree) there are
				int count = 0;
				int curDegree, curDegree2;
				
				for(int j=0; j < counter; j++){
					boolean flag = true;
					int pairs2 = 0;
					
					
					
					String[] temp2 = new String[pairs2];
					
					//Find the degree of each string
					curDegree = mg.degree(wordList[j]);
					if(curDegree == 2){
						
						//look at first neighbor, check to see if it violates any conditions
						//of a size three component
						// Sriram: replaced j by wordList[j]
						temp2 = mg.getNeighbors(wordList[j]);
						
						int degree1 =mg.degree(temp2[0]);
						int degree2 =mg.degree(temp2[1]);
						
						if(degree1 < 1){
							flag = false;
						}
						else if(degree1 ==2){
							if(mg.getNeighbors[temp2[0]] != wordList[j] && +
									mg.getNeighbors[temp2[j]] != temp2[1]){
								flag = false;
							}
						}
							
						//look at the second neighbor, check to see if it violates any conditions
						//of a size three component
						if(degree2 < 1){
							flag = false;
						}
						else if(degree2 ==2){
							if(mg.getNeighbors[temp2[1]] != wordList[j] && +
									mg.getNeighbors[temp2[j]] != temp2[0]){
								flag = false;
							}
						}
						}
					//if flag is still true, it is a size three component	
					if(flag == true){
						count++;
					}
					
					}
				
				//Print out how many size three components there are
				System.out.println("There are " + count + " size three components.");
				
				
				
				//Starting here I get an array out of bounds error
                System.out.println("A word with maximum degree is " + wordList[maxIndex]);
                System.out.println("Its degree is " + maxDegree);
                System.out.println("Its neighbors are...");
                String[] neighbors = mg.getNeighbors(wordList[maxIndex]);
                for(int i = 0; i < neighbors.length; i++)
                        System.out.println(neighbors[i]);

                System.out.println("A word with minimum degree is " + wordList[minIndex]);
                System.out.println("Its degree is " + minDegree);
                if(minDegree > 0)
                {
                        System.out.println("Its neighbors are...");
                        neighbors = mg.getNeighbors(wordList[minIndex]);
                        for(int i = 0; i < neighbors.length; i++)
                                System.out.println(neighbors[i]);
                }

		System.out.println("The clustering coefficient of " + wordList[maxIndex] + " is " + mg.clusteringCoefficient(wordList[maxIndex]));		
		System.out.println("The clustering coefficient of " + wordList[minIndex] + " is " + mg.clusteringCoefficient(wordList[minIndex]));		
		System.out.println("The clustering coefficient of the graph is " + mg.clusteringCoefficient());	


		System.out.println("Printing isolated vertices...");
		int numIsolatedVertices = 0;
		for(int i = 0; i < mg.numberOfVertices(); i++)
			if(mg.degree(wordList[i]) == 0)
			{
				System.out.println(wordList[i]);
				numIsolatedVertices++;
			}

		System.out.println("The number of isolated vertices is " + numIsolatedVertices);
*/
	}

}