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

	// 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....");
		
		// Put vertices of degree 1 and vertices of degree 2 in two separate arrays
		int countDegree2 = 0;
		int countDegree1 = 0;

		// Array for vertices of degree 2
		String[] degree2Words = new String[mg.numberOfVertices()];

		// Array for vertices of degree 1
		String[] degree1Words = new String[mg.numberOfVertices()];

		// Scan all words and pick up those with degree 1 and those with degree 2
		for(int i = 0; i < mg.numberOfVertices(); i++)
		{
			if(mg.degree(wordList[i]) == 2)
				degree2Words[countDegree2++] = wordList[i];

			if(mg.degree(wordList[i]) == 1)
				degree1Words[countDegree1++] = wordList[i];
		}


		System.out.println("The number vertices of degree one is " + countDegree1);
		System.out.println("The number vertices of degree two is " + countDegree2);

		// Find all size-2 connected components
                int count2CC = 0;
                for(int i = 0; i < countDegree1; i++)
		{
			String a = mg.getNeighbors(degree1Words[i])[0];

			if((mg.degree(a) == 1) && (degree1Words[i].compareTo(a) < 0))
                       	{
                       		System.out.println("Size 2 CC "+ degree1Words[i] + " " + a);
                       		count2CC++;
                       	}
		}

                System.out.println("The number of size-2 connected components is " + count2CC);

		// Find all paths and triangles
                int countPaths = 0;
		int countTriangles = 0;

		// Find all paths and triangles
		for(int i = 0; i < countDegree2; i++)
		{
			String[] nbrsI = mg.getNeighbors(degree2Words[i]);
			String a = nbrsI[0];
			String b = nbrsI[1];

			// This condition tests to see if the neighbors are both degree 1 vertices
			// If so we have found a size-3 connected component that is a path
			// The comparison between a and b is to avoid double counting
			if((mg.degree(a) == 1) && (mg.degree(b) == 1) && (a.compareTo(b) < 0))
			{
				System.out.println("Size 3 CC: path " + degree2Words[i] + " " + a + " " + b);
				countPaths++;
			}

			// This condition tests to see if the two neighbors are both degree 2 vertices and there is an edge between them
			// Again, the string comparisons are to avoid overcounting
			if((mg.degree(a) == 2) && (mg.degree(b) == 2) && (mg.isEdge(a, b)) && (degree2Words[i].compareTo(a) < 0) && (degree2Words[i].compareTo(b) < 0))
			{
				System.out.println("Size 3 CC: triangle " + degree2Words[i] + " " + a + " " + b);
				countTriangles++;
			}
		}
			

                System.out.println("The number of paths is " + countPaths);
		System.out.println("The number of triangles is " + countTriangles);

	}

}