Video 11-10: Starke Zusammenhangskomponenten

0:02 Im nächsten Abschnitt schauen wir uns noch mal eine Anwendung von Tiefensuche an, die aber ein bisschen weniger direkt auf so einem so einer Traversierung von Grafen beruht. Ein anderes ähm fundamentales Problem auf gerichteten Grafen, nämlich die starken Zusammenhangskomponenten zu finden. Was hat's damit auf sich? Äh, wir hatten bei den ungerichteten Grafen von Zusammenhangskomponenten gesprochen. Also alle Knoten, die irgendwie von einem Pfad verbunden sind, die fassen wir zusammen. Ähm, gibt's auch hier gleich noch mal die der Vergleich. Also, das war die das alte Bild. Wenn ich keine Richtungen auf den Kanten habe, dann ist das eine relativ einfache Sache. Das ist einfach eine Partitionierung der Knoten in Inseln, die irgendwie verbunden sind und zwischen den Inseln gibt's eben nichts. In dem gerichteten Graf macht das nicht so richtig Sinn, denn wir wollen die Kanten ja nur vorwärts verwenden. Das heißt, die die richtige Definition heißt, dass zwei Knoten stark verbunden sind, stark zusammenhängend sind für den Kraftern, wenn es ein Pfad von V zu W, aber auch einen zurück von W zu V gibt.

1:07 Das ist, glaube ich, die natürliche Art, wie man das verallgemeinert. Äh, das ist auch wieder so eine ähm Partitionierung der Knoten. Also die ähm die Komponenten, die Menge von Knoten, die jeweils paarweise stark verbunden sind, bilden wieder eine Partitionierung der Knoten. Also ähnlich kann ich solche grauen Blops malen wie vorher, aber es ist jetzt nicht mehr so einfach wie vorher, dass ich einfach gar keine Verbindung zwischen denen habe, denn das kann einzelne Verbindung geben, nur nicht in beide Richtungen. Und damit ist insbesondere ähm dieses Problem auch ein bisschen komplizierter zu lösen.

1:46 Sieht man hier noch mal im konkreten Vergleich. Ich habe Kanten dazwischen, gleiches Beispiel. Wir werden gleich noch ein bisschen was über diesen ähm Graf sagen, den man bekommt, wenn man diese grauen Elemente so zu einem Knoten zusammenknuschelt. Also, ich könnte ja sagen, das ist jetzt ein großer Knoten und das ist ein großer Knoten und das ist ein Knoten, das ein Knoten, das ein Knoten. Ähm, will ich aber jetzt eigentlich nicht machen, damit Sie noch was sehen können. Kommen wir gleich drauf zurück. Äh, für beide Probleme ist die Anwendung, wenn wir den Algorithmus ausgeführt haben, der diese Komponenten bestimmt, der gleiche. Wir können jedem Knoten eine ID zuweisen für seine Zusammenhangskomponente und dann kann ich für zwei Knoten einfach fragen, ob sie die gleiche ID haben. Der Teil ist gleich, denn in beiden Fällen sind diese Komponenten eine Partitionierung der Knoten.

3:05 Unterschiede ist das hier schwieriger zu finden, wenn wir gleich zu kommen. Ähm eine äh sicher überzeugende Anwendung ähm wenn Sie eine Menge von Organismen haben, die jeweils in irgendeiner Beziehung zueinander stehen. A ist womöglich B. Spannend sind hier die Kanten mit zwei Richtungen. Das ist ja echt interessant zwischen dieser Art von Fisch und dem Salamander. Wie auch immer es dazu kommt. Äh in der Regel sind die gerichtet. Es gibt so eine äh Nahrungskette, aber eigentlich ist es ein Netzwerk. Wenn Sie sich das anschauen, dann ähm hängen die viel zusammen. Und dann gibt's durchaus ähm äh starke Zusammenhangskomponenten, wo also äh es Kreise gibt, dass ich von einem zum anderen kommen kann. Die einfachste ist natürlich hier diese äh die zwei sind auf jeden Fall in einer Komponente und man kann sich vorstellen, dass das ja irgendwie interessant ist rauszukriegen, wer ist denn mit wem in so einem in so einem Energieäh Flussnetzwerk. Äh die Frage ist genau, wie man ähm Leben ist ja alles ein großer Kreislauf.

4:09 Die Frage ist, wie weit man den Bogen spannt. Das ist eine mögliche Anwendung. äh eine etwas informatischere wäre, so eine Art logische Formel äh auszuwerten, wenn Sie das schon kennen, eine Zweisatformel, also alle Formeln, die der von der Form sind, eine bullische Variable impliziert den Wert für eine andere. Die kann man mit äh starken Zusammenhangskomponenten auch lösen. Wenn wir hier nicht im Detail machen, aber nur noch mal so angeteasert, das ist der Namen des Problems. Brauchen Sie hier nicht weiter wissen, nur so zur Motivation. Das Problem ist nicht rein esoterisch. Äh, wie können wir diese Zusammenhangskomponenten bestimmen?

4:55 Äh, stellt sich raus, dass es im Wesentlichen eine Tiefensuche ist, aber ein bisschen trickreich. Ähm, da wir nicht so viel Zeit dafür übrig haben, werde ich hier keinen keinen gründlichen Beweis machen. Den machen wir in effiziente Algorithmen, wenn Sie das sehen wollen. Äh, deswegen hier nur so ein bisschen, wie man das anwendet und und implementiert. Das ist erstaunlich einfach und Intuition dazu.

5:21 Einfache Beobachtung, wenn ich den Graf nehme und alle Kantenrichtungen umkehre, das ist dieses gr. Also, es gibt die gleichen Kanten nur mit der umgekehrten Richtung. Dann sind die starken Zusammenlungskomponenten, die grauen Blobbels, die gleichen. Denn wenn es vorher ein Pfad von U nach W und von W nach V gibt, dann gibt's das auch beide. Und wenn es vorher nicht beide gab, dann gibt's eben auch ein äh umgedrehten Graf nicht beide. Und was wir auch schon vorhin gesagt hatten, ich kann diese äh diese Komponenten zu einem Knoten kontrahieren und dann bekomme ich so ein Bild. Und was ich vorhin schon angedeutet hatte, ist dieser dieser Kernel Dag, wie Sie ihn hier nennen, der kontrahierte Graf, wo ich also diese ganzen Komponenten zusammengezogen habe, der hat eine Eigenschaft. Der muss nämlich azyklisch sein, denn wenn es da von einer Komponente zu einer anderen irgendwie noch ein Weg zurückgäbe, dann wären die ja eine Komponente, dann gäbe es einen Weg von der einen zur anderen und zurück, dann wärden das stark zusammenhange zusammenhängende Knoten.

6:20 Das ist also ein Dag, ein gerichteterzyklischer Graf. Das heißt, theoretisch brauche ich nur eine ähm topologische Sortierung von diesem Kernel Deck und dann könnte ich von den Knoten in dieser Reihenfolge eine Tiefensuche starten. Würde ich z.B. wir hier bei der ein anfangen, versuchen alle erreichbaren Knoten zu finden. Das ist dann nur die eins und dann weiß ich, das ist die eine Komponente. Dann würde ich ein dieser Knoten aus dem nächsten aus dieser nächsten im nächsten Klaster nehmen und von dem aus würde ich noch eine Tiefensuche starten. Die findet alle Knoten in diesem Kluster und alles weiter links. Aber das weiter links habe ich schon markiert. Die finde ich also nicht noch mal. Damit finde ich genau die vom nächsten Klaster. So kann ich mich, wenn ich die topologische Sortierung von diesem Kernel Deck hab, mit einer einfachen Tiefensuche ähm dieser ganzen Klaster bemächtigen. Das Problem ist, dass wir diesen Kernel Deck nicht kennen, weil das eigentlich das Problem ist, dass wir lösen wollen.

7:26 Das heißt, das ist so ein bisschen nutzlos, diese Beobachtung. Und an der Stelle kommt das ähm was Sie hier mysterious nennen. Da ist natürlich gar nichts mysteriös dran, sondern einfach nur man braucht eine halbe Stunde zum Erklären, warum das funktioniert. Es stellt sich raus, es reicht folgenden cleveren Trick zu machen. Wir lassen eine Tiefensuche auf dem Graf laufen, auf dem alle Kanten umgedreht wurden. Und das gibt uns eine Reihenfolge der Knoten. Das sind nicht die Klaster von dem Kernel Deck, denn der hat ja ganz andere Knoten. Aber wenn ich in dieser Reihenfolge, die ich da rausbekomme, dann eine Tiefenuche auf dem vorwärtsgerichteten Graf laufen lasse, macht es das gleiche. Das ist der Teil, den man den sie ohne tief drüber nachzudenken nicht direkt sehen können. Das ist nicht nicht ob nicht ähm offensichtlich. Ist aber wahr. Und wenn Sie die Details sehen wollen, können Sie ins Buch gucken oder in effiziente Algorithmen zurückkommen oder sich äh ein paar Stunden hinsetzen und grübeln.

8:28 Ähm gibt eine ganz interessante Geschichte zu dem Algorithmus. Den hat jemand spontan erfunden, weil ihm der echte Algorithmus, den er präsentieren wollte, nicht mehr einfiel. Vielleicht ist er also doch gar nicht so äh unintuitiv.

8:41 Ähm hier ist der erste Schritt gezeigt. Wir wir führen auf diesem ähm rückwärtsgerichteten Graf die Tiefensuche aus. Das gibt uns eine gewisse Reihenfolge und dann machen wir darauf ähm den die zweite Tiefensuche mit den Rückwärtskanten und finden dann die Komponenten. Ähm statt uns das hier anzuschauen, das gleiche einmal in in animiert können wir vielleicht etwas größer haben.

9:19 Also dieser erste Schritt ist, wir drehen alle Kanten um. Sie sehen, hier gehen die nach links, z.B. jetzt gehen sie nach rechts. Darin führe ich die Tiefensuche aus, so wie wir es ähm bisher auch hatten. Das heißt, das besucht die Knoten in irgendeiner Reihenfolge und immer, wenn sie grün werden, in der Reihenfolge packe ich sie in die Post order und dann rückwärts Post Order ist eine topologische Sortierung von diesem umgekehrten Graf. Äh, das ist hier die Reihenfolge. Ja, ich habe mit der ein aufgehört. Das war der letzte Knoten, der grün wurde. Der steht also ganz hinten. Und ähm die Reihenfolge muss ich jetzt noch umdrehen, denn das ist die Poster. Die Topologie Sortierung ist rückwärts.

10:02 Das ist die umgekehrte Reihenfolge von eben, in der ich die Knoten grün gemacht habe. Und jetzt gehen wir zurück zum ursprünglichen Graf. Also die Kanten nicht mehr umgedreht und in der Reihenfolge, der die Knoten hier kommen, starten wir eine Tiefensuche. Vom Knoten 1 starten wir eine Tiefensuche. Die macht natürlich nichts, denn der hat keine ausgehenden Kanten. Das ist aber auch korrekt, denn der ist ja eine Zusammenhang eine starke Zusammenhangskomponente von sich selbst, weil niemand ähm von eins aus erreichbar ist. Ich komme da gar nicht weg. Also mache ich diesen Aufruf hier. Der Knoten wird grün markiert. Ich habe hier die Farben ähm mit anderen Bedeutung belegt. Die Farben sind jetzt die Zusammenhangskomponenten, aber ich würde diesen roten Knoten abgehandelt haben. Der fliegt vom Stack und dann weiß ich an der Stelle habe ich alle Knoten gefunden, die von ihm aus erreichbar sind. die alle bekommen ID 0 oder 1, die rote Komponente. Dann gehe ich zum nächsten Knoten in meinem äh in meiner Rückwärtsposter vom umgekehrten Graf und fang von hier aus an zu suchen.

11:07 Und alle Knoten, die ich darüber erreichen kann, das sind die hier, bilden eine Zusammenhangskomponente, denn ich kann hier z.B. im Kreis laufen. Ja, das sind aber auch alle, die ich jetzt erreichen konnte. Keiner geht mehr weiter. Das heißt, ich gehe zum nächsten Knoten hier in meine äh Reihenfolge. Ich gehe natürlich die Reihenfolge systematisch durch. Für alle, die in der Komponente sind, die sind aber schon als als Besuch markiert. Die würde ich also direkt wieder überspringen. Deswegen passiert hier nichts. Und dann habe ich den nächsten und so weiter und so fort. Ähm ich denke, sie können sich vorstellen, wie das wie das Spiel läuft. Wie gesagt, der der knifflige Schritt ist, warum genau diese Reihenfolge ausreicht. Warum hat diese Reihenfolge was mit dem Kernel Deck zu tun, obwohl wir den gar nicht kennen? Äh, da muss man ein bisschen länger drüber krübeln, als wir uns jetzt dafür Zeit nehmen können. Das Schöne daran ist, dass der Algorithmus einfach und schnell einfach zu implementieren ist und schnell läuft.

12:08 Es ist zweimal Tiefensuche. Das heißt, ich bin in der Laufzeit linear in der Größe vom Grafen. Tiefensuche besucht jeden Knoten einmal und guckt jede Kante einmal an. Das war Laufzeit. Ja, ich hatte das würde das sonst schreiben als n + m für n die Anzahl Knoten Ja, hier im Setrick brainbuch ist es mit E und V geschrieben, die Großbuchstaben als die Anzahl kollidiert so ein bisschen mit der üblichen Notation, dass man da das als die Mengen von Knoten und Kanten nimmt. Die Laufzeit ganz einfach. Wir müssen zweimal Tiefensuche machen. Ähm diesen Graf umdrehen muss man auch machen. Ist aber auch in Linearzeit möglich. Das ähm sehen Sie gleich im Code. Und die Implementierung ist relativ einfach. Ähm zum Vergleich hier noch mal die klassischen Zusammenhangskomponenten in in einem ungerichteten Graf. Was hatten wir da gemacht? Wir haben ein ein besucht Array und dann machen wir ein wesentlichen Tiefensuche und zwar auf allen Knoten als Startknoten.

13:20 Und in dieser Tiefensuche markieren wir für diesen Knoten, den wir jetzt erreichen, dass seinen Zusammenhangskomponente die aktuelle ist. Wenn eine Tiefensuche dann zurückkehrt, dann habe ich alle erreichbaren Knoten abgehandelt und dann erhöhe ich die ID von der Zusammenhangskomponente. Das heißt, der nächste Aufruf zählt dann ergibt die nächst größere ID. In ungerichteten Grafen reicht das. Für gerichtete Grafen muss ich mehr tun, aber im Code unfassbar wenig mehr. Wir machen diesen ersten Aufruf der Tiefensuche auf dem Reverse Grah. Das natürlich jetzt geschummelt, weil ich hier den Code für die Methode ausgelagert hab, aber im Prinzip ähm ist es auch einfach. Sie erzeugen einen neuen Graf, der jede Kante rückwärts verwendet. Und dann laufen wir die Knoten in dieser speziellen Reihenfolge durch, während es hier für die ungerichteten Grafen egal war. Da könnten wir konnten wir einfach die Reihenfolge in der natürlichen Ordnung nehmen. Für die starken Zusammenhangskomponenten müssen wir diese spezielle Reihenfolge nehmen, aber sonst bleibt alles gleich. Deswegen ist der Code so äh einfach zu erstellen.

14:33 Wie gesagt, warum das funktioniert ist ein bisschen subtiler. Ähm lassen wir hier aus. Damit fassen wir zusammen. Wir hatten ähm Erreichbarkeit in gerichteten Grafen lösen können mit Tiefensuche. Also einfach nur kann ich von einem Knoten zu einem anderen kommen. Das war so der die die das Kindergartenlevel, auf dem wir eingestiegen sind, das erste Level. Äh, dann hatten wir gesehen, ah, der gleiche Algorithmus kann auch topologische Sortierungen finden oder Kreise und letztlich kann quasi der gleiche Algorithmus sogar dieses viel kompliziertere Problem lösen und ähm da steckt tatsächlich noch ein bisschen mehr dahinter. Die Tiefensuche in gerichteten Grafen kann wirklich äh relativ spannende Probleme lösen und auf den ersten Blick denkt, man bräuchte irgendwas abgefahreneres.