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 Ladders{

	// 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 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, 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;
                        }


                }


                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);
	}

}