5.2.1. Wie man anfängt

Lernziele

Die Klasse graph
Knoten und Kanten erzeugen
Die Klassen node_array und edge_array
Grundlegende Graphenalgorithmen benutzen
Topologische Sortierung mit TOPSORT()
Über alle Knoten und Kanten iterieren

Jeder Autor, der einen zusammenhängenden Themenkomplex wie etwa das LEDA-System selbst beschreiben will, sieht sich zu Beginn seiner Tätigkeit vor die folgende, äußerst wichtige und oftmals schwer zu beantwortende Frage gestellt: „Mein Gott, wo fange ich bloß an?“ Das Problem dabei ist, dass die einzelnen Themengebiete voneinander abhängig sind: Damit der Leser versteht, was in Abschnitt Y gesagt wird, muss er zuerst Abschnitt X gelesen haben. Jeder gute Autor achtet darauf, die Abschnitte so anzuordnen, dass der Leser das Gesamtwerk einmal von vorne nach hinten durchlesen kann, und dabei nie auf Seite x schon wissen muss, was erst später auf Seite y geschrieben steht. Der Autor sollte also ohne Vorwärtsreferenzen auskommen; dann nämlich kommt der Leser mit einem einzigen Durchlauf (single pass) durch den Text aus. Vielen ansonsten hervorragenden Werken fehlt genau diese Eigenschaft, was sie für einen noch nicht Eingeweihten schwer verständlich macht.

Wie lässt sich eine solche Anordnung der Abschnitte herstellen? Zunächst einmal ist es sinnvoll, die Problemstellung als Graph zu modellieren: Für jeden Abschnitt führt man einen Knoten ein. Ist der Stoff von Abschnitt X Vorbedingung für das Verständnis des Stoffes aus Abschnitt Y, so zeichnet man eine Kante (X,Y) von X nach Y ein. Der sich so ergebende Graph wird Abhängigkeitsgraph (dependency graph) genannt. Abbildung 5.3 zeigt einen solchen Abhängigkeitsgraphen für einen Themenkomplex aus 8 Abschnitten.

Abbildung 5.3. Ein Abhängigkeitsgraph

Ein Abhängigkeitsgraph

Ein Abhängigkeitsgraph für 8 in einem literarischen Werk unterzubringende Abschnitte A, B, C, D, E, F, G und H. Die Abschnitte sind im Werk so hintereinander anzuordnen, dass ein Leser das Werk verstehen kann, ohne jemals nach vorne blättern zu müssen.

Beginnen sollten wir unser Werk natürlich mit einem Abschnitt, also mit einem Knoten v, dessen Eingangsgrad 0 ist, zu dem also keine Kanten inzident sind. Nur ein solcher Knoten hat keine anderen Knoten als Voraussetzung für das Verständnis. Was aber, wenn es keinen solchen Knoten gibt? Dann haben wir verloren - es ist unmöglich, den Leser in einem einzigen Durchlauf durch das Werk zu führen; in jedem Abschnitt muss er schon den Inhalt eines anderen Abschnitts kennen. Gibt es dagegen einen solchen Knoten v, so können wir mit v beginnen. Wir geben ihm die Nummer 1.

Wie aber ordnen wir die restlichen Knoten an? Da wir den Abschnitt v schon als ersten einer guten Reihenfolge erkannt haben, können wir v aus der Menge der noch anzuordnenden Abschnitte herausnehmen, d. h., der Knoten v kann aus dem Graph entfernt werden. Dadurch vermindert sich der Eingangsgrad aller ehemals zu v adjazenten Knoten um 1. Nun stellt sich wieder dieselbe Frage: Mit welchem Knoten machen wir weiter? Wiederum suchen wir nach einem Knoten w mit Eingangsgrad 0. Gibt es keinen solchen, haben wir verloren. Ansonsten geben wir ihm die Nummer 2, entfernen ihn aus dem Graphen und machen immer so weiter, bis wir entweder bei einem leeren Graphen angelangt sind und dabei allen Knoten eine Nummer gegeben haben, oder bei einem nicht leeren Graphen stehen geblieben sind, in dem in jeden Knoten mindestens eine Kante einmündet.

In dem Fall, dass wir jedem Knoten v eine Nummer N(v) zuordnen konnten, haben wir gewonnen: Wir ordnen die Abschnitte unseres Werkes in der durch die N(v) gegebenen Reihenfolge an. Diese Nummerierung N hat eine besondere Eigenschaft: Wann immer es eine Kante (u,v) im ursprünglichen Graphen gibt, ist die Nummer N(u) kleiner als die Nummer N(v). Eine Nummerierung mit einer solchen Eigenschaft heißt Topologische Sortierung.

Wann genau kann eine solche Topologische Sortierung gefunden werden? Wie man leicht vermuten kann, hat die Existenz einer solchen Sortierung mit der Existenz von Zyklen in einem Graphen zu tun. Übung 47 fordert dazu auf, sich klar zu machen, dass eine Topologische Sortierung genau dann existiert, wenn ein Graph keine Zyklen hat.

Ein erstes Programm

Einen Graphen topologisch zu sortieren, ist ein graphenalgorithmisches Grundproblem. Selbstverständlich hat LEDA eine entsprechende Funktion bereits eingebaut. Als ein erstes Programm wollen wir den Graphen aus Abbildung 5.3 mittels der in LEDA dafür vorgesehenen Struktur aufbauen und eine Topologische Sortierung berechnen.

Die Klasse von LEDA, mit der Graphen verwaltet werden können, heißt, wie sollte es anders sein, graph. Es handelt sich hierbei um eine überaus mächtige Klasse, deren Methoden wir nach und nach kennen lernen werden.

Ein Graph wird angelegt durch

graph G;

Um nun die Struktur des Graphen aufzubauen, müssen zuerst Knoten eingefügt werden. Das geht durch einen Aufruf von

node v = G.new_node();

Diese Methode liefert ein Item vom Typ node zurück. Es handelt sich dabei um einen abhängigen Item-Typ. Auf den entsprechenden Knoten kann später nur über ein solches Item zugegriffen werden; das zurückgelieferte Item kann dazu in einer Variablen vom Typ node gespeichert werden. Damit kann zu einem späteren Zeitpunkt der Knoten durch

G.del_node(v);

wieder aus dem Graphen gelöscht werden (und damit auch alle von ihm ausgehenden und zu ihm inzidenten Kanten).

Zwischen zwei Knoten v1 und v2 kann eine Kante durch

edge e = G.new_edge(v1, v2);

eingefügt werden. Auch hier wird ein abhängiges Item zurückgeliefert; es ist vom Typ edge. Spätere Zugriffe auf die gerade eingefügte Kante sind nur über ein solches Item möglich; so kann z. B. die Kante durch

G.del_edge(e);

wieder aus dem Graphen entfernt werden.

Mit diesen beiden Methoden lässt sich die kombinatorische Struktur eines vorgegebenen Graphen nach und nach aufbauen. Dadurch hat der Graph aber noch keinerlei Information assoziiert! Wünschenswert wäre es etwa, jedem Knoten einen Namen zu geben, z. B. den Namen des entsprechenden Abschnittes in einem Pulitzer-Preis verdächtigen Tutorium zu LEDA. Und schließlich soll ja auch zu jedem Knoten die Nummer einer Topologischen Sortierung gespeichert werden! Was also hier vonnöten ist, ist eine Möglichkeit, zu jedem Knoten eine Information zu assoziieren. Dafür hält LEDA u. a. die Klasse node_array bereit, die wie ein gewöhnliches array über den Subskript-Operator [] benutzt wird; die Schlüssel-Indizes sind hier immer vom Typ node. Entsprechend gibt es die Klasse edge_array, mit der eine Information zu den Kanten eines Graphen assoziiert werden kann.

[Note] Anmerkung

Es gibt nur sehr wenige Problemstellungen, die sich allein mit der Klasse graph lösen lassen. Wie schon gesagt, dient diese lediglich zur Kodierung der kombinatorischen Struktur eines Graphen. In den allermeisten Fällen werden noch andere Klassen wie etwa node_array oder edge_array benötigt, um Zusatzinformationen festzuhalten.

Auf einem bereits aufgebauten (s. hierzu Abschnitt 5.2.2) Graphen wird ein node_array für die Nummerierung einer Topologischen Sortierung wie folgt definiert:

node_array<int> top_num(G);

Die LEDA-Funktion TOPSORT() zur Berechnung einer Topologischen Sortierung wird wie folgt benutzt:

bool has_top_sort = TOPSORT(G, top_num);

Sie liefert false zurück, wenn der Graph zyklisch ist und daher keine Topologische Sortierung besitzt. Das folgende Programm baut zunächst obigen Graphen auf und ruft dann TOPSORT() auf, um eine Topologische Sortierung zu berechnen.

[Important] Wichtig

Wer die Programme dieses Kapitels austesten möchte und unter Unix™ arbeitet, muss Folgendes beachten: Unter Unix™ sind die Klasse graph und alle anderen in diesem Kapitel eingeführten Klassen und Algorithmen (außer der in Abschnitt 5.2.5 besprochenen Klasse GraphWin) in der LEDA-Bibliothek libG enthalten. Damit diese korrekt dazugebunden wird, muss beachtet werden, was in Abschnitt 1.3.1 zum Binden unter Unix™ gesagt wurde: Es ist die Reihenfolge -lG -lL -lm einzuhalten.

Für GraphWin sind zusätzlich die Bibliotheken libW und libP (in dieser Reihenfolge) hinzuzubinden: -W -P -lG -lL -lm

Filename: AuthorsProblem.C
#include <LEDA/graph.h>
#include <LEDA/node_array.h>
#include <LEDA/basic_graph_alg.h>
#include <LEDA/string.h>

using leda::graph;
using leda::node;
using leda::node_array;
using leda::TOPSORT;
using leda::string;
using std::cout;


int main()
{
  graph G;

  node v0 = G.new_node();
  node v1 = G.new_node();
  node v2 = G.new_node();
  node v3 = G.new_node();
  node v4 = G.new_node();
  node v5 = G.new_node();
  node v6 = G.new_node();
  node v7 = G.new_node();

  G.new_edge(v0, v1);
  G.new_edge(v0, v3);
  G.new_edge(v1, v2);
  G.new_edge(v2, v3);
  G.new_edge(v4, v5);
  G.new_edge(v5, v0);
  G.new_edge(v5, v2);
  G.new_edge(v6, v1);
  G.new_edge(v6, v4);
  G.new_edge(v7, v2);
  G.new_edge(v7, v3);
  G.new_edge(v7, v6);
  G.new_edge(v0, v1);

  node_array<string> name(G);
  name[v0] = "A";
  name[v1] = "B";
  name[v2] = "C";
  name[v3] = "D";
  name[v4] = "E";
  name[v5] = "F";
  name[v6] = "G";
  name[v7] = "H";
    
  cout << "This graph has " << G.number_of_nodes() << " nodes and ";
  cout                      << G.number_of_edges() << " edges.\n";


  node_array<int> top_num(G);
  
  if(!TOPSORT(G, top_num)) {
    cout << "G has no topological sorting!\n";
  }
  else {
    node v;

    cout << "The following is a topological sorting:\n";
    forall_nodes(v,G)
      cout << name[v] << " " << top_num[v] << "\n";


    G.sort_nodes(top_num);
    cout << "Nodes sorted topologically:\n";
    forall_nodes(v,G)
      cout << name[v] << " " << top_num[v] << "\n";
  }
}

Die Ausgabe des Programms lautet:

This graph has 8 nodes and 13 edges.
The following is a topological sorting:
A 5
B 6
C 7
D 8
E 3
F 4
G 2
H 1
Nodes sorted topologically:
H 1
G 2
E 3
F 4
A 5
B 6
C 7
D 8

Als kluger Autor könnte man also die Abschnitte in der Reihenfolge H, G, E, F, A, B, C, D anordnen und würde dabei dem Leser an keiner Stelle noch nicht behandelten Stoff zumuten; er müsste dann also nie nach vorne blättern! Mit diesem Verfahren lässt sich immer eine leserfreundliche Anordnung der Abschnitte finden, sofern der Abhängigkeitsgraph keine Zyklen hat.[38]

Um die Funktion TOPSORT() oder andere grundlegende Graphenalgorithmen benutzen zu können, muss die Header-Datei basic_graph_alg.h eingebunden werden.

Da wir in obigem Programm die von new_edge() zurückgelieferten Kanten-Items nicht weiter verwenden, speichern wir sie erst gar nicht zwischen.

Ein Aufruf

G.number_of_nodes();
G.number_of_edges();

liefert die aktuelle Anzahl der Knoten bzw. Kanten eines Graphen.

Über alle Knoten eines Graphen kann mit dem Makro

forall_nodes(v, G) {...}

iteriert werden, das nach und nach Items v liefert, die auf die einzelnen Knoten eines Graphen verweisen. Entsprechend kann mit dem Makro

forall_edges(e, G) {...}

über alle Kanten iteriert werden. Näheres zur Iteration über Graphen werden wir in Abschnitt 5.2.4 erfahren.

In der internen Darstellung eines graph sind die Knoten und die Kanten in einer bestimmten Reihenfolge angeordnet; diese wird von forall_nodes bzw. forall_edges durchlaufen. Die Methode

G.sort_nodes(numbering)

ordnet die Knoten intern gemäß der durch ein node_array numbering übergebenen Reihenfolge neu an. Das nutzen wir hier aus, um die Knoten in der Reihenfolge ihrer Topologischen Sortierung auszugeben. Entsprechend gibt es sort_edges() zum Sortieren von Kanten.

Implementierung und Weitere Informationen

Graphen sind durch doppelt verkettete, zirkuläre Listen für die Knoten und Kanten implementiert; wir werden darauf noch näher eingehen. Die meisten Operationen auf einem graph benötigen konstante Zeit bzw. die benötigte Zeit ist direkt aus der Semantik der Operation ersichtlich.

Die definitive Referenz zur Klasse graph ist natürlich die entsprechende Manualseite. Diese Seite enthält eine ganze Fülle von Informationen - die Schnittstelle von graph ist außerordentlich groß. Wir werden die wichtigsten Konzepte und Methoden in den nächsten Abschnitten nach und nach kennen lernen.

Übungen

Übung 47.

Überlegen Sie sich, warum Folgendes gilt: Ein gerichteter Graph hat genau dann eine Topologische Sortierung, wenn er keinen Zyklus enthält.

Überlegen Sie zusätzlich, warum das oben vorgestellte Verfahren eine solche Sortierung entdeckt, wenn es denn eine gibt. Warum muss eine Topologische Sortierung nicht eindeutig sein?

Übung 48.

Ein Graph heißt planar, wenn er so in die Ebene gezeichnet werden kann, dass sich seine Kanten an keiner Stelle überschneiden.

In einem alten Kinderspiel sollen 3 Häuser H1, H2 und H3 jeweils mit einem Wasserwerk W, einem Elektrizitätswerk E und einem Heizkraftwerk H durch Leitungen so verbunden werden, dass die Leitungen sich nicht überkreuzen, s. Abbildung 5.4. Dieser Graph hat den Namen K3,3. Wir werden seine Bedeutung für das Zeichnen von Graphen in Abschnitt 5.2.6 näher kennen lernen.

Abbildung 5.4. Der Graph K3,3

Der Graph K3,3

Der Graph ist nicht planar: Wie auch immer wir versuchen, die gepunktete Kante von H3 nach W zu zeichnen, wir müssen dabei eine andere Kante kreuzen. Das gilt auch für jede andere Art und Weise, die anderen Kanten zu zeichnen.

Bauen Sie diesen Graphen mit der Klasse graph auf, und benutzen Sie die eingebaute Funktion Is_Planar() um zu testen, ob dieser Graph planar ist. Um diese Funktion zu verwenden, muss die Header-Datei graph_misc.h eingebunden werden.



[38] Was für Informatiker selbstverständlich und kaum erklärungsbedürftig ist, nämlich beim Verfassen von wissenschaftlichen Texten die einzelnen Abschnitte in der Reihenfolge einer Topologischen Sortierung anzuordnen, scheint in anderen Disziplinen nur wenig bekannt zu sein. So erhielt der Autor von einem ihm wohlbekannten Physiker, der seit über 10 Jahren in der Forschung tätig ist und schon zahlreiche wissenschaftliche Abhandlungen veröffentlicht hat, folgende Rückmeldung auf die hier vorgestellte Anwendung von Topologischer Sortierung: „Also, da bin ich baff. Schon seit über 10 Jahren überlege ich immer wieder unter großen Anstrengungen, wie ich nur meine Abschnitte anordnen kann. Dass das so einfach mit einem Graphen geht, war mir völlig unklar. Du solltest das hier veröffentlichen. Das könnte bahnbrechend für die Publikationspraxis in allen Disziplinen, auch den geisteswissenschaftlichen, sein.