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.6 gibt ein Beispiel.

Abbildung 5.6. 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 gerichteten 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.

	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. (In der klassischen Bezeichnungsweise heißt (v1,v2) „inzident zu v2“ und „inzident aus v1“, auch wenn die letzte Bezeichnung unsinnig ist im Hinblick auf die Bedeutung des lateinischen Wortes „inzident“ = „hineinfallend“.)

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.

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.7 gibt ein Beispiel.

Abbildung 5.7. 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.

	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.

	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.

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.

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.7 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.

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