/************************* TopoSort.java **************************************/

import java.util.*;

/** Topologisches Sortieren eines gerichteten Graphen                         */
/*  Verwendet wird eine Schlange, welche die Knoten aufnimmt,                 */
/*  deren Eingangsgrade auf 0 gesunken sind                                   */

public class TopoSort {

  public static void sortGraph ( Graph g) {

    for (Vertex v : g.vertices()){     // fuer jeden Knoten 
      v.indegree = 0;                  // setze seinen Eingangsgrad auf 0
      v.nr = -1;                       // vergib ungueltige Nummer
    }

    for (Vertex v : g.vertices())      // fuer jeden Knoten
      for (Edge e : v.edges)           // fuer jeden Nachbarknoten
        e.dest.indegree++;             // erhoehe seinen Eingangsgrad um 1

    List<Vertex> l                     // Liste von Knoten, die 
       = new LinkedList<Vertex>();     // inzwischen den Eingangsgrad 0 haben

    for (Vertex v : g.vertices())      // jeden Knoten mit Eingangsgrad 0 
      if (v.indegree==0) l.add(v);     // fuege hinten in die Liste ein 

    int id = 0;                        // initialisiere Laufnummer
    while (!l.isEmpty()) {             // solange Liste nicht leer
      Vertex v = l.remove(0);          // besorge und entferne Kopf aus Liste 
      v.nr = id++;                     // vergib naechste Nummer
      for (Edge e : v.edges){          // fuer jede ausgehende Kante
        Vertex w = e.dest;             // betrachte den zugehoerigen Knoten
        w.indegree--;                  // erniedrige seinen Eingangsgrad
        if (w.indegree==0)             // falls der Eingangsgrad auf 0 sinkt
          l.add(w);                    // fuege Knoten hinten in Liste ein
      }
    }
  }
}