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
   Modified again by Sriram Pemmaraju on 10/11/2007
   to test the the connectedComponents function in myListGraph.java
*/

public class allConnectedComponents{

	// 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;
		myListGraph mg;

		mg = new myListGraph();
		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....");
		
		String[][] cc = mg.connectedComponents();
		System.out.println("There are " + cc.length + " connected components.");
		for(int i = 0; i < cc.length; i++)
		{
			System.out.println("Connected component " + (i+1) + " Size = " + cc[i].length);
			for(int j = 0; j < cc[i].length; j++)
				System.out.println(cc[i][j]);
		}

	}

}