Video 11-8: Gerichtete Graphen

0:02 Primär haben wir bisher über ungerichtete Grafen ungerichtete Grafen gesprochen, in denen ich die Kanten, die Korridore in meinem Labyrinth in beide Richtungen verwenden konnte. Äh, wir werden jetzt ein bisschen den Blick auf gerichtete Grafen äh richten, äh wo sich viele Dinge nicht ändern, aber ein paar neue Aufgaben oder Probleme dazu kommen, äh die manchmal auch ähm relevant sind. Deswegen das noch mal so ein bisschen losgelöst davon. Äh zu den Begriffen erstmal ähm sind viele Dinge ähnlich. Bei ein paar Stellen macht's eben nur Sinn über gerichtete Versionen zu sprechen. Fangen wir z.B. hier mit so einem Knoten an. Ähm ich habe jetzt nicht nur den Grad, sondern ich habe jetzt den Ausgrad und den Eingrad.

0:52 Das sind so die üblichsten deutschen Versionen davon. Englisch out degree in Indegree. Also, wie viele Kanten kommen in dem Knoten an und wie viele gehen aus dem Knoten weg? Wenn Sie einen schöneren Begriff haben, äh dann her damit. Ähm, Fade gibt's natürlich immer noch. Die haben auch die ähnliche Intuition wie wie bisher, aber sie sind jetzt eben mit Richtungen versehen. Das heißt, ein Weg oder Pfad äh muss die Kanten in der richtigen Richtung verwenden. Ähm wenn man explizit sein möchte, dann könnte man auch den gerichteten Weg sagen.

1:31 werden wir uns meistens sparen, weil eigentlich kaum Anwendung ein Pfad erlauben, wo man die Kanten in beide Richtungen verwendet, aber trotzdem drauf besteht, dass der Grafen Richtung hat. Das ist irgendwie widersinnig. Ähm Kreise kann es auch geben. Das sind also gerichtete Wege, die zum gleichen Knoten zurückkehren.

1:48 Da macht es vielleicht mehr Sinn von gerichtet oder ungerichtet zu sprechen, damit man explizit weiß, was gemeint ist. Es gibt vielfältige Anwendungen, in denen eine gerichtete Darstellung der Kannten natürlicher ist. Ähm ganz viele hier aufgelistet. Wir hatten gesehen, okay, Straßennetze mit Einbahnstraßen sind natürlich ein Beispiel äh wir hatten gesehen, dass das Page Rank Beispiel, wo man Hyperlinks hat zwischen Webseiten, ähm gibt viele viele anderen. Ähm kann sich drüber streiten, ob soziale Netzwerke gerichtete Grafen sind oder ob Freundschaft immer beidseitig ist. Na gut. Ähm überlasse ich Ihnen da sich äh paar Beispiele noch zu überlegen oder die anzuschauen. Äh etwas etwas genauer möchte ich noch mal schauen auf die Probleme, die algorithmischen Probleme oder Fragen, die man in einem gerichteten Graf stellen kann. Äh vieles ist ähnlich, gibt es einen Pfad von S nach T. Das ist halt jetzt ein gerichteter Pfad. Ähm was ist mit dem kürzesten Weg? Breitensuche, wie eben, wenn wir sehen, funktioniert immer noch.

2:57 Ähm, hat ein Graf einen gerichteten Kreis? Die Frage kann ichich auch in einem ungerichteten Graf stellen. Hat der Graf irgendeinen Kreis? Äh, die hat hier in diesem Kontext von gerichteten Grafen noch mal eine besondere Bewandnis. ähm nämlich in Verbindung mit dem nächsten kann ich den Graf irgendwie so malen, dass alle Kanten in eine Richtung zeigen oder dass es eben äh eine Anordnung der Knoten gibt, in der ich die besuchen kann, s dass ich niemals eine Kante zurückhabe, wo ich schon herkam. Wenn wir sehen, das ist ein ganz ähm äh natürliches, eine ganz natürliche Frage, wenn man gewisse Grafen hat. Ich lass mal die Spannung noch da. Okay, ein paar speziellere. Das letzte kennen Sie schon auf die beiden auf auf dem hier werden wir noch zurückkommen. Ähm, na gut, das kann ich auch sagen, äh starke Zusammenhangskomponenten.

3:51 Äh, soll ich die deutschen Begriffe noch dazu schreiben? Ich denke, bei den meisten ist es einfach. Das hier heißt einfach topologisches Sortieren, quasi direkt übersetzt.

4:02 Und das hier nennt man auf Deutsch starke Zusammenhangskomponenten, die wesentlichen auch übersetzt. Äh, da geht's darum, dass äh mit den gerichteten Wegen die Komponenten etwas komplizierter sind. Ist noch gar nicht mehr so offensichtlich, wenn man den Graf malt zu sehen, was die starken Zusammenhangskomponenten sind.

4:31 Eine starke Zusammenhangskomponente sind eine Menge von Knoten, wo es von jedem Knoten zu jedem anderen einen gerichteten Weg gibt. Und damit ähm reicht es nicht mehr, dass es da irgendwie einen Pfad gibt, sondern das muss immer auch den Weg zurückgeben. Und das ist tatsächlich ein deutlich kniffligeres Problem als was wir gerade eben für die ungerichteten Grafen hatten, dieses CC, das Connected Components, wo diese Tiefensuche die Antwort liefert. Kommen am Ende noch mal drauf zurück. Wie modellieren wir die gerichteten Grafen im Computer? Äh für die kurze Schreibweise hier immer die Graf directed Graph äh als Abkürzung im Wesentlichen genauso wie die Ungerichteten. Der einzige Unterschied ist, dass wir bisher in den ungerichteten Grafen, wenn man so eine Kante hinzufügt von V zu W, auch die Kante von W zu V einträgt. Und äh das ist im Wesentlichen der einzige Unterschied in der Darstellung. Ähm sonst genauso äh auch die Anwendung von dem von den Grafen ist sehr sehr ähnlich.

5:46 Je nach Implementierung oder je nach ähm Software Framework kann es auch sein, dass sie sozusagen eine Klasse haben für beide Arten von Grafen und es nur dann so ein Flag gibt, ist der Graf gerichtet oder ungerichtet.

6:06 Auch hier werden wir äh Adiazzlistenarstellung verwenden. Die ist eigentlich eh schon gerichtet. Für ungerichtete Grafen mussten wir deshalb die Kanten in beide Richtungen einfügen. Und das machen wir jetzt halt einfach nicht mehr. Wenn ich eine Kante von 6 nach 9 habe, dann ist die in dem Eintrag in der Zinsliste für den Knoten 6 halt einmal die neun hier irgendwo drin. Und das war's.

6:32 Dementsprechend äh auch die anderen Darstellungen, die wir am Anfang letztes Mal diskutiert hatten, Kantenliste und Adjazsmatrix, kann ich auch für gerichtete Grafen mir anschauen. In der Adjazmatrix bin ich dann nicht mehr symmetrisch, ja, weil es nicht unbedingt die Richtung, die Kante in beide Richtungen gibt. Wir werden uns aber auch hier wieder auf die Adjazslisten beschränken. Das ist quasi immer die bessere Lösung.

6:56 Äh im Code sieht das dann ähm so aus, dass sind noch mal die ungerichteten Grafen sozusagen kennen sie schon. Und der Unterschied jetzt ist äh optisch.

7:09 Wir benennen die Klasse um und wir haben einen Aufruf hier weniger. Ja, hier mussten wir die Rückwärtskante einfügen. Das machen wir jetzt halt einfach nicht. ändert sich sonst gar nichts.

7:28 Auch für die Traversierung Tiefensuche und Breitensuche ändert sich ganz wenig, wenn Sie noch mal so ein bisschen versuchen Revue passieren zu lassen, wie die Algorithmen gearbeitet haben und jetzt nicht die metaphorische Variante, sondern tatsächlich die Variante, die die Adjazlisten durchläuft. Äh wie wir das auch implementieren können. Da ändert sich nicht viel. denn wir machen immer noch die gleichen Adjazlisten. Es gibt nur so ein paar Subtilitäten, die anders sind. Ähm, Tiefensuche zuerst kann ich auch wieder als eine rekursive Methode beschreiben. Ähm, letztlich der gleiche Algorithmus, äh auch quasi der gleiche Code. Ähm, hier ist wieder in rot hervorgehoben, was sich ändert. Und sie sehen, es ändert sich hier überhaupt nur oberflächlich der Name und welchen Typ von Graf ich übernehme, der eigentliche Code so resident ist.

8:28 Ähm, es gibt weitere Anwendung von der Tiefensuche in gerichteten Grafen, die auch diesen gleichen Code verwenden, wo aber sozusagen ein paar spannendere Dinge passieren. Dazu kommen wir noch. Der Code ist aber tatsächlich unverändert. Schauen wir uns eine Anwendung an, die neu in ähm in gerichteten Grafen ist, wo das ein bisschen spannender ist. Eine eine Anwendung, wo man gerichtete Grafen auf natürliche Weise hat, sind Kontrollflussgrafen von der Methode in einem Stück Code. Also, ich weiß nicht, ob Sie irgendwas da lesen können, ist sehr klein. Äh, die Knoten in so einem Graf sind Stellen im Code, Zeilennummern, wenn Sie mögen, oder auch Blöcke von Zeilen, die immer sequentiell ausgeführt werden. Und ich habe Kanten, wenn es eine Möglichkeit gibt, von einem Quotstück in ein anderes zu springen. Entweder, weil es das nächste in der Zeile drunter ist oder weil es irgendeinen Go gibt, was sie natürlich nicht wirklich verwenden wollen oder weil es halt einen if oder while oder irgendeinen anderen Kontrollfluss äh Operation gibt, die ändert, wo wir äh im Programm weitermachen.

9:36 Und dann könnte man z.B. versuchen toten Code zu finden, also unerreichbaren Code, der einfach nie im Programm erreichbar ist. Das machen in der Regel Compiler. Ich glaube, Java ist da auch sehr streng und verbietet das gänzlich. Wenn sie Code haben, von dem statisch klar ist, dass er nie erreichbar ist, also z.B. Code nach dem Return von der Methode, dann haut ihn Java direkt auf den Java C genauer direkt auf die Finger.

10:07 Äh man könnte auch versuchen zu erkennen, ob ein Programm terminieren kann, aber das ist im allgemeinen natürlich nicht wirklich möglich. Äh, man könnte aber zumindest versuchen, ob eine bestimmte Stelle jemals erreicht werden kann. Also, wenn ich eine Methode gebaut habe, in der es nie ein Return Statement gibt, das erreichen kann, dann haut ihn das der Java Compiler auch um die Ohren und auch dahinter steckt so ein gerichteter Graf und Analyse dazu.

10:30 Anderes Beispiel, wo gerichtete Grafen ganz natürlich vorkommen, sind Objekte und die Referenzen auf andere Objekte. Das ist immer gerichtet und die zumindest ältere Versionen von Java haben auch im Wesentlichen diesen Algorithmus verwendet, um das Garbage Collection zu implementieren. Sie wissen ja, sie können in Java neue Objekte anlegen und ihren Müll einfach liegen lassen. Irgendwer räumt den dann auf. Wenn Sie auf Kilonova vergleichen, dann sehen Sie auch, dass das einen Overhead im Speicherplatz hat, der durchaus beträchtlich ist. Wir machen immer den Vergleich C++ und Java für Aufgaben, um zu sehen, wie man die Timeouts und so weiter setzen muss. Und Java braucht immer deutlich mehr Speicher, weil man eben nicht so streng direkt aufräumen muss. Wie macht Java das? Ähm mittlerweile mit einem etwas komplizierteren Algorithmus, aber die ursprüngliche Variante ist so ein Mark and Sweep Garbage Collector. Da fange ich an mit Objekten, die statisch bekannt sind. Also z.B. statische Variablen, globale Variablen, sowas in der Art. Von denen verfolge ich alle Pointer und markiere jedes Objekt, dass ich so erreichen kann. Und dafür hat tatsächlich jedes Java Objekt auch ein kleines äh Stückchen Speicher für reserviert. Alle Java Objekte haben ein bisschen Overhead und eins davon ist dieser Garbage Collector. Und alle Objekte, die ich hier erreicht habe, ähm haben jetzt eben dieses markiert Bit gesetzt. Das heißt, die sind noch irgendwo erreichbar von statischen Variablen. Die sollte ich nicht aufräumen, denn die benutzt vielleicht noch jemand. Alle Objekte, die ich nicht erreicht habe, sind also jetzt nicht markiert worden und die mache ich dann in einem Durchlauf über den ganzen Hieb äh auf den auf die Müllhalte.

12:16 Also im Wesentlichen ein ähm Erreichbarkeitscheck von einem von einem gerichteten Grab. Ja, bisschen Historie dazu können Sie noch nachlesen. Ich brauche auf jeden Fall ein Bit, um das dann zu speichern.

12:38 Äh, wir haben ein bisschen an der Oberfläche gekratzt. Man kann mit Tiefen Suche in den gerichteten Grafen entscheiden, ob ich von einem Knoten irgendeinen anderen erreichen kann, wie gerade im letzten Beispiel. Und ich kann natürlich auch den Pfad ausgeben mit der gleichen Edge2 äh Variante wie bisher. Und wir werden sehen, dass man eine grei eine Reihe von anderen komplizierteren Problemen genauso lösen kann, indem man clever Tiefenzuche wieder verwendet. Auf den ersten Blick sah es vielleicht so aus, als bräuchte man nur Breitensuche, weil die eigentlich das gleiche tun und Breitensuche dazu wenigstens kurze Wege findet. Ähm stellt sich raus, zumindest bei diesen ähm gerichteten Grafen genaueren Blick, die Tiefensuche kann eine ganze Menge cooler Sachen, die man mit breitensuche nicht machen kann. Ein paar davon äh sehen wir noch.

13:27 Jetzt habe ich Breitensuche ein bisschen klein geredet. Wir wollen es aber breitens trotzdem angucken, denn manchmal wollen wir ja auch kürzeste Wege haben, auch in gerichteten Grafen. Auch hier ist die große Nachricht im Wesentlichen, es gibt nichts zu sagen. Breitensuche funktioniert genauso. Äh ändert sich im Wesentlichen nichts am Algorithmus und auch nichts wirklich im Code. Ähm habe ich Ihnen auch nicht noch mal jetzt hier explizit gezeigt. Äh, es gibt eine eine ähm Erweiterung von Breitensuche, die auch in ungerichteten Grafen genauso Sinn macht. Ähm, die möchte ich noch erwähnen. Wir können das Problem verallgemeinern, indem wir sagen, wir fangen nicht an einem bestimmten Knoten an, sondern es gibt mehrere Optionen, wo ich starten kann. Also vielleicht wollen sie nur wissen, was ist die kürzeste Distanz von verschiedenen Hotels zu einem Bahnhof und es ist ihnen nicht so wichtig, welcher. Dann könnten Sie von allen Bahnhöfen aus loslaufen und den kürzesten Weg von jedem interessanten Knoten, jedem Hotel zu einem Bahnhof binden. Das klingt erstmal ziemlich kompliziert, als würde ich von jedem Bahnhof aus dieses diese Distanzen berechnen, dann irgendwie das Minimum daraus nehmen. Das müssen sie aber nicht. Sie können in der breiten Suche, statt mit einem Startknoten loszulaufen, einfach mit allen loslaufen, die sie als Startknoten haben wollen, indem sie die am Anfang alle in die Queue packen und die Distanz auf null setzen und der Rest vom Algorithmus ist unverändert.

15:01 Das ist das, was hier auf der Folie ein bisschen erklärt ist. Ähm, sie können mit einer ganzen Menge von Knoten beginnen. Hier ist es ähm 01 und 7. Mach die vielleicht mal so.

15:20 01 und 10. Was habe ich gesagt? Ein, na, Quatsch. N 0 1 17 1 7 und 10. Okay. Äh, man liest, was man lesen möchte und dann kann ich einen kürzesten Pfad finden, der zu irgendeinem Startknoten zu irgendeinem Knoten führt. Z.B. hier der vier. Wie komme ich am schnellsten zur vier von irgendeinem dieser Knoten? Stellt sich raus von der 7 zur 6 zur 4 ist tatsächlich kürzer als von allen anderen. Ich darf aber für einen anderen Knoten, z.B. für die fünf, einen anderen Startknoten verwenden.

15:56 Äh nehmen wir ein Beispiel, wo ein anderen ist, nehmen wir die 12. Da komme ich natürlich direkt von der 10. Ja. Ähm, gleicher Code, ich fange oder gleicher Algorithmus. Ich muss nur mit diesen drei Knoten in der Q anfangen und der Rest bleibt gleich.