/*
 * GeometricGraph.class
 * Part of package project
 *
 * Author: Philip Bradley
 *
 */

package project;

import java.lang.Math;
import java.util.Random;
import java.io.*;

public class GeometricGraph implements Serializable{

  private Random numberGen = new Random();
  private int[][] adjacancyMatrix;
  private int order = 0;
  private int size = 0;
  private int i,n;
  
  public GeometricGraph(int order) {
    this.order = order;
    adjacancyMatrix = new int[order][order];
  }
  
  public GeometricGraph(int order, String filename) {
    this.order = order;
    adjacancyMatrix = new int[order][order];
    size = readMatrixFromFile(filename, adjacancyMatrix);
  }
  
  /**
    * This generates edges by creating n GraphNodes and connecting
    * those nodes of Euclidean distance less than cutOffPoint.
    */
  public void generateEdges(double cutOffPoint) throws Exception {
    
    double delta;
    GraphNode[] nodeArray;
    
    nodeArray = new GraphNode[order];
    
    for (n = 0; n<order; n++) {
      nodeArray[n] = new GraphNode();
    }
    
    if ((cutOffPoint >= 0) && (cutOffPoint <= 1)) {
      // The co-ordinates of the GraphNode objects exists within a 1x1 grid.
      // Thus a valid cutoffrange is between 0 and 1.
      
      for (n=0; n<order-1; n++) {
	for (i= n+1; i<order; i++) {
	  delta = java.lang.Math.sqrt(java.lang.Math.pow((nodeArray[n].x - nodeArray[i].x),2.0) +
				      java.lang.Math.pow((nodeArray[n].y - nodeArray[i].y),2.0));
	  
	  if (delta < cutOffPoint) {
	    adjacancyMatrix[n][i] = (numberGen.nextInt() % 100) + 1;
	    adjacancyMatrix[i][n] = adjacancyMatrix[n][i];
	    size++;
	  }
	}
      }
    } else {
      throw(new Exception("Cutoff Point out of range: " + cutOffPoint));
    }
  }
  
  /**
    * Adds an edge of weight 1 to the graph
    */
  public void addEdge(int i, int j) throws Exception {
    if (i != j) {
      adjacancyMatrix[i][j] = 1;
      adjacancyMatrix[j][i] = 1;
      size++;
    } else {
      throw(new Exception("Cannot add edge from node " + i + " to " + j));
    }
  }

  /**
    * Adds an edge of weight w to the graph
    */
  public void addEdge(int i, int j, int w) throws Exception {
    if (i != j) {
      adjacancyMatrix[i][j] = w;
      adjacancyMatrix[j][i] = w;
      size++;
    } else {
      throw(new Exception("Cannot add edge from node " + i + " to " + j));
    }
  }

  public int getEdgeWeight(int i, int j) throws NoSuchEdgeException {
    if (adjacancyMatrix[i][j] != 0) {
      return adjacancyMatrix[i][j];
    } else {
      throw( new NoSuchEdgeException(i,j));
    }
  }

  /**
    * @return a boolean indicating if an edge joins the vertices i & j
    */
  public boolean hasEdge(int i, int j) {
    return ((adjacancyMatrix[i][j] != 0) && (i != j));
  }

  /**
    * This returns a boolean indicating that the graph is connected.
    * This is determined by traversing the graph in breadth first
    * order and checking that all vertices have been 'visited'
    *
    * @return boolean indicating if the graph is connected.
    */
  public boolean isConnected() {
    int[] traversalOrder = breadthFirstTraverse(0);
    int index = traversalOrder.length;
    int visitOrder = traversalOrder[0];
    
    while((index-- > 0) && (visitOrder != 0)) 
      visitOrder = traversalOrder[index];
    
    // If index == -1 then the whole array has been traversed 
    return(index == -1);
  }
  
  /**
    * This returns an array of int's indicating the vertices
    * which are adjacent to the input vertex.
    *
    * @return Array of int's indicating adjacent vertices.
    */
  private int[] getAdjacentVertices(int vertex) {
    int index0 = order;
    int index1 = 0;	
    int count = 0;
    int[] adjacentVertices;
    
    // Count the number of vertices adjacent to the target vertex. 
    while (--index0 >= 0) 
      if (adjacancyMatrix[vertex][index0] != 0) 
	count ++;
    
    adjacentVertices = new int[count];
    index0 = order;
    while (--index0 >= 0) {
      if (adjacancyMatrix[vertex][index0] != 0) 
	adjacentVertices[index1++] = index0;
    }
    return(adjacentVertices);
  }
  
  /**
    * This returns an array of int's indicating the order in which each
    * vertex was encountered. A value of 0 in a position means that that
    * vertex was not encountered in the Breadth First Search (BFS).
    *
    * @return Array of int's indicating traversal order of vertices.
    */
  private int[] breadthFirstTraverse(int vertex) {
    Queue q = new Queue();
    int[] visited = new int[order];
    int[] adjacentVertices;
    Integer v = new Integer(vertex);
    int index = 0;
    int count = 1;
    
    // Initialise array to 0s
    index = order;
    while (--index >= 0) 
      visited[index] = 0;
    
    visited[v.intValue()] = 1;
    q.enQueue(v);
    try {
      while(!q.isEmpty()) {
	v = (Integer)q.serve();
	adjacentVertices = getAdjacentVertices(v.intValue());	
	
	index = adjacentVertices.length;
	while (index-- > 0) {
	  if (visited[adjacentVertices[index]] == 0) {
	    q.enQueue(adjacentVertices[index]);
	    visited[adjacentVertices[index]] = ++count;
	  }
	}
      }
    } catch (Exception e) {
      System.err.println("Error: " + e.getMessage());
      System.exit(1);
    }
    return(visited);
  }
  
  /**
    * Performs Breadth First Search ReOrdering on the graph, that is, renames
    * the vertices so that their name corresponds to the order in which they
    * were encountered by a breadth first search. This requires the graph to be
    * connected.
    */
  public void BFSReordering(int vertex) {
    
    int[] traversal = breadthFirstTraverse(vertex);
    int[][] newAdjacancyMatrix = new int[order][order];
    int i,j;
    
    for (i=0; i<order; i++) {
      for (j=0; j<order; j++) {
	newAdjacancyMatrix[traversal[i] - 1][traversal[j] - 1] = adjacancyMatrix[i][j];
      }
    }
    
    adjacancyMatrix = newAdjacancyMatrix;
  }
  
  /**
    * @return The size of the graph (The number of edges)
    */
  public int getSize() {
    return(size);
  }
  
  /**
    * @return The order of the graph (The number of nodes)
    */
  public int getOrder() {
    return(order);
  }
  
  /**
    * @return A reference to the adjacancy matrix representing the graph.
    */
  public int[][] getAdjacancyMatrix() {
    return(adjacancyMatrix);
  }
  
  /**
    * Prints every edge in the for i,j to System.out
    * Used for testing purposes
    */
  public void printEdges() {
    int i;
    int j;
    
    for (i=0; i<order; i++) {
      for (j=i; j<order; j++) {
	if (adjacancyMatrix[i][j] != 0) {
	  System.out.println(i + ", " + j);
	}
      }
    }
  }
  
  /**
    * Prints the adjacancy matrix to the screen (formatted into
    * columns). Purely for test purposes.
    */
  public void write() {
    int currentEntry = 0;
    
    for (int i=0; i<order; i++) {
      for (int j=0; j<order; j++) {
	currentEntry = adjacancyMatrix[i][j];
	if (currentEntry < 10 && currentEntry >= 0) { 
	  System.out.print("   " + currentEntry);
	} else if ((currentEntry >= 10) || (currentEntry < 0 && currentEntry > -10)) {
	  System.out.print("  " + currentEntry);
	} else if (currentEntry <= -10) {
	  System.out.print(" " + currentEntry);
	}	
      }
      System.out.println("");
    }
  }
  
  /**
    * Saves the state of the object to a file.
    */
  public void writeToFile(String filename) {
    
    try {
      ObjectOutputStream os = new ObjectOutputStream(new FileOutputStream(filename));
      os.writeObject(this);
      os.close();
    } catch (Exception e) {
      System.err.println("Error writing object: " + e.getMessage());
    }
  }
  
  public static GeometricGraph readFromFile(String filename) {
    GeometricGraph g = (GeometricGraph)null;
    try {
      ObjectInputStream in = new ObjectInputStream(new FileInputStream(filename));
      g = (GeometricGraph)in.readObject();
    } catch (Exception e) {
      System.err.println("Error reading object: " + e.getMessage());
    }
    return(g);
  }

  /**
    * This reads a text file describing a matrix and assigns that
    * matrix to that passed in.
    *
    * @return The size of the graph represented by the matrix read in
    */
  public int readMatrixFromFile(String filename, int[][] matrix) {
    // The reference to a matrix is passed in rather that creating
    // a matrix and returning that. This saves on a potentially wasteful
    // memory allocation to accomodate a potentially very large matrix
    // which is typically destroyed afterwards.
    
    int graphSize = 0;
    try {
      FileReader fileReader = new FileReader(filename);
      StreamTokenizer st = new StreamTokenizer(fileReader);
      
      int rowLength = matrix.length;
      int columnLength = matrix[0].length;
      
      int row = 0;
      int col = 0;
      while (st.nextToken() != StreamTokenizer.TT_EOF) {
	if ((matrix[row][col] = (int)st.nval) != 0) {
	  graphSize++;
	}
	
	col++;
	if (col == columnLength) {
	  col = 0;
	  row++;
	}
      }
    } catch (Exception e) {
      System.err.println("Exception: " + e);
    }
    return((int)graphSize/2);
  }

  public static GeometricGraph readAdjacancyList(String filename) {

    int graphOrder = 0;
    int graphSize = 0;
    int vertex = 0;
    GeometricGraph g = (GeometricGraph)null;

    try {
      FileReader fileReader = new FileReader(filename);
      StreamTokenizer st = new StreamTokenizer(fileReader);

      graphOrder = (int)st.nval;
      st.nextToken();
      graphSize = (int)st.nval;
      g = new GeometricGraph(graphOrder);

      while (st.nextToken() != StreamTokenizer.TT_EOF) {
	vertex = (int)st.nval;
	while (st.nextToken() != StreamTokenizer.TT_EOL) {
	  g.addEdge(vertex, (int)st.nval);
	}
      }    
    } catch (Exception e) {
      System.out.println("Error: " + e.getMessage());
    }
    return(g);
  }

  public void printAdjacancyList() {
    int i;
    int j;
    String row = new String("");

    System.out.println(getOrder() + " " + getSize());
    for (i=0; i<order; i++) {
      row = "";
      for (j=i; j<order; j++) {
	if (adjacancyMatrix[i][j] != 0) {
	  row = row + (" " + j);
	}
      }
      if (row.length() != 0) {
	System.out.println(i + " " + row);
      }
    }
  }
  
  public static void main(String[] args) {
    /*
     * At the moment the main function provides a user interface to creating
     * a new instance of class GeometricGraph and writing it to a file.
     * This should be moved to a seperate method.
     */
    
    if (args.length == 3) {
      try {
	System.out.println("Creating new graph of order " + args[0]);
	GeometricGraph g = new GeometricGraph(new Integer(args[0]).intValue());
	g.generateEdges(new Double(args[1]).doubleValue());
	System.out.println("Graph has size: " + g.getSize());
	System.out.println("Writing graph to file " + args[2]);
	g.writeToFile(args[2]);
	if (g.isConnected()) {
	  System.out.println("Graph is connected.");
	} else {
	  System.out.println("Graph is unconnected");
	}
      } catch (Exception e) {
	System.err.println("Error: " + e.getMessage());
      }
    } else {
      System.err.println("Usage Error: GeometricGraph Order CutOffPoint FileName");
    }
  }
}

class GraphNode implements Serializable {
  public double x;
  public double y;  
  private Random numberGen = new Random();
  
  GraphNode () {	
    x = numberGen.nextDouble();
    y = numberGen.nextDouble();
  }
}