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

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

public class LaddersCC{

	// returns true if the words are different by only one letter
	public 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 LaddersCC()
	{
		String[] wordList;
		myGenericListGraph<String> mg;

		mg = new  myGenericListGraph<String>();
		wordList = new String[5800];
		int counter = 0;
		String word = "";
		
		
		try
		{
			BufferedReader in = new BufferedReader(new FileReader("words.dat"));

        	// 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....");
		System.out.println("Type the word whose clustering coefficient you want to know.");
		try
		{
			BufferedReader stdin = new BufferedReader( new InputStreamReader( System.in ) );
			word = stdin.readLine();
		}
		catch (IOException e) {}
		System.out.println("The clustering coefficient of this word is " + mg.clusteringCoefficient(word));

		System.out.println("Here is an explanation...");
		GenericLinkList<String> neighbors = mg.getNeighbors(word);
		System.out.println("The neighbors of this word are:");
		neighbors.displayList();
		int size = neighbors.size();
		System.out.println("These make up " + size*(size - 1)/2 + " pairs.");

		// Copy the neighbors list into an array
		String[] neighborsArray = new String[size];
		for(int i = 0; i < size; i++)
			neighborsArray[i] = neighbors.deleteFirst();

		// Scan the array to look for pairs of neighbors connected by an edge
		int edges = 0;
		System.out.println("Of these, the following pairs are connected by edges:");
		for(int i = 0; i < size; i++)
			for(int j = 0; j < i; j++)
				if(mg.isEdge(neighborsArray[i], neighborsArray[j]))
				{
					edges++;
					System.out.println(neighborsArray[i] + " " + neighborsArray[j]);
				}
		System.out.println("So a total of " + edges + " pairs are connected by edges.");
		System.out.println("You can verify that " + edges + "/" + size*(size - 1)/2 + " equals the clustering coefficient.");

		
		System.out.println("By the way, the clustering coefficient of the entire graph is " + mg.clusteringCoefficient());
		
	}

	public static void main(String args[])
	{
		new LaddersCC();	
	}

}