/************************** 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
    int entschieden = 0;                  // 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 == 0) {            // solange noch nicht entschieden
      iter = s.peek();                    // oberster Adjazenz-Iterator
      int verlaengerbar=0;                // bisher keine weiteren gefunden
      while (verlaengerbar==0) {          // solange keine weiteren gefunden
        if (iter.hasNext()) {             // falls es weiteren Nachbarn gibt
          Edge e = (Edge)iter.next();     // e ist naechste Kante
          v = e.dest;                     // v ist potentielle Verlaengerung
          if (!v.seen) verlaengerbar=1;   // Verlaengerung gefunden
        } else verlaengerbar=-1;          // keine Verlaengerung moeglich
      }
      if (verlaengerbar==1) {             // 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 = 1;                // 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=-1;    // endgueltig keinen Kreis gefunden
      }
    }
    if (entschieden ==-1 ) return null;   // kein Kreis gefunden               
                      else return v;      // liefere letzten Knoten des Kreises
  }
}