package dap2.blatt3;

/**
 * Pseudocode des Algorithmus:
 * 
 * Setze p = 0
 * Iteriere über alle KnotenIndizes i mit 0 < i < n
 * 		Falls A[p][i] = 1 -- eine Kante von p nach i existiert
 * 			dann p = i -- p kein SL, aber i Kandidat
 * 
 * p ist Kandidat für SL
 * Falls A[p][p] = 1, dann ist p kein SL (p hat Kante auf sich selbst)
 *  	sonst
 *  		Iteriere über alle Knoten i mit 0 < i < n && i!=p
 *  			Falls !A[i][p] -- sprich: keine Kante von i nach p existiert 
 *  				oder 
 *  				   A[p][i] -- sprich: eine Kante von p nach i existiert   				
 *  				dann ist p kein SL!
 *
 */
public class SchwarzesLoch {
	
	/**
	 * Liefert true, falls schwarzes Loch im übergebenen Graphen gefunden, false sonst.
	 * 
	 * @param adjazenzMatrix Adjazenzmatrix des zu untersuchenden Graphen.
	 * @return true, falls schwarzes Loch gefunden, false sonst.
	 */
	public static boolean hatSchwarzesLoch(boolean[][] adjazenzMatrix ) {
		int potentiellesLoch = 0;
		
		// Finde potentielles schwarzes Loch:
		for (int i = 1; i < adjazenzMatrix.length; i++) {
			if (adjazenzMatrix[potentiellesLoch][i]) {
				potentiellesLoch = i;
			}
		}
		
		if (adjazenzMatrix[potentiellesLoch][potentiellesLoch]){
		// p zeigt auf sich selbst - hat eine ausgehende Kante - ist also kein SL	
			return false;
		} 
		
		// Suche nach Knoten, der nicht auf das schwarze Loch zeigt oder einen
		// Nachfolger des schwarzen Loches
		for (int j = 0; j < adjazenzMatrix.length; j++) {
			if (j != potentiellesLoch
					&& (!adjazenzMatrix[j][potentiellesLoch] || adjazenzMatrix[potentiellesLoch][j])) {
				return false;
			}
		}
		// Potentielles schwarzes Loch bestätigt.
		return true;
	}

	public static void main(String[] args) {
		boolean[][] matrix =getAdjazenzmatrix();
		dumpMarix(matrix);
		System.out.println(hatSchwarzesLoch(matrix));
	}

	/**
	 * Zufällige Erzeugung eines Graphen mit schwarzem Loch.
	 */
	public static boolean[][] getAdjazenzmatrix() {
		int n = 10; // anzahl der knoten
		int hole = 9; // knotennummer des lochs
		boolean[][] adjazenzMatrix = new boolean[n][n];
		for (int i = 0; i < adjazenzMatrix.length; i++) {
			for (int j = 0; j < adjazenzMatrix[i].length; j++) {
				//50% chance für eine Kante
				adjazenzMatrix[i][j] = Math.random() > 0.5;
			}
			adjazenzMatrix[i][hole] = true; // zeige auf das loch
		}
		for (int i = 0; i < adjazenzMatrix.length; i++) {
			adjazenzMatrix[hole][i] = false; // loch zeigt auf keinen
		}
		return adjazenzMatrix;
	}

	public static void dumpMarix(boolean[][] matrix) {
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				System.out.print(" " + (matrix[i][j] ? 1 : 0));
			}
			System.out.println();
		}
	}

}