import net.datastructures.DFS;
import net.datastructures.FindPathDFS;
import net.datastructures.FindCycleDFS;
import net.datastructures.ConnectivityDFS;
import net.datastructures.Graph;
import net.datastructures.AdjacencyListGraph;
import net.datastructures.Vertex;
import net.datastructures.Edge;
import net.datastructures.DecorablePosition;
import net.datastructures.Vector;
import net.datastructures.ArrayVector;
import java.util.Iterator;

/*
 * This class is an example of how to use the various applications of
 * the depth-first search algorithm provided by the net.datastructures
 * Package.  During the initialization procedure, a bunch of vertices
 * and edges are inserted into an adjacency-list graph at random.
 * Next, the three applications of DFS are executed.  Finally, the
 * results are printed.
 */

public class DFSExample {

  public static void main(String[] args) {
    
    /* INITIALIZATION */

    // the algorithm objects
    DFS findPath = new FindPathDFS();
    DFS findCycle = new FindCycleDFS();
    DFS connectivity = new ConnectivityDFS();

    // the input graph
    Graph g = new AdjacencyListGraph();

    // vector to keep track of vertices
    Vector vertices = new ArrayVector();

    // insert vertices into the graph
    int num = 20;
    for(int i = 0; i < num-2; i++) {
      Vertex vert = g.insertVertex(new Integer(i));
      vertices.insertAtRank(0,vert);
    }

    // the source vertex
    Vertex source = g.insertVertex(new Integer(num-2));
    vertices.insertAtRank(num-2,source);

    // the sink vertex (for FindPathDFS)
    Vertex sink = g.insertVertex(new Integer(num-1));
    vertices.insertAtRank(num-1,sink);

    // insert edges into the graph
    int num2 = 50;
    for(int i = 0; i < num2; i++) {

      // pick two random vertices
      Vertex u, v;
      int r, s;
      r = randomNumber(num-1,0);
      s = randomNumber(num-1,0);
      u = (Vertex)vertices.elemAtRank(r);
      v = (Vertex)vertices.elemAtRank(s);
      
      // insert the edge between two random vertices
      Edge edge = g.insertEdge(u,v,new Integer(i));
    }

    // print the input graph
    System.out.println("The Input Graph: ");
    System.out.println(g);
    System.out.println();

    /* EXECUTING THE ALGORITHMS */
    
    // find and return an iterator containing an alternating sequence
    // of vertices and edges (a path) from the source vertex to the
    // sink vertex
    Iterator path = (Iterator)findPath.execute(g,source,sink);

    // find and return a cycle of the graph.  the third parameter can
    // be anything, as it is unused by the algorithm
    Iterator cycle = (Iterator)findCycle.execute(g,source,null);

    // return whether the graph is connected. the third parameter can
    // be anything, as it is unused by the algorithm
    Boolean connected = (Boolean)connectivity.execute(g,source,null);

    /* PRINTING THE RESULTS */

    System.out.println("RESULTS:\n");

    // FindPathDFS
    
    // if the iterator is non-empty, there exists a path
    if(path.hasNext()) {
      
      System.out.println("The following path was found between vertex " +
			 source + " and vertex " + sink + ":");

      // loop through the path and print out each vertex or edge
      while(path.hasNext()) {

	// each component in the path is either a vertex or an edge
	DecorablePosition vertexOrEdge = (DecorablePosition)path.next();

	// if it's a vertex
	if(vertexOrEdge instanceof Vertex) {
	  System.out.println("Vertex " + vertexOrEdge);
	}
	// otherwise, it's an edge
	else {
	  System.out.println("Edge " + vertexOrEdge);
	}	
      }
    }
    // otherwise, no path exists between the source and sink
    else {
      System.out.println("No path was found between vertex " + 
			 source + " and vertex " + sink + ".");
    }

    System.out.println();

    //FindCycleDFS
    
    // if the iterator is non-empty, there exists a cycle in the graph
    if(cycle.hasNext()) {
      
      System.out.println("The following cycle was found:");

      // loop through the cycle and print out each vertex or edge
      while(cycle.hasNext()) {

	// each component in the cycle is either a vertex or an edge
	DecorablePosition vertexOrEdge = (DecorablePosition)cycle.next();

	// if it's a vertex
	if(vertexOrEdge instanceof Vertex) {
	  System.out.println("Vertex " + vertexOrEdge);
	}
	// otherwise, it's an edge
	else {
	  System.out.println("Edge " + vertexOrEdge);
	}	
      }
    }
    // otherwise, no cycle exists between the source and sink
    else {
      System.out.println("No cycle was found in the graph.");
    }

    System.out.println();

    //ConnectivityDFS

    // determined whether the algorithm returned true or false
    if(connected.booleanValue() == true) {
      System.out.println("The graph is connected.");
    }
    else {
      System.out.println("The graph is not connected.");
    }

  }

  // helper function to return a random number in the interval
  // [low,high] (inclusive)
  private static int randomNumber(int high, int low) {
    return low + (int)(Math.random()*(high-low+1));
  }
  
}