package algo;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.HashSet;





//XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
// Klasse fuer den Algorithmus von Floyd-Warshall
//XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
public class Floyd_Warshall {

	static double[][] DISTANZ; 	//   Distanz-Matrix
	static Integer[][] VORGANGER; 	//   Vorgaenger-Matrix


//     * filetointarray: Werte aus Datei (dat) werden gelesen und Graph wird in Array gelegt
//     *
//     * @param dat - eine Datei mit int-Werten:
//     * 				1.Reihe: Knotenanzahl -->n
//     * 				2.Reihe: Kantenanzahl -->m
//     * 				3.Reihe0: (m+2)e Zeile--> Endknoten der Kante und das Kantengewicht
//     *
//     *
//     * @return Array aus Graphen von dat:
//     * -->Jedes Teil des Arrays hat ein Array mit 3 Zahlen
//     * -->Teil 0 hat Knotenzahl und Kantenzahl (Index 0 und 1)
//     * -->Teil 1 hat Kanten (u,v)
//

	static Integer[][] filetointarray(String dat) {
		Integer[][] A = null;
		FileInputStream fis = null;
		try {
			fis = new FileInputStream(dat);
		} catch (Exception e) {
			System.out.println(dat + " konnte nicht geoeffnet werden");
			System.out.println(e.getMessage());
		}
		try {
			InputStreamReader isr = new InputStreamReader(fis);
			BufferedReader br = new BufferedReader(isr);

			// Knotenanzahl lesen
			String einZeile;
			einZeile = br.readLine();
			Integer n = new Integer(einZeile);

			// Kantenanzahl lesen
			einZeile = br.readLine();
			Integer m = new Integer(einZeile);
			A = new Integer[m + 1][3];

			// Knoten- und Kantenanzahl -> Array
			A[0][0] = n;
			A[0][1] = m;

			// Kanten lesen
			for (int i = 1; i <= m; i++) {
				einZeile = br.readLine();
				Integer sepIndex1 = einZeile.indexOf(' ');
				Integer sepIndex2 = einZeile.indexOf(' ', sepIndex1 + 1);
				String vStr = einZeile.substring(0, sepIndex1);
				String uStr = einZeile.substring(sepIndex1 + 1, sepIndex2);
				String wStr = einZeile.substring(sepIndex2 + 1, einZeile.length());
				Integer v = new Integer(vStr);
				Integer u = new Integer(uStr);
				Integer w = new Integer(wStr);
				if (!(u >= 0 && u < n && v >= 0 && v < n))
					throw new Exception("Knotennummer nicht korrekt");
				A[i][0] = v;
				A[i][1] = u;
				A[i][2] = w;
			}
		} catch (Exception e) {
			System.out.println("Einlesen nicht möglich");
			System.out.println(e.getMessage());
		}

		return A;
	}












//	 * Floyd-Warshall Algorithmus zum bestimmen des kürzesten Weges und des Vorgängers
//	 *
//	 * @param G - der zu untersuchende Graph
//	 * gibt false zurück, wenn es negativen zyklus hat, sonst gibt er true zurück
//	 *
//	 * Aktion   - vorgänger/distanzmatrix bestimmen und zeigt sie
//	 *
//

	static boolean floydalgorithmus(Integer[][] G) {

		//  Knoten-ID mit 0,...,n indizieren

		HashSet<Integer> vertexIds = new HashSet<Integer>();
		// Knoten-ID sammeln
		for (Integer[] reihe : G) {
			if (reihe == G[0]) continue;
			vertexIds.add(reihe[0]);
			vertexIds.add(reihe[1]);
		}

		//   Knoten-IDs aufsteigend sortieren
		Object[] sort0 = vertexIds.toArray();
		int[] sortie = new int[sort0.length];
		for (int i = 0; i < sortie.length; i++) {
			sortie[i] = (int) sort0[i];
		}
		MergeSort.mergesort(sortie, 0, sortie.length - 1);

		// Knoten IDs bezeichnen von 0 ...n
		for (int i = 0; i < vertexIds.size(); i++) {
			for (Integer[] reihe : G) {
				if (reihe[0] == sortie[i]) reihe[0] = i;
				if (reihe[1] == sortie[i]) reihe[1] = i;
			}
		}
	   //danach--> Jetzt von 0,...,vertexIds.size()-1


		// Distanz/Vorganger-Matrix mit MAX_VALUE / null initialisieren
		DISTANZ = new double [G[0][0]][G[0][0]];
		VORGANGER = new Integer[G[0][0]][G[0][0]];

		for (int i = 0; i < DISTANZ.length; i++) {
			for (int j = 0; j < DISTANZ[i].length; j++) {
				DISTANZ[i][j] = Double.MAX_VALUE;
				VORGANGER[i][j] = null;
			}
		}

		// Vorgaenger/ Distanzen löschen ausm Graphen
		for (int i = 1; i < G.length; i++) {
			DISTANZ[G[i][0]][G[i][1]] = G[i][2];
			VORGANGER[G[i][0]][G[i][1]] = G[i][0];
		}



		// IDs zurück benennen
		for (Integer i = 0; i < vertexIds.size(); i++) {
			for (Integer[] reihe : G) {
				if (reihe[0] == i) reihe[0] = sortie[i];
				if (reihe[1] == i) reihe[1] = sortie[i];
			}
			for (Integer[] reihe : VORGANGER) {
				for (Integer j = 0; j < reihe.length; j++) {
					if (reihe[j] == i) reihe[j] = sortie[i];
				}
			}
		}
		// IDs haben jetzt alten Namen

		// Ausgabe der Graphen /  Distanz / VorgaangerMatrix
		zeichnegraph(G);
		System.out.println("\n");
		System.out.println("Ursprungsmatrizen: \n");

		printDISTANZ(DISTANZ);
		System.out.println();
		printVORGANGER(VORGANGER);
		System.out.println();

		// Hauptaufgabe -->Distanz/ Vorgaenger-Matrix bestimmen
		for (int k = 0; k < DISTANZ.length; k++) {
			for (int i = 0; i < DISTANZ.length; i++) {
				for (int j = 0; j < DISTANZ.length; j++) {
					if (DISTANZ[i][j] > DISTANZ[i][k] + DISTANZ[k][j]) {
						DISTANZ[i][j] = DISTANZ[i][k] + DISTANZ[k][j];
						VORGANGER[i][j] = VORGANGER[k][j];
					}
				}
			}
			// Fehlermeldung wenn Zyklus negativ ist
			if (DISTANZ[k][k] < 0.0) {
				System.out.println("Negativer Zyklus");
				return false;
			}
		}

		// Ausgabe End- Distanz/Vorgaenger
		System.out.println("Endmatrizen \n");
		System.out.println("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX");
		printDISTANZ(DISTANZ);
		System.out.println();
		printVORGANGER(VORGANGER);
		System.out.println();
		return true;
	}




















//	 * Methode für Ausgabe Graph
//	 *
//	 * @param g - Graph, der angezeigt wird

	static void zeichnegraph(Integer[][] g) {

		System.out.println("Graph der Matrix");
		System.out.println("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX");

		for (Integer[] reihe : g) {
			// Erste Zeile wird ignoriert, da nur knoten/kantenzahl

			if (reihe == g[0]) continue;
			for (Integer c : reihe) {
				System.out.printf(" %5d ", c);
			}
			System.out.print("\n");

		}
		System.out.println("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX");
	}















//	 * Methodeum Vorgangermatrix anzuzeigen
//	 *
//

	static void printVORGANGER(Integer[][] vorganger) {

		System.out.println("Die UrsprungsMatrix");
		System.out.println("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX");
		for (Integer[] reihe : vorganger) {
			for (Integer c : reihe) {
				// Bei (noch) nicht bekanntem Vorgaenger:
				if (c == null) System.out.printf(" %5s ", "?");
				else {
					System.out.printf(" %5d ", c);
				}
			}
			System.out.print("\n");
		}
	}













//	 * Methode um Distanzmatrix anzuzeigen

	static void printDISTANZ(double[][] dist) {

		System.out.println("Distanz der Matrix");
		System.out.println("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX");

		for (double[] reihe : dist) {
			for (double c : reihe) {
				// Bei  nicht bekannten Distanzen: (Inf. -> Infinity)
				if (c == Double.MAX_VALUE) System.out.printf(" %5s ", "∞");
				else {
					System.out.printf(" %5.1f ", c);
				}
			}
			System.out.print("\n");
		}
	}

	static public void main(String[] args) {

		// Beispieltest aus Vorlesung
		Integer[][] G1 = filetointarray("graphwfw.txt");
		floydalgorithmus(G1);



	}
}