import structure.*;
import java.util.Iterator;
import java.util.Collection;


/*

  graphTest.java
  Greg Nichols
  10/27/2004

  This will help test your graph class... it's not exhaustive,
  but if your class can pass these tests, then you can be sure
  most (if not all) of it works correctly.

*/



public class graphTest
{
    public graphTest()
    {
        MyAbstractGraph mg;

        Matrix testMatrix;
        Vector testVec;
        boolean testBool;


        // create whichever kind of graph class you're testing here
        mg = new MyMatrixGraph();


        // make sure there are no vertices yet
        if( mg.numberOfVertices() != 0 )
        {
            System.out.println( "Test #1 failed" );
            return;
        }


        // make sure there are no edges yet
        if( mg.numberOfEdges() != 0 )
        {
            System.out.println( "Test #2 failed" );
            return;
        }


        // add some vertices (some a few times)
        mg.addVertex( "Chicago" );
        mg.addVertex( "Buffalo" );
        mg.addVertex( "New York" );
        mg.addVertex( "Chicago" );
        mg.addVertex( "Atlanta" );
        mg.addVertex( "Houston" );
        mg.addVertex( "Chicago" );
        mg.addVertex( "Chicago" );
        mg.addVertex( "Denver" );
        mg.addVertex( "Buffalo" );
        mg.addVertex( "Atlanta" );


        // make sure the right number of vertices are there
        if( mg.numberOfVertices() != 6 )
        {
            System.out.println( "Test #3 failed" );
            return;
        }


        // make sure there are no edges yet
        if( mg.numberOfEdges() != 0 )
        {
            System.out.println( "Test #4 failed" );
            return;
        }


        // add a whole bunch of edges (some a few times)
        mg.addEdge( "Chicago", "New York" );
        mg.addEdge( "Chicago", "Houston" );
        mg.addEdge( "Denver", "Buffalo" );
        mg.addEdge( "Denver", "Buffalo" );
        mg.addEdge( "Denver", "New York" );
        mg.addEdge( "Denver", "Atlanta" );
        mg.addEdge( "Denver", "Houston" );
        mg.addEdge( "Houston", "Denver" );
        mg.addEdge( "Buffalo", "Denver" );
        mg.addEdge( "New York", "Chicago" );
        mg.addEdge( "Denver", "Houston" );
        mg.addEdge( "Buffalo", "New York" );
        mg.addEdge( "New York", "Buffalo" );
        mg.addEdge( "New York", "Chicago" );
        mg.addEdge( "Houston", "Atlanta" );
        mg.addEdge( "Denver", "Buffalo" );
        mg.addEdge( "Chicago", "New York" );
        mg.addEdge( "Chicago", "New York" );
        mg.addEdge( "Atlanta", "Houston" );
        mg.addEdge( "New York", "Chicago" );
        mg.addEdge( "Denver", "Houston" );
        mg.addEdge( "Houston", "Denver" );
        mg.addEdge( "Houston", "Denver" );
        mg.addEdge( "Denver", "Buffalo" );
        mg.addEdge( "Houston", "Atlanta" );
        mg.addEdge( "New York", "Denver" );
        mg.addEdge( "New York", "Atlanta" );
        mg.addEdge( "Buffalo", "Denver" );
        mg.addEdge( "Buffalo", "New York" );
        mg.addEdge( "New York", "Buffalo" );
        mg.addEdge( "Chicago", "New York" );
        mg.addEdge( "Atlanta", "New York" );
        mg.addEdge( "Atlanta", "Denver" );
        mg.addEdge( "Denver", "Buffalo" );
        mg.addEdge( "Chicago", "New York" );
        mg.addEdge( "Chicago", "New York" );
        mg.addEdge( "Atlanta", "Houston" );
        mg.addEdge( "Houston", "Denver" );
        mg.addEdge( "Houston", "Chicago" );
        mg.addEdge( "Houston", "Atlanta" );


        // make sure there are the right number of edges
        if( mg.numberOfEdges() != 9 )
        {
            System.out.println( "Test #5 failed" );
            return;
        }


        // try and connect a vertex that isn't there
        testBool = false;
        try
        {
            mg.addEdge( "Chicago", "Iowa City" );
        }
        catch( Throwable t )
        {
            testBool = true;   // an exception got thrown
        }
        if( !testBool )
        {
            System.out.println( "Test #6 failed" );
            return;
        }


        // same test, different direction
        testBool = false;
        try
        {
            mg.addEdge( "Iowa City", "Chicago" );
        }
        catch( Throwable t )
        {
            testBool = true;   // an exception got thrown
        }
        if( !testBool )
        {
            System.out.println( "Test #7 failed" );
            return;
        }


        // make sure that getVertices() returns all the vertices
        testVec = mg.getVertices();
        if( testVec.size() != 6 ||
            testVec.indexOf("Chicago") == -1 ||
            testVec.indexOf("Buffalo") == -1 ||
            testVec.indexOf("New York") == -1 ||
            testVec.indexOf("Houston") == -1 ||
            testVec.indexOf("Denver") == -1 ||
            testVec.indexOf("Atlanta") == -1 )
        {
            System.out.println( "Test #8 failed" );
            return;
        }
        

        // check to see if getNeighbors() validates its input
        testBool = false;
        try
        {
            testVec = mg.getNeighbors( "Iowa City" );
        }
        catch( Throwable t )
        {
            testBool = true;   // an exception got thrown
        }
        if( !testBool )
        {
            System.out.println( "Test #9 failed" );
            return;
        }


        // make sure that getNeighbors() returns all the correct stuff
        testVec = mg.getNeighbors( "New York" );
        if( testVec.size() != 4 ||
            testVec.indexOf("Chicago") == -1 ||
            testVec.indexOf("Buffalo") == -1 ||
            testVec.indexOf("Denver") == -1 ||
            testVec.indexOf("Atlanta") == -1 )
        {
            System.out.println( "Test #10 failed" );
            return;
        }


        // check to see if areNeighbors() validates its input
        testBool = false;
        try
        {
            mg.areNeighbors( "Denver", "Iowa City" );
        }
        catch( Throwable t )
        {
            testBool = true;   // an exception got thrown
        }
        if( !testBool )
        {
            System.out.println( "Test #11 failed" );
            return;
        }


        // check to see if areNeighbors() validates its input (other direction)
        testBool = false;
        try
        {
            mg.areNeighbors( "Iowa City", "Denver" );
        }
        catch( Throwable t )
        {
            testBool = true;   // an exception got thrown
        }
        if( !testBool )
        {
            System.out.println( "Test #12 failed" );
            return;
        }


        // spot check a few neighbors calls
        if( mg.areNeighbors( "Buffalo", "New York" ) == false ||
            mg.areNeighbors( "Houston", "Denver" ) == false ||
            mg.areNeighbors( "Chicago", "New York" ) == false ||
            mg.areNeighbors( "Chicago", "Atlanta" ) == true ||
            mg.areNeighbors( "Buffalo", "Houston" ) == true ||
            mg.areNeighbors( "Denver", "Chicago" ) == true )

        {
            System.out.println( "Test #13 failed" );
            return;
        }


        // check to see if deleteEdge() validates its input
        testBool = false;
        try
        {
            mg.deleteEdge( "Denver", "Iowa City" );
        }
        catch( Throwable t )
        {
            testBool = true;   // an exception got thrown
        }
        if( !testBool )
        {
            System.out.println( "Test #14 failed" );
            return;
        }


        // check to see if deleteEdge() validates its input (other direction)
        testBool = false;
        try
        {
            mg.deleteEdge( "Iowa City", "Denver" );
        }
        catch( Throwable t )
        {
            testBool = true;   // an exception got thrown
        }
        if( !testBool )
        {
            System.out.println( "Test #15 failed" );
            return;
        }


        // delete an edge...
        mg.deleteEdge( "Buffalo", "New York" );


        // make sure there are 8 edges left
        if( mg.numberOfEdges() != 8 )
        {
            System.out.println( "Test #16 failed" );
            return;
        }


        // they better not be neighbors now
        if( mg.areNeighbors( "Buffalo", "New York" ) == true )

        {
            System.out.println( "Test #17 failed" );
            return;
        }


        // check to see if deleteVertex() validates its input
        testBool = false;
        try
        {
            mg.deleteVertex( "Iowa City" );
        }
        catch( Throwable t )
        {
            testBool = true;   // an exception got thrown
        }
        if( !testBool )
        {
            System.out.println( "Test #18 failed" );
            return;
        }


        // delete Denver (didn't need it anyway!)
        mg.deleteVertex( "Denver" );


        // should only be 5 vertices left...
        if( mg.numberOfVertices() != 5 )

        {
            System.out.println( "Test #19 failed" );
            return;
        }


        // deleting Denver takes out 4 edges too... in addition to the one hosed above
        if( mg.numberOfEdges() != 9 - 4 - 1 )

        {
            System.out.println( "Test #20 failed" );
            return;
        }

        
        // make sure Denver's really gone
        testVec = mg.getVertices();
        if( testVec.indexOf("Denver") != -1 )
        {
            System.out.println( "Test #21 failed" );
            return;            
        }


        // Buffalo should have no neighbors now
        testVec = mg.getNeighbors( "Buffalo" );
        if( testVec.size() != 0 )
        {
            System.out.println( "Test #22 failed" );
            return;            
        }        


        // get rid of Chicago, and the NewYork/Atlanta edge
        mg.deleteVertex( "Chicago" );
        mg.deleteEdge( "New York", "Atlanta" );


        // should only be one edge left
        testMatrix = mg.getEdges();
        testBool = ((testMatrix.get(0,0) == "Houston") && (testMatrix.get(1,0) == "Atlanta")) ||
                   ((testMatrix.get(0,0) == "Atlanta") && (testMatrix.get(1,0) == "Houston"));
        if( testMatrix.height() != 2 || testMatrix.width() != 1 || !testBool )
        {
            System.out.println( "Test #23 failed" );
            return;            
        }        


        // Buffalo's the only one left...        
        mg.deleteVertex( "Houston" );
        mg.deleteVertex( "Atlanta" );
        mg.deleteVertex( "New York" );
        if( mg.numberOfVertices() != 1 )
        {
            System.out.println( "Test #24 failed" );
            return;            
        }        


        // and no edges left
        if( mg.numberOfEdges() != 0 )
        {
            System.out.println( "Test #25 failed" );
            return;            
        }        

        // all done!
        System.out.println( "all tests passed!" );
    }

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