package main;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import java.io.StreamTokenizer;
import java.util.Random;

/**
 * Lösung des "Traveling Salesman Problem" mit Branch-and-Bound.
 * @author Matthias Jauernig
 */
public class TSP {
	/**
	 * Gibt die Rundreisen an, die mit dem Algorithmus beendet wurden.
	 */
	static int m_tours;
	
	/**
	 * Dies stellt die obere Schranke O dar, welche zu jedem Zeitpunkt
	 * die Länge der bisher kürzesten Rundreise enthält.
	 */
	static double m_upperBound;
	
	/**
	 * Diese Matrix speichert die Distanzmatrix der zum jeweiligen Zeitpunkt 
	 * kürzesten gefundenen Rundreise ab. In dieser Matrix sind in jeder Spalte 
	 * und in jeder Zeile genau 1 Element besetzt, der Rest ist 
	 * Double.POSITIVE_INFINITY. Somit kann die Rundreise aus dieser 
	 * Distanzmatrix wiederhergestellt werden.
	 */
	static double[][] m_shortestKnownTour;
	
	/**
	 * Diese Methode berechnet in der mit distMatrix dargestellten Situation
	 * die untere Schranke für die Lösung des TSP.
	 * Vorbedingung: distMatrix ist eine gültige Distanzmatrix, enthält also 
	 * pro Zeile und Spalte mindestens ein Element !=Double.POSITIVE_INFINITY. 
	 * Es gilt distMatrix.length>1.
	 * Nachbedingung: Die untere Schranke der übergebenen Distanzmatrix wurde
	 * 	berechnet und zurückgegeben.
	 * @param distMatrix Distanzmatrix, in welcher die untere Schranke
	 * 					 berechnet werden soll.
	 * @return Untere Schranke für eine minimale Rundreise.
	 */
	static double lowerBound(double[][] distMatrix){
		double lBound = 0.0;
		
		// suche Summe der Minima aller Zeilen
		for(int i=0; i<distMatrix.length; i++){
			double rowMin = Double.POSITIVE_INFINITY;
			for(int j=0; j<distMatrix[i].length; j++){
				rowMin = Math.min(rowMin, distMatrix[i][j]);
			}
			lBound += rowMin;
		}
		
		//suche Summe der Minima aller Spalten
		for(int j=0; j<distMatrix[0].length; j++){
			double colMin = Double.POSITIVE_INFINITY;
			for(int i=0; i<distMatrix.length; i++){
				colMin = Math.min(colMin, distMatrix[i][j]);
			}
			lBound += colMin;
		}
		
		return lBound/2.0;
	}
	
	/**
	 * Diese Methode schließt die Kante from->to in das aktuelle Anfangsstück
	 * der Rundreise mit ein. Dazu werden nicht mehr gangbare Kanten auf
	 * Double.POSITIVE_INFINITY gesetzt.
	 * Vorbedingung: „from“ und „to“ sind 2 gültige Knoten des Graphen 
	 * mit from!=to. „from“ muss der letzte Knoten des aktuellen Anfangsstücks 
	 * der Rundreise sein, „to“ darf noch nicht Teil der Rundreise sein und 
	 * muss von „from“ erreicht werden können. distMatrix muss eine gültige 
	 * Distanzmatrix mit wenigstens einem Element in jeder Zeile und 
	 * Spalte != Double.POSITIVE_INFINITY sein. Es gilt distMatrix.length>1.
	 * Nachbedingung: Kanten, die mit der Entscheidung, die Kante from->to
	 * 	in die Rundreise einzuschließen, nicht mehr begehbar sind, wurden
	 * 	in distMatrix invalidiert, also auf Double.POSITIVE_INIFINTY gesetzt.
	 *  Das sind im einzelnen:
	 *  1.) alle Kanten VON from außer from->to,
	 *  2.) alle Kanten NACH to außer from->to,
	 *  3.) die Kante to->from. 
	 * @param from Von welchem Knoten geht die einzuschließende Kante aus?
	 * @param to Zu welchem Knoten führt die einzuschließende Kante?
	 * @param distMatrix Distanzmatrix des Graphen mit dem aktuellen
	 * 					 Anfangsstück einer Rundreise.
	 */
	static void includeEdge(int from, int to, double[][] distMatrix){
		// setze zunächst die Kanten auf Double.POSITIVE_INFINITY,
		// welche nicht mehr von "from" aus erreicht werden können
		for(int j=0; j<distMatrix[from].length; j++){
			if(j != to){
				distMatrix[from][j] = Double.POSITIVE_INFINITY;
			}
		}
		
		// setze nun die Kanten auf Double.POSITIVE_INFINITY,
		// welche "to" nicht mehr erreichen können
		for(int i=0; i<distMatrix.length; i++){
			if(i != from){
				distMatrix[i][to] = Double.POSITIVE_INFINITY;
			}
		}
		
		// setze Kante to->from auf Double.POSITIVE_INFINITY
		if(distMatrix.length != 2){
			distMatrix[to][from] = Double.POSITIVE_INFINITY;
		}
	}
	
	/**
	 * Diese Methode schließt die Kante from->to vom aktuellen Anfanggstück
	 * der Rundreise aus, das Anfangsstück wird also nicht über diese Kante
	 * erweitert.
	 * Vorbedingung: „from“ und „to“ sind 2 gültige Knoten des Graphen mit 
	 * from!=to. „from“ muss der letzte Knoten des aktuellen Anfangsstücks 
	 * der Rundreise sein, „to“ darf noch nicht Teil der Rundreise sein 
	 * und muss von „from“ erreicht werden können. distMatrix muss eine 
	 * gültige Distanzmatrix mit wenigstens einem Element in jeder Zeile und 
	 * Spalte != Double.POSITIVE_INFINITY sein. Es gilt distMatrix.length>1.
	 * Nachbedingung: Die Kante from->to wird nicht begangen und wurde
	 * 	somit in der Distanzmatrix invalidiert, also auf
	 * 	DOUBLE.POSITIVE_INFINITY gestzt.
	 * @param from Von welchem Knoten geht die auszuschließende Kante aus?
	 * @param to Zu welchem Knoten führt die auszuschließende Kante?
	 * @param distMatrix Distanzmatrix des Graphen mit dem aktuellen
	 * 					 Anfangsstück einer Rundreise.
	 */
	static void excludeEdge(int from, int to, double[][] distMatrix){
		// setze auszuschließende Kante auf Double.POSITIVE_INFINITY 
		distMatrix[from][to] = Double.POSITIVE_INFINITY;
	}
	
	/**
	 * Es soll die Anzahl aller vom Knoten „from” aus erreichbaren Knoten 
	 * ermittelt und zurückgegeben werden.
	 * Vorbedingung: „from“ ist ein gültiger Knoten des Graphen, 
	 * distMatrix ist eine gültige Distanzmatrix, in der in jeder Zeile 
	 * und Spalte wenigstens ein Element !=Double.POSITIVE_INFINITY 
	 * vorhanden sein muss. distMatrix.length>1.
	 * Nachbedingung: Die Anzahl der von from aus erreichbaren Knoten in der
	 * 	Distanzmatrix wurde ermittelt und zurückgegeben.
	 * @param from Knoten, von welchem aus die Anzahl erreichbarer Knoten
	 * 			ermittelt werden soll.
	 * @param distMatrix Distanzmatrix, in der die von from aus
	 * 					 erreichbaren Knotenzahl ermittelt werden soll. 
	 * @return Anzahl der von Knoten from aus erreichbaren Knoten.
	 */
	static int getNumberOfReachableNodes(int from, double[][] distMatrix){
		int nodes = 0;
		
		// gehe alle Kanten durch, die mit from adjazent sind
		for(int j=0; j<distMatrix.length; j++){
			if(distMatrix[from][j] < Double.POSITIVE_INFINITY){
				nodes++;
			}
		}
		
		return nodes;
	}
	
	/**
	 * Es soll der erste vom Knoten „from” aus erreichbare Knoten ermittelt 
	 * und zurückgegeben werden.
	 * Vorbedingung: „from“ ist ein gültiger Knoten des Graphen, distMatrix 
	 * ist eine gültige Distanzmatrix, in der in jeder Zeile und Spalte 
	 * wenigstens ein Element !=Double.POSITIVE_INFINITY vorhanden sein muss. 
	 * Es muss gelten: distMatrix.length>1.
	 * Nachbedingung: Der erste von from aus erreichbare Knoten wurde 
	 * ermittelt und zurückgegeben.
	 * @param from Knoten, von welchem aus der erste erreichbare Knoten
	 * 		  	   gefunden werden soll.
	 * @param distMatrix Distanzmatrix, in der der erste von from aus
	 * 					 erreichbare Knoten ermittelt werden soll.
	 * @return Erster von from aus erreichbarer Knoten oder -1, falls
	 * 		   kein Knoten von from ausgehend erreicht werden kann.
	 */
	static int getFirstReachableNode(int from, double[][] distMatrix){
		int node = -1;
		
		// gehe alle mit from adjazenten Kanten durch
		for(int j=0; j<distMatrix[from].length && node==-1; j++){
			if(distMatrix[from][j] < Double.POSITIVE_INFINITY){
				node = j; 
			}
		}
		
		return node;
	}
	
	/**
	 * Ist der Aufruf der Methode nicht-rekursiv, so soll durch diese Methode das 
	 * mit der Distanzmatrix übergebene TSP gelöst werden. Anderenfalls ist ein 
	 * rekursiver Aufruf erfolgt und der Entscheidungsbaum ist vom aktuellen Knoten 
	 * aus gemäß des in 2. und 4. spezifizierten Algorithmus weiter aufzubauen bzw. 
	 * abzuarbeiten.
	 * Vorbedingungen:
	 * I)	Für nicht-rekursive Aufrufe: distMatrix ist eine gültige Distanzmatrix 
	 * 		des zu lösenden TSP.
	 *		Für rekursive Aufrufe: distMatrix ist eine gültige Distanzmatrix, welche 
	 *		mit den bisher getroffenen Entscheidungen konform ist (enthält nur noch 
	 *		die in der Situation gangbaren Kanten) und ein Anfangsstück einer Rundreise 
	 *		enthält, welches in der Länge mit actTourLength übereinstimmt.
	 * II)	actTourLength muss die Länge des Anfangsstücks einer Rundreise bis zum 
	 * 		derzeitigen Knoten im Entscheidungsbaum angeben. 
	 * 		Es gilt: 0 <= actTourLength < distMatrix.length. Beim ersten 
	 * 		nicht-rekursiven Aufruf der Methode muss gelten: actTourLength==0.
	 * III)	fromNode gibt den Knoten an, welcher der letzte Knoten des aktuellen 
	 * 		Anfangsstücks der Rundreise ist und von dem aus ein Nachfolgeknoten 
	 * 		gefunden werden soll.
	 * IV)	Die untere Schranke der durch distMatrix gegebenen Situation ist kleiner 
	 * 		als die obere Schranke m_upperBound.
	 * Nachbedingung:
	 * I)	Für nicht-rekursive Aufrufe: m_upperBound enthält die Länge einer 
	 * 		minimalen Rundreise, m_shortestKnownTour gibt die Distanzmatrix 
	 * 		dieser Rundreise an. In dieser ist in jeder Spalte und Zeile jeweils 
	 * 		genau ein Element !=Double.POSITIVE_INFINITY, sodass man die 
	 * 		Distanzmatrix als Permutation der n Städte und somit als Rundreise 
	 * 		ansehen kann.
	 *		Für rekursive Aufrufe: wurde eine Rundreise gefunden, deren Kosten 
	 *		kleiner der bisher kürzesten Rundreise sind, so enthält m_shortestKnownTour 
	 *		diese kürzere Rundreise und m_upperBound ihre Länge.
	 * Rekursions-Invarianten:
	 * I)	Die obere Schranke m_upperBound beinhaltet die Kosten der bis dato 
	 * 		günstigsten Rundreise oder Double.POSITIVE_INFINITY, falls noch keine 
	 * 		Rundreise gefunden wurde.
	 * II)	m_shortestKnownTour beinhaltet die bis dato günstigste Rundreise oder null, 
	 * 		falls noch keine Rundreise gefunden wurde.
	 * @param actTourLength Anzahl der bereits in die Rundreise aufgenommenen Knoten.
	 * @param fromNode Von welchem Knoten soll ausgegangen werden?
	 * @param distMatrix Als Distanzmatrix kodierter Graph, der nur noch die in der
	 * 					 jeweiligen Situation gangbaren Kanten enthält.
	 */
	static void branchAndBound(int actTourLength, int fromNode, double[][] distMatrix){
		// lege Variablen für die unteren Schranken von linkem und rechtem Sohn fest
		double u1 = Double.POSITIVE_INFINITY;
		double u2 = Double.POSITIVE_INFINITY;
		double[][] distMatrix1 = null;
		double[][] distMatrix2 = null;
		
		// wenn nur noch 1 Knoten von Rundreise entfernt, dann gehe zurück zu
		// Knoten 0 und komplettiere die Rundreise
		if(actTourLength == distMatrix.length-1){
			m_tours++;
			double lBound = lowerBound(distMatrix);
			if(lBound < m_upperBound){ // wir haben eine neue kürzeste Rundreise
				m_upperBound = lBound;
				m_shortestKnownTour = distMatrix;
				//System.out.println("Zwischen-Ergebnis - "+actTourToString());
				//m_upperBound = Double.POSITIVE_INFINITY;
			}
			return;
		}
		
		// zum Anfang wollen wir noch nicht zurück
		distMatrix[fromNode][0] = Double.POSITIVE_INFINITY;
		
		// berechne die vom aktuellen Knoten aus erreichbaren Knoten
		int reachableNodes = getNumberOfReachableNodes(fromNode, distMatrix);
		int reachableFirst = getFirstReachableNode(fromNode, distMatrix);
		
		// wenn wir mehr als 1 Knoten erreichen können, dann können wir in
		// "nicht nach reachableFirst" verzweigen
		if(reachableNodes > 1){
			distMatrix2 = cloneDistMatrix(distMatrix);
			// auszuschließende Kante in Distanzmatrix eintragen
			excludeEdge(fromNode, reachableFirst, distMatrix2);
			// berechne untere Schranke nach dieser Entscheidung
			u2 = lowerBound(distMatrix2);
		}
		
		// verzweige immer in "nach reachableFirst"
		distMatrix1 = distMatrix;
		includeEdge(fromNode, reachableFirst, distMatrix1);
		u1 = lowerBound(distMatrix1);
		
		
		// verzweige dahin, wo die untere Schranke günstiger ist
		// unter der Bedingung, dass sie die obere Schranke nicht übersteigt
		if(u1 <= u2){
			// gehe zuerst in linken Sohn
			if(u1 < m_upperBound){
				branchAndBound(actTourLength+1, reachableFirst, distMatrix1);
				// gehe als zweites in rechten Sohn (nur, wenn rechter Sohn ex.)
				if(u2 < m_upperBound){
					branchAndBound(actTourLength, fromNode, distMatrix2);
				}
			}
		}else{
			// gehe zuerst in rechten Sohn
			if(u2 < m_upperBound){
				branchAndBound(actTourLength, fromNode, distMatrix2);
				// gehe als zweites in linken Sohn
				if(u1 < m_upperBound){
					branchAndBound(actTourLength+1, reachableFirst, distMatrix1);
				}
			}
		}
	}
	
	/**
	 * Diese Methode löst das TSP für den übergebenen Graphen. Als Ergebnis steht
	 * die Lösung in den Attributen m_upperBound und m_shortestKnownTour.
	 * Vorbedingung: distMatrix ist eine gültige Distanzmatrix, welche einen 
	 * vollständigen gerichteten Graphen enthält. D.h. für alle Elemente (i,j) 
	 * der Matrix mit 0 ?<= i,j <= ? n-1, i !=?            j  gilt: 
	 * 0 ?<= distMatrix[i][j] < Double.POSITIVE_INFINITY. Weiterhin gilt für i=j: 
	 * distMatrix[i][j]=Double.POSITIVE_INFINITY.
	 * Nachbedingung: Nach Abarbeitung des Branch-and-Bound-Algorithmus ist die 
	 * Distanzmatrix einer minimalen Rundreise in m_shortestKnownTour und die 
	 * Länge dieser in m_upperBound gespeichert. Die Distanzmatrix enthält genau 
	 * ein Element pro Zeile und pro Spalte, sodass sie als Permutation der n 
	 * Städte angesehen werden kann und somit als Rundreise.
	 * @param distMatrix Ursprüngliche Distanzmatrix, in welcher das zu
	 * 					 lösende TSP kodiert ist.
	 */
	static void solveTSP(double[][] distMatrix){
		// keine gültige Distanzmatrix -> Rückgabe
		if(distMatrix.length<2){
			return;
		}
		
		// setze obere Schranke anfänglich auf Double.POSITIVE_INFINITY
		m_upperBound = Double.POSITIVE_INFINITY;
		m_shortestKnownTour = null;
		m_tours = 0;
		
		// rufe Branch-and-Bound auf, um das TSP zu lösen
		branchAndBound(0, 0, distMatrix);
	}
	
	/**
	 * Diese Methode klont die übergebene 2D-Matrix.
	 * Vorbedingung: distMatrix != null.
	 * Nachbedingung: Kopie der übergebenen 2D-Matrix wurde zurückgegeben.
	 * @param distMatrix Zu klonende Matrix.
	 * @return Klon der Matrix.
	 */
	static double[][] cloneDistMatrix(double[][] distMatrix){
		double[][] clone = distMatrix.clone();
		for(int i=0; i<distMatrix.length; i++){
			clone[i] = distMatrix[i].clone();
		}
		return clone;
	}
	
	/**
	 * Diese Methode nimmt die aktuelle Distanzmatrix und extrahiert die
	 * darin enthaltene Rundreise -> diese wird mit ihrer Länge ausgegeben.
	 * Vorbedingung: m_shortestKnownTour beinhaltet eine Rundreise oder null,
	 * 	m_upperBound beinhaltet die Länge der Rundreise oder Double.POSITIVE_INFINITY.
	 * Nachbedingung: die Rundreise und ihre Länge wurden in einen String 
	 * transformiert und zurückgegeben.
	 * @return String, welcher die kürzeste Rundreise und ihre Länge enthält.
	 */
	static String actTourToString(){
		if(m_shortestKnownTour == null){
			return "Keine Rundreise vorhanden...";
		}
		
		String str = new String();
		str = "Kürzeste Rundreise: '0";
		
		int nextNode = getFirstReachableNode(0, m_shortestKnownTour);
		while(nextNode != 0){
			str += " -> " + nextNode;
			nextNode = getFirstReachableNode(nextNode, m_shortestKnownTour);
		}
		
		str += " -> 0', Kosten: " + m_upperBound;
		return str;
	}
	
	/**
	 * Konvertiere die übergebene Matrix in einen auszugebenden String.
	 * Vorbedingung: matrix != null
	 * Nachbedingung: die übergebene Matrix wurde in einen String umgewandelt
	 * 	und zurückgegeben.
	 * @param matrix Zu transformierende Matrix.
	 * @return String, welcher die Matrix repräsentiert.
	 */
	static String matrixToString(double[][] matrix){
		String str = new String();
		
		str = "[";
		for(int i=0; i<matrix.length; i++){
			if(i != 0){
				str += " ";
			}
			str += "[";
			for(int j=0; j<matrix[i].length; j++){
				str += matrix[i][j] + ",";
			}
			str = str.substring(0, str.length()-1);
			str += "]\n";
		}
		str = str.substring(0, str.length()-1);
		str +="]";
		
		return str;
	}
	
	/**
	 * Berechnet n!
	 * Rekursiver Aufruf und Rückgabe von n*fac(n-1), da gilt: n! = n*(n-1)!
	 * und 0! = 1 ist.
	 * Vorbedingung: n > 0
	 * Nachbedingung: n! wurde berechnet und zurückgegeben.
	 * @param n Zahl, von der die Fakultät gebildet werden soll
	 * @return Fakultät von n
	 */
	static int fac(int n){
		if(n < 0){
			return 0;
		}
		if(n == 0){
			return 1;
		}
		return n*fac(n-1);
	}
	
	/**
	 * Haupt-Programmmethode.
	 * Vorbedingung: keine
	 * Nachbedingung: keine
	 * @param args Übergebene Kommandozeilen-Argumente.
	 */
	public static void main(String[] args){
		int abfrage = 0;
		int dim = 0;
		double[][] distMatrix = null;
		
		// Menü anzeigen und Benutzerwahl abfragen
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		System.out.println("Traveling Salesman Problem");
		System.out.println("(1) Distanzmatrix selbst eingeben");
		System.out.println("(2) Distanzmatrix zufällig erzeugen");
		System.out.println("(3) Distanzmatrix aus Datei einlesen");
		do{
			System.out.print("> ");
			try{
				abfrage = Integer.parseInt(br.readLine().trim());
			}catch(IOException exc){
				System.out.println("IOException gefangen...");
				return;
			}
		}while(abfrage<1 || abfrage>3);
		
		// Dimension der zu erzeugenden Matrix abfragen
		if(abfrage<3){
			System.out.print("Matrixdimension eingeben: ");
			dim = 0;
			try{
				dim = Integer.parseInt(br.readLine().trim());
			}catch(IOException exc){
				System.out.println("IOException gefangen...");
				return;
			}
			distMatrix = new double[dim][dim];
		}
		
		// Benutzerwahl ausführen
		if(abfrage == 1){ // Matrix soll eingegeben werden
			for(int i=0; i<dim; i++){
				for(int j=0; j<dim; j++){
					if(i == j){
						distMatrix[i][j] = Double.POSITIVE_INFINITY;
					}else{
						System.out.print("Eingabe von distMatrix["+i+"]["+j+"]: ");
						try{
							distMatrix[i][j] = Double.parseDouble(br.readLine().trim());
						}catch(IOException exc){
							System.out.println("IOException gefangen...");
							return;
						}
					}
				}
			}
		}else if(abfrage == 2){ // Matrix soll zufällig erzeugt werden
			Random r = new Random();
			for(int i=0; i<dim; i++){
				for(int j=0; j<dim; j++){
					if(i == j){
						distMatrix[i][j] = Double.POSITIVE_INFINITY;
					}else{
						distMatrix[i][j] = r.nextInt(100) + 1.0;	
					}
				}
			}
		}else if(abfrage == 3){ // Matrix soll aus Datei eingelesen werden
			String filename = new String();
			System.out.print("Dateinamen angeben: ");
			// Filename einlesen lassen
			try{
				filename = br.readLine().trim();
			}catch(IOException exc){
				System.out.println("IOException gefangen...");
				return;
			}
			Boolean ende = false;
			Reader r = null;
			// Datei öffnen
			try{
				r = new FileReader(filename);
			}catch(FileNotFoundException e){
				System.out.println("Datei ist nicht existent, breche ab...");
				return;
			}
			StreamTokenizer st = new StreamTokenizer(r);
			// Matrixdimension einlesen
			try{
				st.nextToken();
			}catch(IOException e){
				System.out.println("Lesefehler, breche ab...");
				return;
			}
			dim = (int)st.nval;
			// Matrix einlesen
			distMatrix = new double[dim][dim];
			for(int i=0; i<dim && !ende; i++){
				for(int j=0; j<dim && !ende; j++){
					if(i == j){
						distMatrix[i][j] = Double.POSITIVE_INFINITY;
					}else{
						try{
							if(StreamTokenizer.TT_EOF == st.nextToken()){
								System.out.println("Unerwartetes EOF, breche ab...");
								return;
							}
						}catch(IOException e){
							System.out.println("Lesefehler, breche ab...");
							return;
						}
						switch (st.ttype) {
				    		case StreamTokenizer.TT_NUMBER:{
								distMatrix[i][j] = st.nval;
								break;
							}
							default:{
								System.out.println(
									"Unerwartetes Token empfangen, breche ab...");
								return;
							}
						}	
					}
				}
			}
		}
		
		// Gib Problemmatrix aus
		System.out.println("Löse folgendes TSP:");
		System.out.println(matrixToString(distMatrix));
		System.out.println("Berechne...");
		
		// Löse Problem
		solveTSP(distMatrix);
		
		// Gib Lösung aus
		System.out.println("Mit Branch&Bound beendete Rundreisen: "+m_tours+
			" (von "+fac(dim-1)+" möglichen)");
		System.out.println(actTourToString());
	}
}