package dap2.blatt3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Pseudocode des DFS Algorithmus:
 * 
 * Iteriere über alle Knoten i mit 0<= i < n
 * 	   Falls Knoten i nicht besucht ==> DFS(i,-1)
 * 
 * DFS(aktuellerKnoten, vorgaengerKnoten):
 * 
 * Inkrementiere besuche[aktuellerKnoten], falls vorgaengerKnoten =! -1
 * 
 * 1. Fall:
 * Wenn besuche[aktuellerKnoten]=1 ==> 
 * prüfe ob aktuellerKnoten SG-Kandidat (Siehe unten) und setze 
 * sackgassenEndpunkt[aktuellerKnoten] auf Ergebnis
 * 
 * Iteriere über alle v in Adj(aktuellerKnoten)
 * 		DFS(v,aktuellerKnoten)
 * 
 * 2. Fall:
 * Wenn besuche[aktuellerKnoten]>1 ==>
 * Anz. eingehender Kanten > 1 ==> sackgassenEnpunkt[aktuellerKnoten] = false;
 * 
 * 3. Fall: (für den ersten DFS Aufruf)
 * Wenn besuche[aktuellerKnoten]=0 ==>
 * 
 * Iteriere über alle v in Adj(aktuellerKnoten)
 * 		DFS(v,aktuellerKnoten)
 * 
 * 
 * Prüfung, ob Knoten SG-Kandidat ist:
 * 
 * Falls |Adj(Knoten)|=1 und 
 * Knoten in Adj(w) wobei w in Adj(Knoten) 
 * 
 * -- sprich: der Knoten hat nur eine ausgehende Kante
 * und der einzige direkte Nachfolger hat eine Kante
 * auf den Knoten selbst.
 * 
 * ==============================================================================
 * 
 * Pseudocode des Turnaround Algorithmus:
 * 
 * // Erzeuge neuen Graphen mit umgedrehten Kanten
 *    Iteriere ¨uber alle Knoten v 2 V :
 *    	Iteriere ¨uber alle Knoten w 2 Adj1(v):
 *    		fuege v in Adj2(w) ein
 *    
 * // Vergleiche Adj1 mit Adj2
 *    Iteriere ¨uber alle Knoten v 2 V :
 *    	Falls Adj1(v).size == 1 und Adj2(v).size == 1 und w1 = w2
 *    		(mit w1 2 Adj1(v) und w2 2 Adj2(v))
 *    			dann ist v Sackgassenendpunkt
 *
 */
@SuppressWarnings("unchecked")
public class Sackgasse {

	private static final int n = 5;	
	private static int[] besuche = new int[n];	
	private static boolean[] sackgassenEndpunkt = new boolean[n];			
	private static List<Integer>[] adjazenzListe = new ArrayList [n]; 			
	private static List<Integer>[] adjazenzListeUmgedreht = new ArrayList[n];
			
	/*
	 * Beispielgraph:
	 *             -> 0   ->4---
	 *             \  |  / 		 \
	 *              \ v / 		  |
	 *                1 <-----    |
	 *               /       |    |
	 *              /        |   /  
	 *              -> 2 --> 3 <-
	 */
	
	public static void initBeispielGraph(){		
		adjazenzListe[0] = new ArrayList<Integer>();		
		adjazenzListe[0].add(1);		
		adjazenzListe[1] = new ArrayList<Integer>();		
		adjazenzListe[1].add(2);
		adjazenzListe[1].add(4);
		adjazenzListe[1].add(0);
		adjazenzListe[2] = new ArrayList<Integer>();
		adjazenzListe[2].add(3);
		adjazenzListe[3] = new ArrayList<Integer>();
		adjazenzListe[3].add(1);
		adjazenzListe[4] = new ArrayList<Integer>();
		adjazenzListe[4].add(3);
	}
	
	public static void init(){		
		Arrays.fill(besuche, 0);
		
		for (int i= 0; i<n; i++){
			adjazenzListeUmgedreht[i] = new ArrayList<Integer>();
		}
	}
	
	/**
	 * Prüfung auf:
	 * Aktueller Knoten hat nur eine ausgehende Kante
	 * 						und 
	 * die einzige ausgehende Kante zeigt auf den Vorgänger 
	 * == > Kandidat für das Ende einer Sackgasse
	 *
	 * @param knotenIndex ist der Index des aktuell betrachteten Knotens.
	 * @return
	 */
	private static boolean istSGEndpunktKandidat(int knotenIndex, int vorgaengerKnotenIndex){
						
		return (adjazenzListe[knotenIndex].size()==1 &&
				adjazenzListe[knotenIndex].get(0)==vorgaengerKnotenIndex);
		
	}
	
	/**
	 * Rekursiver DFS, der einen Knoten als besucht markiert, falls er über eine Kante erreicht worden ist.
	 * Für jeden Knoten wird die Anzahl der Besuche gezählt. Sollte die Anzahl > 1 sein (Fall 2), so stellt dies
	 * ein Rekursionsende dar. Für die Nachfolger des Knotens wird kein DFS mehr gestartet.
	 * 
	 * Wird ein Knoten zum ersten mal besucht (über eine Kante - Fall 1), so wird zunächst geprüft,
	 * ob der Knoten ein Sackgassenkandidat ist und der Kandidatenstatus in einem Array gespeichert. 
	 * Anschließend wird für jeden Knoten in der Adjazenzliste des aktuellen Knotens der DFS gestartet.
	 * 
	 * Sollte die Anzahl der Besuche = 0 sein ( DFS für den Knoten über Main-Schleife gestartet - Fall 3)
	 * so wird lediglich für alle direkten Nachfolger des Knotens der DFS gestartet.
	 * Der Knoten muss nicht weiter ausgewertet werden, da jeder Knoten mindestens eine eingehende Kante 
	 * (in einem gültigen Straßennetz) hat
	 * und daher irgendwann über die DFS-Graphtraversierung erreicht werden wird.
	 * 
	 * @param aktuellerKnotenIndex ist der Index des aktuell betrachteten Knotens.
	 * @param vorgaengerKnotenIndex ist der Index des zuvor betrachteten Knotens.
	 */
	private static void DFS(int aktuellerKnotenIndex, int vorgaengerKnotenIndex){		
						
		if (vorgaengerKnotenIndex!=-1)  
			++besuche[aktuellerKnotenIndex]; // inkrementiere den Zähler			
						
		//Fall 1: ueber Graphtraversierung erreicht
		if (besuche[aktuellerKnotenIndex]==1) {											
			sackgassenEndpunkt[aktuellerKnotenIndex] = istSGEndpunktKandidat(aktuellerKnotenIndex, vorgaengerKnotenIndex);																			
			
			for (Integer index : adjazenzListe[aktuellerKnotenIndex]){																							 
				DFS(index, aktuellerKnotenIndex);			
			}

		//Fall 2: Anzahl der eingehenden Kanten > 2, somit Knoten kein SGEndpunkt		
		} else if (besuche[aktuellerKnotenIndex]>1){ 			
			sackgassenEndpunkt[aktuellerKnotenIndex] = false; // Rekursionsende! 

		//Fall 3: Anzahl der Besuche == 0 ==> DFS ueber Mainschleife	
		} else {     											
			for (Integer index : adjazenzListe[aktuellerKnotenIndex]){									 
				DFS(index, aktuellerKnotenIndex);				
			}
		}
				
	}
	
	public static void SGEndpunktDFS(){
		for (int i = 0; i<adjazenzListe.length; i++){						
			if (besuche[i]==0) DFS(i,-1);			
		}
	}
	
	/**
	 * Drehe Kanten um (vgl. TopSort).  
	 * @param knotenIndex des aktuell betrachteten Knotens
	 * @param adjazenzListe des aktuell betrachteten Knotens
	 */
	private static void dreheKantenUm(int knotenIndex, List<Integer> adjazenzListe){		
				
		for (int i = 0; i<adjazenzListe.size(); i++){								
			adjazenzListeUmgedreht[adjazenzListe.get(i)].add(knotenIndex);			
		}
		
	}
			
	public static void SGEndpunktTurnAround(){
		
		/*
		 * erzeuge umgedrehte Liste
		 */
		for (int i = 0; i<adjazenzListe.length; i++){			
			dreheKantenUm(i, adjazenzListe[i]);			
		}
				
		for (int i = 0; i<adjazenzListe.length; i++){	
			
			if (adjazenzListe[i].size()==1 && 
					adjazenzListeUmgedreht[i].size()==1 && 
						adjazenzListe[i].get(0)==adjazenzListeUmgedreht[i].get(0)){				
				sackgassenEndpunkt[i] = true;				
			}			
		}
	}
	
	public static void gibAus() {
		System.out.println("Gefundene Sackgassenendpunkte:");
		for (int i = 0; i < sackgassenEndpunkt.length; i++) {
			if (sackgassenEndpunkt[i]) System.out.println(i);
		}
	}
		
	public static void main(String[] args) {
		
		/*
		 * Initialisierung
		 */
		init();
		initBeispielGraph();
		
		// wahl das Algos:
		boolean algo1  = true;
		
		if (algo1)
			SGEndpunktDFS(); // Algo 1
		else
			SGEndpunktTurnAround(); // Algo 2		
		
		gibAus();
	}
	
}