Video 11-9: Topologisches Sortieren

0:01 Als nächstes schauen wir uns die topologische Sortierung an. Unter dem Begriff können Sie sich vielleicht nicht viel vorstellen. Sie werden aber gleich in die in der Anwendung sehen, die dahinter steckt, dass das ein sehr intuitives und nahliegendes Problem ist und dass es unbedingt gerichtete Kanten braucht, damit es Sinn ergibt. Äh z.B. könnte man es beschreiben als eine ähm als einen Scheduling Problem. Ich möchte also gewisse Aufgaben erledigen und die haben ähm Bedingungen, was ich vor was ich zuerst erledigen muss. Äh Klassiker könnte sein, ich habe Module in einem Studiengang und die haben auf Voraussetzungen, das heißt, ich muss eins bestanden haben, bevor ich das nächste machen kann. Klammer auf haben wir möglichst wenig davon, weil man dann äh den, wenn man das hart als Voraussetzung äh deklariert, viel Probleme mit anderen Nebenfächern und so bekommt. Aber äh grundsätzlich inhaltliche Voraussetzungen gibt's ja dann doch. Das heißt, eine empfohlene Reihenfolge müsste zumindest dafür sorgen, dass manche äh Constraints eingehalten sind. Also hier z.B. ist gemalt eine Kante von 6 zu 0. Das bedeutet äh Advanced Programmings braucht Algorithms als Voraussetzung.

1:17 Ist das so rum gemeint? Andersrum, ne? Algorithms braucht Advanced Programming. Advanced Programming klingt schon so Advanced, aber ich glaube, sie meinen das so rum. äh und umgekehrt 2 und 5 und 1, also Artificial Intelligence, Scientific Computing und Complexity Theory, wollen, dass sie vorher Algorithms gehört haben. Das sind die Beispiele jetzt aus Princeton. Wir haben natürlich andere Module. Was man letztlich ähm immer dahinter hat, ist ein gerichteter Graf, indem es eine Kante von einer Aufgabe zu den anderen gibt, wenn ich die zuerst erledigen muss.

1:55 Und die Frage ist, gibt es eine Möglichkeit, diesen Graf so anzuordnen, in eine lineare Ort Reihenfolge zu bringen, dass ich ein Modul nach dem anderen hören kann, ohne jemals äh zyklische Abhängigkeiten zu haben? Und äh hier gibt's so eine Reihenfolge, indem ich bei der 3 anfange, dann zur sechs und dann so weiter. Und sie sehen, alle Kanten führen nach oben. Das heißt, wenn ich das ähm der Zeit entsprechend von unten nach oben abarbeite, dann habe ich nie eine nicht erfüllte Voraussetzung. Okay, natürlich geht das nicht immer. Ähm, ich kann auch Beispiele haben, in denen es eine zyklische Abhängigkeit gibt. Und in dem Fall kann es keine solche Anordnung geben. Egal, wo ich anfange, ich habe immer eine Aufgabe, die davorkommen sollte, dann habe ich ein Problem, sollte für ein Studiengang nicht vorkommen. Ähm, hier ist es natürlich irgendwie offensichtlich, jede äh solche, das nennt man dann eine topologische Sortierung, also eine Sortierung, in der das eindimensional geworden ist und alle Kanten nach vorne oder nach oben gehen.

3:06 Jede solche topologische Sortierung muss irgendwo anfangen. Das heiß, es muss immer einen Knoten geben, der keine eingehende Kante hat. Klar. Ähm, ich kann aber hier diesen Graf ein bisschen modifizieren, so dass der einen Knoten hat, der keine eingehende Kante hat. Und trotzdem hat er natürlich diese zyklische Abhängigkeit hier. Das heißt, das bringt mir gar nichts. Das ist aber jetzt erstmal nicht mehr so ganz offensichtlich zu erkennen. Ich kann nicht Knoten für Knoten durchprüfen und sagen, ähm ja, hier gibt's einen, mit dem ich anfangen könnte, also passt schon. Was dahinter steckt, ist letztlich ähm genau die Frage, gibt es einen gerichteten Kreis?

3:45 Wenn es einen gerichteten Kreis gibt, dann habe ich ein Problem. Die Frage ist, ist das denn auch umgekehrt dann das einzige Problem? Also sozusagen, wenn ein Graf keinen gerichteten Kreis hat, gibt's dann immer sowas?

4:14 Äh, das Umgekehrte nennt man dann einen Dag. einen directed accelic Graph. Das hat einen extra Namen, auch wenn das nur so eine unschöne ähm Abkürzung ist, weil die viel vorkommen. Also ein gerichteter azzyklischer Graf.

4:49 Also ich denke es ist nicht vollkommen offensichtlich, ob das hinreichend ist. Also kein gerichteter Kreis bedeutet, ich kann so eine topologische Sortierung finden. Wie würde man das beweisen? Am schönsten konstruktiv, also mit einem Algorithmus. Genau das werden wir jetzt machen. Wir werden einen Algorithmus angeben, der entweder so einen gerichteten Kreis findet oder eine topologische Satierung ausgibt und damit noch die Frage beantwortet. Das ist tatsächlich das einzige Hindernis, das gegen eine topologische Sattierung spricht, ist ein gerichteter Kreis irgendwo. Und den Algorithmus, den wir dafür wenden, den kennen Sie schon, der heißt Tiefensuche. Und ähm schockierenderweise müssen wir gar nicht viel im Code ändern, um diesen Algorithmus ähm zu realisieren. Das hier ist jetzt erstmal die Einstiegsversion, die ähm diese topologische Sortierung berechnet. ähm sollte vielleicht korrekter sagen, wir berechnen eine Reihenfolge der Knoten und die Aussage wird sein, entweder ist das eine topologische Sortierung oder es gibt keine. Ja.

6:31 Was ist es für eine mysteriöse Reihenfolge, die wir hier bestimmen? Äh, wir legen ein Stack an, auf der wir das äh das Ding realisieren. Das das heißt Reverse Post order, rückwärts Post order oder inverse invertier. Ja, rückwärts wahrscheinlich am besten inverse klingt klingt gefähr habe ich so gelesen, aber gut. Sag mal die rückwärts gelesene DFS Post order. Wanmeh ich einen Knoten in meiner rekursiven Tiefensuche endgültig verlasse, also alle seine ausgehenden Kanten sind auch rekursiv besucht, dann füge ich diesen Knoten hinzu. Deswegen heißt das Ding Post order. Ich mache erst alles mit einem Knoten und dann besuche ich den Knot Knoten. Packe ihn also in meine Reihenfolge. Da das Ganze ein Stack ist, dreht der die Reihenfolge von alleine um, wenn ich es hinterher auslese. Ähm, das ist alles, was dit mit mit diesem Reverse gemeint ist. Und äh überraschenderweise vielleicht ist das ausreichend. Entweder das ist eine topologische Sortierung oder es gibt keine Beispiel. Ähm, wir müssen ja immer einen Knoten haben, der keine eingehenden Kanten hat, um anzufangen.

7:48 Also, ein erster Schritt wäre zu prüfen, ob dieses diese Poster rückwärts gelesen diese Eigenschaft erfüllt. Hier ist die Post Order gelistet. Also, ich fange bei Knoten null an und ähm ich nehme an, die Kanten sind sortiert, verfolgt worden. Das heißt, ich mache einen rekursiven Aufbruch von hier nach hier nach hier. Die vier hat keine ausgehenden Kanten, das heißt, ich bin mit dem fertig und kehre zurück. An dem Zeitpunkt wird die vier in die Post order eingefügt. Das heißt, hier ist die vier deshalb gelandet. Und dann gehe ich zur eins zurück. Die hat keine ausgehenden Kanten. Das wä die ein dann das nächste. So wird die Poster bestimmt und jetzt drehen wir die um. Die Behauptung ist, das ist eine gültige topologische Sortierung, wenn es überhaupt eine gibt. In dem Fall äh sehen Sie, es gibt keinen gerichteten Kreis so optisch. Und tatsächlich ist die drei ein Knoten, mit dem ich anfangen kann. Die hat keine eingehenden Kanten.

8:57 Äh der Knoten davor, die sechs, wenn es Kanten gäbe, dann ähm nur von der drei, denn äh die drei war sozusagen das let den letzten Knoten, den ich abgeschlossen habe, von dem kann es keine weiteren äh Kanten mehr geben. Na ja, ein bisschen besser sieht man das, wenn man ähm von dieser Tiefensuche einen expliziten Trace aufmalt. Also hier ist äh der Aufruf gestartet. Dann gebe ich dieses DFS mit dem Knoten aus und ich gebe aus, wenn ich den rekursiven Aufruf verlasse und es ist äh eingerückt, dass man sieht, welcher Aufruf welchen äh bedingt hat.

9:42 Und der das korrekte Argument, warum diese DFS Post Order, die Reihenfolge, die wir daraus bekommen, tatsächlich eine topologische Sortierung ist, zumindest äh wenn es eben keinen gerichteten Kreis gibt. Der und er teilt sich in diese drei Fälle. Ähm, entweder habe ich den, also wenn man sich irgendeine Kante anschaut, dann muss die Kante anschaulich immer von früh zu spät gehen. Ich darf keine Kanten zurück in die Vergangenheit haben. Wenn der Knoten ähm W vor dem Knoten V schon abgehandelt wurde, dann würde ich da gar nicht mehr reinspringen. Und dann ist der Knoten W in der Post Order vor dem Knoten V. Das heißt, in der Reverse Post Order ist der Knoten W nach dem Knoten V. Die Kante zeigt vorwärts in der Zeit. Passt. Also das ist der einfachste Fall. Äh, der zweite Fall ist, wir haben den Aufruf für W noch gar nicht gestartet, wenn wir diese Kante jetzt im Aufruf von DFS bei V finden.

10:53 In dem Fall machen wir diesen Aufruf jetzt oder äh zumindest indirekt. Es könnte auch sein, dass wir erst eine andere Kante verfolgen. Ähm, wie dem auch sei, würden wir dann aber äh da das ein atzyklischer Graf ist, ähm diesen Knoten zuerst abschließen und dann zu dem W zum V zurückkehren. Das heißt, W ist wieder in der Poster vor V und in der umgekehrten Poster nach V. Also passt auch wieder. Der dritte Fall ist, wir haben irgendwie angefangen, den Aufruf zu W zu machen und ähm sind dann bei V gelandet. Und das wäre aber ein Widerspruch, wenn das auftritt, dann haben wir einen Kreis gefunden, denn dann gibt es einen Weg ähm auf dem Stack. Der Ariatnefaden liegt von W zu V. Und wir finden jetzt eine Kante von V zu W. Das ist genau ein Kreis.

12:03 Schauen wir uns das noch mal ähm an dem kleinen Beispiel an. Ähm erstmal in einem, wo es auch gut geht. Also, das hier ist ein einzyglicher Graf. Ich fange bei der Null an.

12:27 und mach mal eine Tiefensuche nach dem gleichen Muster. Stopp, stopp, stopp. wie vorhin. Ähm und statt den äh Aufrufen, wann habe ich einen Aufruf gestartet, wann habe ich ihn beendet, malen wir den Stack und die Zeit, die in Knoten auf dem Stack verbringt. Okay, ich muss das etwas kleiner machen, um das alles drauf zu kriegen.

12:56 Also noch mal etwas langsamer. Ähm, ich fange an mit dem Knoten null Step wollte ich machen. Den packe ich auf meinen Stack. Der liegt jetzt hier und ist Teil von meinem Ariatne Faden durch den Graf. Dann verfolge ich den nächsten Knoten. Der den packe ich jetzt auch auf den Stack. Dann verfolge ich von dem wieder eine Kante. Dann kommt die drei auch auf den Stack und so weiter und so fort. Bis ich das erste Mal bei einem Knoten angekommen bin, den ich abschließen kann. 6 hat keinerlei ausgehende Kanten. Das heißt, der wird jetzt direkt als abgeschlossen markiert. Also, die Farben bedeuten, ne, blau, äh grau heißt, ich habe den noch nicht erreicht, habe noch keinen Aufruf dort gestartet. Rot heißt, ich habe einen aktuellen Aufruf am laufen und der ist noch nicht abgeschlossen. Und grün heißt, ich habe den schon erreicht und der rekursier der Aufruf dort ist zu Ende. Das heißt, dieser Knoten ist schon in die Poster eingefügt worden.

13:49 Und die sechs ist jetzt an dieser Stelle fertig. Das heißt, wir haben hier den die Markierung für die Post order. Können Sie vielleicht gerade noch sehen hier unten.

14:01 Dann ist die fünf auch fertig. Der hat nur diese ausgehende Kante nach oben gehabt. Damit machen wir die fünf zu. Dann ist die drei auch fertig. Hat auch keine ausgehenden Kanten mehr. Von der ein gibt's aber noch ausgehende Kanten. Das heißt, wir gehen jetzt zur vier, packen die auf den Stack und da gelbe es jetzt noch mal eine Kante zur fünf. Die fünf ist aber schon als besucht markiert. Da passiert dann nichts mehr. Gleiches Spiel wie in Tiefensuche bevor wie vorher. Ähm über diese Klassifizierung der Kanten, die können Sie erstmal ignorieren. Die benutzen wir hier nicht. äh vier ist damit auch fertig, dann komme ich zurück und von der Null gibt's noch eine Kante zur zwei und ähm keine wei weiteren ausgehen Kanten bin ich hier auch zurück. Und alles, was man über die Tiefensuche verstehen muss, ist eigentlich in diesem über die zeitgemalten Stack abzulesen. Insbesondere gibt's diese Poster, die genau daraus entsteht, wann der Balken für einen Knoten endet.

14:57 Sie können sich leicht überlegen, ähm dieses Bild muss immer so aussehen, dass ein Knoten, der zuerst in den Stack kommt, auch nach einem Knoten wieder rauskommt, der sozusagen auf seinem Balken eingefügt wird. Das liegt einfach an dem rekursiven Aufruf. Ich habe ja aus dem Aufruf hier für die 0, den Aufruf für die 1 gestartet. Ich kann den Aufruf für null nicht beenden, bevor die rekursive Funktion zurückkehrt. Und das gilt natürlich geschachtelt auch für alle anderen.

15:34 Okay. Und ähm diese Reihenfolge rückwärts gelesen gibt uns eben dann die topologische Sortierung. Ah, ich wollte Ihnen den Kreis zeigen. Das war noch der Punkt. Ähm, was passiert, wenn wir einen gerichteten Kreis haben?

15:52 Ich fange hier beim Knoten null an. Das erste ähm der erste Teil ist so wie gehabt. Ich finde irgendwelche Knoten, packt der auf den Stack und jetzt finde ich an dieser Stelle eine Kante, das im letzten Beispiel nie vorkam. Eine Kante zurück zu einem Knoten, der noch rot ist. Wir hatten vorher auch Kanten, aber zu Knoten, die schon als grün markiert waren, die also komplett fertig sind. Das ist kein Kreis, denn da bin ich hin und wieder zurückgelaufen. Da gibt's dann nicht unbedingt eine Kante noch auf dem Stack. Hier habe ich jetzt aber direkt auf dem Stack einen Weg von 0 zu 3 über die 1 und ich habe jetzt einen Weg von der 3 zurück zu 1. Das heißt, hiermit habe ich einen Kreis gefunden. Und sie sehen an der Stelle auch, ich kann erkennen, wann ich diese Situation habe, wenn ich mir äh merke zusätzlich, welche Knoten sind aktuell auf dem Stack. Also, wir hatten bisher nur markiert als besucht, das heißt nicht mehr grau. Wir brauchen einen zweiten Zustandsunterscheidung zwischen rot und grün.

16:55 Wenn wir uns aber merken, wer schon grün war und wer noch rot ist oder eine der drei Farben, jeder Knoten ist entweder grau, rot oder grün, merken sich ähm was immer äh am bequemsten ist zu implementieren. Wenn ich einen Knoten erreiche mit einer Kante, der aktuell rot ist, dann habe ich immer einen Kreis gefunden. Ich aufhören.

17:16 Also noch mal hier ähm, wenn Sie wenn sie schauen, jede Kante, die zu einem Knoten führt, den wir schon gesehen haben, dann führt die zu einem grünen Knoten und ich habe nie einen Fah zurück zu einem roten.

17:38 Okay. Und hier ist ein bisschen, wenn man die Fälle unterscheidet, dann kann man sich genau diese drei Möglichkeiten überlegen. Ähm dementsprechend ist die einzige Option übrig bleibt, dass wir eben diese Post Order finden. Und was ich im Beispiel eben schon gezeigt hatte, ist wenn dieses äh wenn dieser Algorithmus läuft und er jemals diese Rückwärtskante findet zurück in den Stack, dann kann er auch direkt einen Kreis ausspucken als als sozusagen als äh Zertifikat. Der Graf, den du mir da gegeben hast, der hat einen Kreis, den kann man nicht topologisch sortieren. Äh, ich bin nicht schuld. Okay. Und äh viele XKcD ähm Zitate, die hier natürlich einfach so ein bisschen selbstironisch gemeint sind. Also wann immer ich so einen so einen Kreis habe, funktioniert es nicht. eine sehr etwas sinnvollere Anwendung, die auch wiederum der Java Compiler implementiert ist, wenn Klassen voneinander erben, dann habe ich auch so einen, dann möch kann ich keine Zykel erlauben und der Java Compiler äh haut ihn das entsprechend in die Ohren, falls sie das so hinschreiben. Wenn die direkt so untereinander stehen, ist es natürlich offensichtlich in einem größeren Projekt mit vielen über viele Klassen verteilt. Vielleicht kann einem das schon mal passieren.

18:59 Äh ähnlich auch Excel hat scheinbar sowas eingebaut. Ich das habe ich noch nie ist mir noch nie passiert, dass einem das dann in der echten Anwendung unterkommt, aber theoretisch kann man natürlich Formeln in Excel selbstbezüglich definieren und dann muss das die Software irgendwie erkennen. Äh, sonst gibt's keinen sinnvollen Wert oder womöglich hängt sogar eine Endlusschleife fest. wäre auch nicht ausgeschlossen. Na gut. Äh leichte Verallgemeinerung von dem, was wir eben getan haben, die manchmal auch noch hilfreich ist, ist diese äh hier auf den Folien. Was wir im Wesentlichen verwendet hatten, war der letzte Teil hier, Reverse Post Order. Es gibt auch die nicht umgedrehte, aber es gibt auch die Preorder, in die ich einen Knoten einfüge, wenn ich ihn das erste Mal erreiche. Habt Sie in der Animation vielleicht auch schon gesehen, dass das hier mit eingezeichnet ist? Ähm, ich habe markiert, wann ein Knoten das erste Mal den Stack betritt und das ist dann die Preorder in der Reihenfolge.

20:00 Wenn er den Stack verlässt, in der Reihenfolge, in der die Balken enden, ergibt die Postorder. Dementsprechend rein intuitiv erstmal, wenn ich Preorder habe, dann habe ich im Wesentlichen die diese Historie des Stacks mir gemerkt. Das heißt, wenn dieser Stack irgendwie clevere Dinge tun kann, dann kann ich das mit Pre und Post Order tun.