/*************************  Graph_TopoSort.java *******************************/

/** Topologisches Sortieren eines gerichteten Graphen                         */

public class Graph_TopoSort {                   // Klasse mit einer Methode 

  public static int[]sort (Graph g){            // zum topologischen Sortieren 
  
    int i, j;                                   // Knotennamen 
    int id=0;                                   // Nummerierungsvariable
    int[]indegree = new int[g.number()];        // Vektor mit Eingangsgraden
    int[]ergebnis = new int[g.number()];        // Vektor fuer Ergebnis

    for (i=0; i<g.number(); i++) indegree[i]=0; // setze indegree auf 0

    g.reset();                                  // setze Adjazenzlisten zurueck 
    for (i=0; i<g.number(); i++) {              // fuer jeden Knoten i
      while (g.moreNeighbors(i)) {              // solange er Nachbarn hat 
        j = g.nextNeighbor(i);                  // hole Namen des Nachbarn
        indegree[j]++;                          // erhoehe dessen Eingangsgrad
      }
    }

    Schlange s = new ArraySchlange(g.number());// besorge eine Schlange
    
    for (i=0; i< g.number(); i++)               // jeder Knoten
      if (indegree[i]==0)                       // mit Eingangsgrad 0
        s.enq(new Integer(i));                  // kommt in die Schlange

    while (!s.empty()) {                        // solange Schlange nicht leer
      i = ((Integer)s.front()).intValue();      // hole Knoten aus Schlange
      ergebnis[id++]=i;                         // vergib naechste ID
      g.reset(i);                               // setze Knoten i zurueck
      while (g.moreNeighbors(i)){               // solange i Nachbarn hat
        j = g.nextNeighbor(i);                  // holen Namen des Nachbarn
        indegree[j]--;                          // erniedrige den Eingangsgrad
        if (indegree[j]==0)                     // falls Eingangsgrad jetzt 0
          s.enq(new Integer(j));                // Knoten in Schlange stellen 
      }
    }
    if (id==g.number())                         // falls genuegend IDs vergeben 
                   return ergebnis;             // gib Ergebnis zurueck 
                   else return null;            // sonst gib null zurueck
  }
}