5.2.3. Gerichtete und ungerichtete Graphen

Lernziele

Gerichtete und ungerichtete Graphen in LEDA
Die Methoden make_undirected(), make_directed() und is_directed()
Die Methode make_bidirected()

Eine sehr häufig im Zusammenhang mit den Graphentypen von LEDA gestellte Frage ist die, wie LEDA zwischen gerichteten und ungerichteten Graphen unterscheidet, und wie man einen gerichteten bzw. ungerichteten Graphen erzeugt. Im gerade vorgestellten Programm zur Breitensuche mittels BFS() z. B. haben wir für jede Kante auch eine Rückwärtskante eingefügt und dadurch (implizit) die ungerichtete Version eines Graphen erzeugt. Wäre das auch anders möglich gewesen? Wie wir schon angedeutet haben, unterscheidet sich LEDAs Definition der Begriffe „gerichtet“ und „ungerichtet“ ein wenig von der klassischen Sichtweise.

Um den Unterschied zu verstehen, müssen wir ein wenig darüber wissen, wie die Knoten und Kanten eines Graphen intern gespeichert werden. Zunächst einmal liegen alle Knoten in einer Liste V und alle Kanten in einer Liste E. Zusätzlich aber sind die Kanten noch in andere Listen eingeordnet, wie wir gleich sehen werden.

Gerichtete Graphen in LEDA

Wird nichts anderes gesagt, so ist ein graph gerichtet. Das bedeutet, dass zu jedem Knoten v zwei (zirkuläre) Listen gehalten werden: In der Liste out_edges(v) liegen alle Kanten, deren Quelle v ist, die also von v ausgehen. In der Liste in_edges(v) dagegen liegen alle Kanten, deren Ziel v ist, die also inzident zu v sind. Die Liste adj_edges(v) ist ein Synonym für out_edges(v) und wird oft auch als Adjazenzliste von v bezeichnet. Abbildung 5.5 gibt ein Beispiel.

Abbildung 5.5. Interne Darstellung eines gerichteten Graphen

Interne Darstellung eines gerichteten Graphen

Ein Graph mit den 3 Knoten 0, 1, 2 und den 5 Kanten a, b, c, d und e. Es ist Quelle(a)=0, Ziel(a)=1 usw. Es sind a=(0,1) und d=(0,1); a und d sind somit Multikanten. e ist eine Selbstschleife

Es sind out_edges(0)=(a,c,d), in_edges(0)=(), out_edges(1)=(b), in_edges{1}=(a,d), out_edges(2)=(e), in_edges(2)=(b,c,e).

G.make_undirected() hängt jede Liste in_edges(v) an out_edges(v) an, und die out_edges(v) werden zu adj_edges(v) umbenannt. Das Flag wird auf ungerichtet gesetzt. G ist dann ungerichtet. Die Listen in_edges(v) und out_edges(v) stehen nicht mehr zur Verfügung.

Um also in LEDA mit einem ungerichteten Graphen im klassischen Sinne zu arbeiten, muss nichts anderes als

graph G;

gesagt werden. Eine danach durch G.new_edge(v1,v2) eingefügte Kante e hat immer eine Richtung: Es ist Quelle(e)=v1 und Ziel(e)=v2.

[Note] Anmerkung

Im Unterschied zur klassischen Bezeichnung „inzident “ wird in LEDA eine Kante e=(v1,v2) (in einem gerichteten Graphen) als adjazent zu v1 (nicht aber zu v2!) bezeichnet.

Der einzige Unterschied zu gerichteten Graphen im klassischen Sinne ist die Möglichkeit, Multikanten (multiedges) einzufügen. Das bedeutet, dass von einem Knoten v aus mehrere Kanten zum selben Knoten w zeigen.

Ungerichtete Graphen in LEDA

LEDAs Sichtweise von ungerichteten Graphen ist die folgende: Jeder gerichtete Graph ohne Selbstschleifen kann auch als ungerichteter Graph aufgefasst werden, wenn nur der Begriff „adjazent“ anders definiert wird. Die Kanten haben dabei immer noch eine Richtung, sie kennen immer noch Quell- und Zielknoten; allerdings werden sie intern anders gespeichert.

Durch die Anweisungsfolge

graph G;
G.make_undirected();

wird G als (im Sinne von LEDA) ungerichteter graph definiert. Das hat folgende Auswirkungen: Zu jedem Knoten v existiert nur die Liste adj_edges(v); darin sind alle Knoten enthalten, deren Quelle oder Ziel v ist. Ein Kante gilt also als adjazent sowohl zum Quell- als auch zum Zielknoten. Abbildung 5.6 gibt ein Beispiel.

Abbildung 5.6. Interne Darstellung eines ungerichteten Graphen

Interne Darstellung eines ungerichteten Graphen

Ein Graph mit den 3 Knoten 0, 1, 2 und den 4 Kanten a, b, c und d. a=(0,1), d=(0,1), b=(1,2), c=(0,2). Diese Kanten haben immer noch eine Richtung! Es ist Quelle(a)=0, Ziel(a)=1 usw. a und d sind Multikanten.

Es sind adj_edges(0)=(a,c,d), adj_edges(1)=(a,b,d), adj_edges(2)=(c,b).

G.make_directed() trennt adj_edges(v) wieder in in_edges(v) und out_edges(v) auf, also z. B. out_edges(1)={b}, in_edges(1)={a,d} usw.

Worin besteht hier nun der Unterschied zum klassischen Verständnis des Begriffes „ungerichtet“? Zunächst einmal ist wieder festzuhalten, dass Multikanten erlaubt sind. Aus Sicht des Programmierers gibt es bei der Verwendung eines ungerichteten graph einige wichtige Konsequenzen:

Die Makros, die zum Iterieren über die zu einem Knoten (im Sinne von LEDA) adjazenten Kanten und Knoten dienen, arbeiten anders als bei einem gerichteten graph. Das liegt daran, dass nun zu einem Knoten v möglicherweise andere (i. Allg. mehr) Kanten und Knoten als adjazent gelten.

[Important] Wichtig

Viele in LEDA eingebaute Graphenalgorithmen, wie z. B. die Funktion BFS(), erwarten als Eingabe einen gerichteten graph und versagen, wenn dieser vorher durch G.make_undirected() ungerichtet gemacht wird.

Will man nun mit einer dieser Funktionen einen im klassischen Sinne ungerichteten Graphen bearbeiten, so muss man zu jeder Kante die entsprechende Rückwärtskante einfügen, wie wir das im Programm zur Breitensuche mittels BFS() auch getan haben. Ein solcher graph heißt dann bidirektional. Die Methode

G.make_bidirected();

macht einen graph bidirektional, indem sie fehlende Rückwärtskanten einfügt. Damit kann auf einfache Weise ein im klassischen Sinne ungerichteter Graph durch einen gerichteten graph simuliert werden.

[Tip] Tipp

I. Allg. kommt man auch für ungerichtete Graphen mit einem gerichteten graph aus: Das Makro forall_inout_edges und die Methode opposite() genügen in den meisten Problemstellungen, um die Richtungsinformation eines gerichteten graph zu „vergessen“ und sich dadurch wie in einem ungerichteten Graphen zu bewegen.

Der wahre Unterschied zwischen gerichteten und ungerichteten Graphen in LEDA

Die Methode

G.is_directed();

testet, ob ein graph (im Sinne von LEDA) gerichtet oder ungerichtet ist. Was macht diese Funktion intern? Ganz einfach: Sie liefert den Wert eines Flags zurück. Ein Flag alleine entscheidet also darüber, ob ein graph als gerichtet oder ungerichtet gilt, nicht die Frage, ob zu jeder Kante auch eine Rückwärtskante existiert o. Ä. Die Methoden der Klasse graph sorgen selbsttätig dafür, dass ein graph gerichtet bzw. ungerichtet bleibt. So ist es z. B. im ungerichteten Falle nicht möglich, eine Selbstkante einzufügen.

Die Methoden make_directed() und make_undirected()

Dieses Flag steht zunächst auf true, bis es ein Aufruf von make_undirected() auf false setzt. Ein solcher Aufruf macht aber noch mehr: Er entfernt alle Selbstschleifen, hängt jede Liste in_edges(v) and out_edges(v) an und benennt letztere zu adj_edges(v) um. Die ursprünglichen Listen in_edges(v) und out_edges(v) stehen nicht mehr zur Verfügung - ihr Inhalt ist nicht wohldefiniert. So entsteht z. B. der graph von Abbildung 5.6 durch einen Aufruf von make_undirected() aus dem graph von Abbildung 5.6.

Dagegen wird dieses Flag durch einen Aufruf von

G.make_directed();

wieder auf true gesetzt. Diese Methode trennt die Listen adj_edges(v) auf in jeweils zwei Listen in_edges(v) und out_edges(v) - das kann sie, da auch in einem ungerichteten graph die Kanten eine Richtung haben.

[Warning] Warnung

Die Methoden make_directed() und make_undirected() sind keine Umkehrfunktionen zueinander! Wird der graph aus Abbildung 5.6 wieder gerichtet gemacht, so entsteht nicht wieder der graph aus Abbildung 5.5: Es fehlen die ursprünglichen Selbstschleifen. Es wird also nur teilweise umgekehrt.

Übungen

Übung 50.

Testen Sie was geschieht, wenn Sie im Programm zur Breitensuche mittels BFS() den graph ungerichtet machen. Probieren Sie make_undirected() an verschiedenen Stellen aus.

Formulieren Sie dann das Programm mittels make_bidirected() so um, dass Sie nicht explizit zu jeder Kante auch eine Rückwärtskante einfügen müssen.