/************************** Hamilton.java  ************************************/

import java.util.*;

/** sucht einen Hamiltonkreis in einem gerichteten Graphen                    */
/*  verwendet wird ein Keller mit den Adjazenzlisten in Form von Iteratoren   */

public class Hamilton {

  public static Vertex hamilton(Graph g, Vertex start) {
    for (Vertex v : g.vertices()) {       // fuer jeden Knoten
      v.seen = false;                     // noch nicht gesehen
      v.prev = null;                      // noch kein Vorgaenger bekannt
    }
    Iterator iter;                        // Iteratorvariable
    Stack<Iterator> s = new Stack<Iterator>(); // Stack fuer Adjazenz-Iteratoren
    boolean entschieden = false;          // bisher ist noch nichts entschieden
    s.push(start.edges.iterator());       // Nachbarn des Startknoten auf Stack
    start.seen = true;                    // Startknoten gilt als besucht
    Vertex last = start;                  // last ist der zur Zeit letzte Knoten
    int k = 1;                            // Weglaenge = 1

    Vertex v=null;                        // Hilfsknoten
    while (!entschieden) {                // solange noch nicht entschieden
      iter = s.peek();                    // oberster Adjazenz-Iterator
      boolean verlaengerbar=false;        // bisher keine weiteren gefunden
      while (!verlaengerbar && iter.hasNext()) { // solange Hoffnung besteht
        Edge e = (Edge)iter.next();       // e ist naechste Kante
        v = e.dest;                       // v ist potentielle Verlaengerung
        if (!v.seen) verlaengerbar=true;  // Verlaengerung gefunden
      }
      if (verlaengerbar) {                // falls Verlaengerung moeglich 
        k++;                              // erhoehe Weglaenge
        v.seen = true;                    // markiere v als besucht
        v.prev = last;                    // trage last als Vorgaenger ein
        last   = v;                       // v ist jetzt der letzte
        if (k==g.size()&&v.hasEdge(start))// Weg lang genug und Kante zu Start
          entschieden = true;             // endgueltig Kreis gefunden 
        else s.push(v.edges.iterator());  // pushe Nachfolger von v auf Stack
      } else  {                           // keine Verlaengerung moeglich
        s.pop();                          // entferne oberste Adjazenzliste
        last.seen = false;                // last gilt als nicht besucht
        last = last.prev;                 // Vorgaenger ist nun der letzte
        k--;                              // Weglaenge erniedrigen
        if (s.empty()) entschieden=true;  // endgueltig keinen Kreis gefunden
      }
    }
    if (entschieden && s.empty()) 
        return null;                      // kein Kreis gefunden 
        else return v;                    // liefere letzten Knoten des Kreises
  }
}