/*
 * Main.java
 *
 * Created on November 2, 2007, 9:50 PM
 *
 */

import java.io.*;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;
import java.util.StringTokenizer;

/**
 * @author Lukas Blakk 030 211 056
 * @date November 15, 2007 Assignment 2 for BTP500 - Lew Baxter
 */

/**
 * The Graph class will hold an adjacency matrix and be able to be asked if
 * there is an edge between two points as well as be able to identify the
 * neighbours of a point it also contains an algorithm to set the neighbours for
 * a knight's tour
 */
class Graph {
	private int size;
	boolean[][] adjacencyMatrix = null;
	ArrayList<Node> vertices = null;

	public Graph() {

	}

	/**
	 * print() displays the adjacency matrix contents as well as the edges found
	 * for each node in the graph
	 */
	void print() {

		// prints out the adjacency matrix values
		System.out.println("Size is: " + size);
		for (int row = 1; row < size; row++) {
			for (int column = 1; column < size; column++) {
				System.out
						.println("The value of adjacencyMatrix[" + row + "]["
								+ column + "] " + "is: "
								+ adjacencyMatrix[row][column]);
			}
		}

		// prints out the edges information
		for (Node i : vertices) {
			if (i.name != "dummy") {
				System.out.println("Node: " + i.name + " edges ...");
				ArrayList<Node> edges = new ArrayList<Node>();
				edges = getNeighbours(i);
				for (Node e : edges) {
					System.out.println("Edges are " + e.name);
				}
			}
		}

	}

	/**
	 * setEdge accepts row and column in order to set the value of the Graph
	 * adjacency matrix
	 * 
	 * @param row
	 * @param column
	 */
	void setEdge(int row, int column) {
		// 1 - 2 so adjacencyMatrix[1][2] = 1 and adjacencyMatrix[2][1] = 1
		adjacencyMatrix[row][column] = true;
		adjacencyMatrix[column][row] = true;
	}

	/**
	 * Loads up the vertices with Nodes to represent the graph points
	 */
	void setVertices() {
		for (int i = 1; i < size; i++) {
			Node n = new Node(false, String.valueOf(i));
			vertices.add(i, n);
		}
	}

	/**
	 * getNeighbours returns an ArrayList of any Nodes that share an edge with
	 * the Node which is passed in
	 * 
	 * @param index
	 * @return ArrayList
	 */
	ArrayList<Node> getNeighbours(Node a) {
		ArrayList<Node> temp = new ArrayList<Node>();
		int index = vertices.indexOf(a);

		for (int i = 0; i < getSize(); i++) {
			if (isEdge(index, i)) {
				temp.add(vertices.get(i));
			}

		}

		return temp;
	}

	/**
	 * resets the adjacency matrix and the vertices to null so that the graph
	 * can be reused in the same run of the program.
	 */
	void resetGraph() {
		adjacencyMatrix = null;
		vertices = null;
	}

	/**
	 * This function loads the adjacency matrix with false values and
	 * initializes the vertices ArrayList as well as setting the first vertex to
	 * "dummy" so that all node lists will start at 1
	 * 
	 * @param sizeOfGraph
	 * @param nodes
	 */
	void setGraph(int sizeOfGraph) {
		// check that there at least three points for a circuit
		if (sizeOfGraph < 3) {
			System.out.println("Not enough nodes to "
					+ "make a connected graph.");
		} else {
			size = sizeOfGraph;
			// initialize the Adjacency Matrix to false
			// the size is n X n (or size X size)
			adjacencyMatrix = new boolean[size][size];
			boolean tempadjacencyMatrix = false;
			for (int row = 0; row < size; row++) {
				for (int column = 0; column < size; column++) {
					adjacencyMatrix[row][column] = tempadjacencyMatrix;
				}
			}
			// initialize the Node array for the vertices
			vertices = new ArrayList<Node>();
			// set dummy for 0 so that Nodes start at 1
			vertices.add(0, new Node(false, "dummy"));

		}
	}

	/**
	 * 
	 * @param row
	 * @param column
	 * @return
	 */
	// check for an edge between two points
	boolean isEdge(int row, int column) {
		return adjacencyMatrix[row][column];
	}

	/**
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	// check for an edge between two nodes
	boolean isEdge(Node a, Node b) {
		return isEdge(Integer.valueOf(a.name), Integer.valueOf(b.name));
	}

	/**
	 * @return the size of the graph
	 */
	int getSize() {
		return size;
	}

	/**
	 * @return the Node in index 1 of the vertices ArrayList
	 */
	Node firstNode() {
		return vertices.get(1);
	}

}

/**
 * Node is a data structure that represents a point on a graph and has a name as
 * well as a boolean value to indicate if it has been visited
 */
class Node {

	boolean visited = false;
	String name;

	public Node(boolean vis, String n) {
		visited = vis;
		name = n;
	}

	public Node(Node a) {
		this.name = a.name;
		this.visited = a.visited;
	}

	void visit() {
		this.visited = true;
	}

	void clearVisit() {
		visited = false;
	}

	boolean isVisited() {
		return visited;
	}

	String getName() {
		return name;
	}

	boolean equals(Node u) {
		return u.name.equals(this.name);
	}

}

/**
 * 
 * @author lukasblakk
 * 
 */

class Queue {

	LinkedList<LinkedList<Node>> queue;

	public Queue() {
		queue = new LinkedList<LinkedList<Node>>();
	}

	public void enqueue(LinkedList<Node> o) {
		queue.addLast(o);
	}

	public int size() {
		return queue.size();
	}

	public LinkedList<Node> dequeue() {
		LinkedList<Node> removeLast = queue.removeLast();
		return removeLast;

	}

	public boolean isEmpty() {
		return queue.isEmpty();
	}

}

/**
 * 
 * @author lukasblakk
 * 
 */
public class Main {

	static Graph currentGraph = new Graph();
	static String circuit = null;

	/** Creates a new instance of Main */
	public Main() {

	}

	/**
	 * @param args
	 *            the command line arguments
	 */
	public static void main(String[] args) {
		boolean running = true;

		while (running) {
			System.out
					.println("Hello and welcome to the Hamiltonian Circuit Finder.");
			System.out.println("Please choose an option from the menu:");
			System.out.println("[1] Load a graph");
			System.out.println("[2] Print the current graph");
			System.out.println("[3] Check for Hamiltonian Circuit");
			System.out.println("[4] Quit");

			// Accept user input
			// open up standard input
			BufferedReader br = new BufferedReader(new InputStreamReader(
					System.in));

			System.out.print("Enter Choice: ");
			System.out.flush();
			String s;
			try {
				s = br.readLine();
				StringTokenizer st = new StringTokenizer(s);
				char[] ca = st.nextToken().toCharArray();
				char c = ca[0];
				switch (c) {

				case '1':
					loadGraph();
					break;
				case '2':
					if (currentGraph.getSize() > 0) {
						printGraph();
					} else {
						System.out
								.println("You don't have a graph yet.  Please load a graph.");
					}
					break;
				case '3':
					if (currentGraph.getSize() > 0) {
						runHamilonian();
					} else {
						System.out.println("Please load a graph first.");
					}
					break;
				case '4':
					running = false;
					break;
				default:
					System.out
							.println("Must choose between 1 and 4.  Please try again.");
					break;

				}

			} catch (IOException e) {
				// Auto-generated catch block
				e.printStackTrace();
			}

		}

		System.out.println("Exiting now....");
		System.out.println("Goodbye.");

	}

	private static void printGraph() {
		if (currentGraph != null) {
			currentGraph.print();
		} else {
			System.out
					.println("You haven't loaded a graph in the system.  Please load a graph first.");
		}
	}

	/**
	 * runHamiltonian checks user input to call either a depth first search or a
	 * breadth first search
	 */
	private static void runHamilonian() {
		// DEBUG checking to see that current graph persisted
		// currentGraph.print();

		// User chooses Stack Solution or Queue Solution
		System.out.println("Depth First (d) Search or Breadth First (b)?");

		// Accept user input
		// open up standard input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		System.out.print("Enter Choice: ");
		System.out.flush();
		String s;
		try {
			s = br.readLine();
			StringTokenizer st = new StringTokenizer(s);
			char[] ca = st.nextToken().toCharArray();
			char c = ca[0];
			switch (c) {
			case 'd':
				System.out
						.println("Calling on the Depth First Search...This may take a moment...");
				// send in (size - 1) because that's how many nodes there are
				if (depthFirstSearch(currentGraph.firstNode(), (currentGraph
						.getSize() - 1))) {
					System.out.println("Found a hamiltonian circuit!");
					System.out.println(circuit);
				} else {
					System.out
							.println("No circuit was found, try a different graph.");
				}
				break;
			case 'b':
				System.out
						.println("Calling on the Breadth First Search...This may take a moment...");
				if (breadthFirstSearch(currentGraph.firstNode(), (currentGraph
						.getSize() - 1))) {
					System.out.println("Found a hamiltonian circuit!");
					System.out.println(circuit);
				} else {
					System.out
							.println("No circuit was found, try a different graph.");
				}
				break;
			default:
				System.out
						.println("Error - You must select 'd' or 'b' to run a search.");
				break;
			}
		} catch (IOException e) {
			System.out.println("Error accepting user input " + e);
			e.printStackTrace();
		}

	}

	private static boolean breadthFirstSearch(Node u, int sizeOfGraph) {

		// initialize the first set with the first node
		LinkedList<Node> partialSet = new LinkedList<Node>();
		LinkedList<Node> tempSet = new LinkedList<Node>();
		// visit the node
		u.visit();
		// add to the partial set
		partialSet.add(u);

		// TODO Debug remove
		System.out.println(sizeOfGraph);

		// initialize the seachStack with the first set
		Queue searchQueue = new Queue();
		searchQueue.enqueue(partialSet);

		// a variable to toggle if a solution is found
		boolean solution = false;

		while (!searchQueue.isEmpty() || !solution) {
			// temporary local variables
			Node lastNode;

			// pop a set off the stack
			tempSet = searchQueue.dequeue();

			// check to see if the stack is a solution
			// is it as long as the size of the graph?
			System.out.println("Size of set = " + tempSet.size()); // DEBUG
			// TODO remove

			// should the set be equal in length the amount of nodes we are
			// looking to connect then check for a solution
			if (tempSet.size() == sizeOfGraph) {
				// look at the lastNode
				lastNode = tempSet.removeLast();
				// get the neighbours of the lastNode
				Iterator<Node> iter = currentGraph.getNeighbours(lastNode)
						.iterator();
				while (iter.hasNext() && !solution) {
					Node v = (Node) iter.next();
					if (v.name == u.name) {
						// the last node has a neighbour that is the first node
						// we have a solution!
						circuit = "A path is: ";
						for (Node i : tempSet) {
							circuit += i.name + " ";
						}
						circuit += lastNode.name + " 1";
						solution = true;
					} else {
						// TODO Remove - DEBUG
						System.out.println("Name of v " + v.name.toString()
								+ " Name of u " + u.name.toString());
						System.out
								.println("Removing from last item from set and pushing back into stack");
						// lastNode.clearVisit();
						// searchStack.push(tempSet);
					}
				}
			} else {
				// Otherwise, we need to check for dead end partials and
				// if no dead end, then go a level deeper in our search
				if (!tempSet.isEmpty()) {
					// get the last Node in the set
					lastNode = tempSet.getLast();

					// find the Neighbours for the last Node in the current set
					Iterator<Node> iter = currentGraph.getNeighbours(lastNode)
							.iterator();

					boolean unvisited = false;
					// if there are neighbours it is not a dead end
					if (iter.hasNext()) {

						while (iter.hasNext() && !unvisited) {
							Node v = (Node) iter.next();
							// should there be an unvisited node, add it to the
							// set
							// then add the set to the stack
							if (!v.isVisited()) {
								unvisited = true;
								v.visit();
								tempSet.add(v);
								searchQueue.enqueue(tempSet);

							}
						}
						if (!unvisited) {
							tempSet.removeLast();
							searchQueue.enqueue(tempSet);

						}
					}
				}// else it's a dead end, the set will not be returned
				// to the stack
			}
		}

		return solution;

	}

	/**
	 * Using a Java Stack class, this function searches for a Hamiltonian
	 * circuit in a graph
	 */
	private static boolean depthFirstSearch(Node u, int sizeOfGraph) {

		// initialize the first set with the first node
		// visit the node and add to the partial set
		LinkedList<Node> partialSet = new LinkedList<Node>();
		u.visit();
		partialSet.add(u);

		// TODO Debug remove
		System.out.println(sizeOfGraph);

		// initialize the seachStack with the first set
		Stack<LinkedList<Node>> searchStack = new Stack<LinkedList<Node>>();
		searchStack.push(partialSet);

		// a variable to toggle if a solution is found
		boolean solution = false;

		while (!searchStack.isEmpty() || !solution) {
			// temporary local variables
			Node lastNode;

			// Three options:
			// * valid partials go back in storage to be pulled out again later
			// * invalid partials are discarded
			// * complete circuit returns the hamiltonian 

			LinkedList<Node> tempSet = new LinkedList<Node>();

			tempSet = searchStack.pop();

			// check to see if the stack is a solution
			// is it as long as the size of the graph?
			System.out.println("Size of set = " + tempSet.size()); // DEBUG
			// TODO remove

			// should the set be equal in length the amount of nodes we are
			// looking to connect then check for a solution
			if (tempSet.size() == sizeOfGraph) {
				// look at the lastNode
				lastNode = tempSet.removeLast();
				// get the neighbours of the lastNode
				Iterator<Node> iter = currentGraph.getNeighbours(lastNode)
						.iterator();
				while (iter.hasNext() && !solution) {
					Node v = (Node) iter.next();
					if (v.name == u.name) {
						// the last node has a neighbour that is the first
						// node
						// we have a solution!
						circuit = "A path is: ";
						for (Node i : tempSet) {
							circuit += i.name + " ";
						}
						circuit += lastNode.name + " 1";
						solution = true;
					} else {
						// TODO Remove - DEBUG
						System.out.println("Name of v " + v.name.toString()
								+ " Name of u " + u.name.toString());
						System.out
								.println("Path found that does not complete circuit.");
					}
				}
			} else {
				// Otherwise, we need to check for dead end partials and
				// if no dead end, then go a level deeper in our search
				if (!tempSet.isEmpty()) {
					// get the last Node in the set
					lastNode = tempSet.getLast();

					// find the Neighbours for the last Node in the current
					// set
					Iterator<Node> iter = currentGraph.getNeighbours(lastNode)
							.iterator();

					boolean unvisited = false;
					// if there are neighbours it is not a dead end
					if (iter.hasNext()) {

						while (iter.hasNext() && !unvisited) {
							Node v = (Node) iter.next();
							// should there be an unvisited node, add it to
							// the
							// set
							// then add the set to the stack
							if (!v.isVisited()) {
								unvisited = true;
								v.visit();
								tempSet.add(v);
								searchStack.push(tempSet);

							}
						}
						if (!unvisited) {
							tempSet.removeLast();
							searchStack.push(tempSet);

						}
					}
				}// else it's a dead end, the set will not be returned
				// to the stack
			}

		}

		return solution;

	}

	/*
	 * loadGraph is a function which takes user input of graph coordinates in
	 * the form of "1-2 2-3 3-1" and loads up the instance of currentGraph with
	 * the edges so that the user can then go and search for the Hamiltonian
	 * circuit
	 */
	private static void loadGraph() {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		System.out.println("How many nodes will you be adding? ");
		System.out.flush();

		int nodes = 0;
		int sizeOfGraph = 0;

		String input;
		try {
			input = br.readLine();

			try {
				nodes = Integer.parseInt(input);
				sizeOfGraph = nodes + 1;
				System.out.println("\n\n\n\n\n");
				System.out
						.println("=============================================================================");
				System.out
						.println("*   Please enter the coordinates in a string in the following style         *");
				System.out
						.println("*   example: \"1-2 2-3 3-6 6-9 9-1\" with only - between the coords           *");
				System.out
						.println("=============================================================================");

				// creating a stream for user input

				System.out.print("Enter Graph Coordinates: ");
				System.out.flush();

				// reset the current graph so we can load it with new edges
				currentGraph.resetGraph();
				// set graph to the amount of nodes
				currentGraph.setGraph(sizeOfGraph);

				String s;
				try {
					s = br.readLine();
					StringTokenizer st = new StringTokenizer(s);
					while (st.hasMoreTokens()) {
						String node = st.nextToken();
						String[] c = node.split("-");
						int a = Integer.parseInt(c[0]);
						int b = Integer.parseInt(c[1]);
						currentGraph.setEdge(a, b);

					}

					currentGraph.setVertices();

				} catch (IOException e) {
					// handle any user input errors here
					System.out.println("Error reading user input " + e);
					e.printStackTrace();
				}
			} catch (NumberFormatException e) {
				System.out
						.println("\n\n You must enter a number...Back to main menu\n\n");
			}

		} catch (IOException e) {
			System.out.println("Error accepting user input " + e);
			e.printStackTrace();
		}

	}

}