import java.io.*;
import java.util.*;
import CITS2200.*;

public class CITS2200ProjectTester {
	public static void loadGraph(CITS2200Project project, String path) {
		// The graph is in the following format:
		// Every pair of consecutive lines represent a directed edge.
		// The edge goes from the URL in the first line to the URL in the second line.
		try {
			BufferedReader reader = new BufferedReader(new FileReader(path));
			while (reader.ready()) {
				String from = reader.readLine();
				String to = reader.readLine();
				System.out.println("Adding edge from " + from + " to " + to);
				project.addEdge(from, to);
			}
		} catch (Exception e) {
			System.out.println("There was a problem:");
			System.out.println(e.toString());
		}
	}

	public static void main(String[] args) {
		// Change this to be the path to the graph file.
		String pathToGraphFile = "E:\\lab2\\example_graph.txt";
		// Create an instance of your implementation.
		CITS2200Project proj = new CITS2200Project();
		// Load the graph into the project.
		loadGraph(proj, pathToGraphFile);

		proj.getShortestDistance("/wiki/Flow_network", "/wiki/Braess%27_paradox");
		proj.getShortestDistance("/wiki/Flow_network", "/wiki/Minimum-cost_flow_problem");
		proj.hamlitonianPath("/wiki/Flow_network");
	}
}

class CITS2200Project {
	static HashMap<String, Vert> vertMap;
	public int mapSize, pathSize;
	public Vert[] path;
	public Vert pathStart;

	public CITS2200Project() {
		this.vertMap = new HashMap<String, Vert>();
		this.mapSize = 0;
		this.pathSize = 0;
	}

	public void addEdge(String source, String dest) {
		Vert v = getVert(source);
		Vert w = getVert(dest);
		v.edgeList.add(w);

	}

	public Vert getVert(String vertexname) {
		Vert v = vertMap.get(vertexname);
		if (v == null) {
			v = new Vert(vertexname);
			vertMap.put(vertexname, v);
			mapSize++;
		}
		return v;
	}

	public int getShortestDistance(String source, String dest) {
		HashMap<Vert, Integer> distance = new HashMap<Vert, Integer>();
		LinkedList<Vert> uncheckedVert = new LinkedList<Vert>();
		ArrayList<Vert> checkedVert = new ArrayList<Vert>();
		Vert start = vertMap.get(source);
		Vert end = vertMap.get(dest);
		if (start == null) {
			throw new Underflow("Source not in graph");
		}
		if (end == null) {
			throw new Underflow("Destination not in graph");
		}

		distance.put(start, 0);
		uncheckedVert.add(start);
		while (!uncheckedVert.isEmpty()) {
			Vert vertex = uncheckedVert.removeLast();
			if (checkedVert.contains(vertex)) {
				continue;
			}
			checkedVert.add(vertex);

			for (Vert neighbour : vertex.edgeList) {
				int current = distance.get(vertex) + 1;
				if (distance.get(neighbour) == null) {
					distance.put(neighbour, current);
					if (neighbour == end) {
						System.out.println("The distance between " + source + " and " + dest + " is " + distance.get(end));
						return distance.get(end);
					}
				}
			}
		}
		System.out.println("You cannot reach " + dest + " from " + source);
		return -1;
	}

	public Vert[] hamlitonianPath(String startpoint) {
		path = new Vert[mapSize];
		if (mapSize > 20) {
			System.out.println("Graph too big to find Hamiltonian Path");
			return null;
		}
		Vert start = vertMap.get(startpoint);
		if (start == null) {
			throw new Underflow("Source not in graph");
		}
		pathStart = start;
		try {
			path[0] = start;
			pathSize = 1;
			solvePath(start);
		} catch (Exception e) {
			System.out.println("There was a problem:");
			System.out.println(e.toString());
		}
		if (pathSize == mapSize) {
			if (path[pathSize].edgeList.contains(pathStart)) {
				System.out.println("Path found: ");
				for (int i = 0; i < mapSize; i++) {
					System.out.println(path[i].getID());
				}
				return path;
			}
		}
		System.out.println("No path found");
		return path;
	}

	public void solvePath(Vert vertex) {
		if (pathSize == mapSize) {
			if (path[pathSize].edgeList.contains(pathStart)) {
				return;
			}
		}
		for (Vert neighbour : vertex.edgeList) {
			path[pathSize] = neighbour;
			pathSize++;
			if (!isPresent(neighbour)) {
				solvePath(neighbour);
			}
			if (pathSize == mapSize) {
				if (path[pathSize].edgeList.contains(pathStart)) {
					return;
				}
			}
			path[pathSize] = null;
			pathSize--;
		}
	}

	public boolean isPresent(Vert v){
		for (int i = 0; i < pathSize - 1; i++){
			if(path[i] == v){
				return true;
			}
		}
		return false;
	}
}


class Vert {
	final private String id;
	public ArrayList<Vert> edgeList;


	public Vert(String id) {
		this.id = id;
		this.edgeList = new ArrayList<Vert>();
	}

	public String getID() {
		return id;
	}


	@Override
	public String toString() {
		return id;
	}

	}