Quelltext

Man legt mit einem beliebigen Editor eine Datei (z.B. simple.c) an und gibt den notwendigen Quelltext ein. Zunächst sind, neben anderen Deklarationen, die Deklarationen des Graphenlabors dem Programm mitzuteilen:

Ab jetzt stehen alle Typen, globalen Variablen und Funktionsprototypen des Graphenlabors zur Verfügung. Das Programm besteht aus dem Hauptprogramm main(), einer Funktion buildTree() zum Aufbau des Baumes und einer rekursiven Funktion traverse() zur Traversierung. Diese Funktionen werden erst weiter unten definiert. Damit sie trotzdem im Hauptprogramm benutzbar sind, muß zuerst ihre Signatur deklariert werden.

Bei Betreten der Funktion main wird zunächst ein leeres Typsystem ts angelegt und über den Konstruktor der Klasse G_typeSystem initialisiert. Genauso wird ein leerer Graph g angelegt und mit dem Typsystem ts verbunden.

Alle Informationen über die Graphstruktur werden im Graph g abgespeichert und verwaltet. Die Knoten und Kanten existieren nur innerhalb des Graphen g und nicht als eigenständige C++-Objekte. Für den Zugriff auf einzelne Graphelemente werden Instanzen der Klassen  G_vertex und  G_edge benutzt, die Referenzen auf die Graphelemente im Graph enthalten. Will man auf Knoten oder Kanten zugreifen, dann muß man Methoden der Klasse G_graph aufrufen und dabei die Knoten und Kanten durch Variablen vom Typ G_vertex oder G_edge angeben. In unserem Beispiel benötigen wir eine Variable root, über die wir auf den Wurzelknoten (als Repräsentanten) des Baumes zugreifen können.

Nachdem alle Variablen definiert sind, wird der abgebildete Baum mit buildTree() aufgebaut. Diese Funktion liefert uns die Referenz des Wurzelknotens zurück. Die Funktion traverse() schließlich traversiert den Baum von der Wurzel root aus mit einer anfänglichen Rekursionstiefe von 0.

Als nächstes wird die Funktion buildTree() angegeben. Da jeder Knoten und jede Kante einem Typen aus dem Typsystem zugeordnet sein muß, werden sie alle dem  Nulltyp zugeordnet. Hierzu wird zuerst der Nulltyp des mit dem Graph verbundenen Typsystems abgefragt und in der Variablen tNull gespeichert.

Mit der Methode  G_graph::createVertex() werden neue Knoten im Graph g erzeugt. Die Knotenreferenzen werden in den Variablen v1 bis v6 gespeichert, da sie beim Erzeugen der Kanten benötigt werden. Die Methode  G_graph::createEdge() erzeugt neue gerichtete Kanten. Zuletzt wird die Referenz des Wurzelknotens als Rückgabewert der Funktion behandelt.

Die Funktion traverse() testet zuerst, ob sie sich in einem Kreis befindet. Danach werden Punktepaare ausgegeben, die der Rekursionstiefe entsprechen.

Im Graphenlabor wird jeder Knoten durch eine im Graph eindeutige Nummer identifiziert. Diese Nummer wird mit der Methode  G_graph::getVNo() abgefragt und als Knoteninformation ausgedruckt. Danach werden alle Kanten in $\Lambda^+(v)$ bearbeitet. Der Zugriff auf $\Lambda^+(v)$ erfolgt über das Makro  G_forAllOutEdges. Da die Endknoten $\omega(e)$ der Kanten $e\in\Lambda^+(v)$ die Kindknoten des gerade betrachteten Knotens v sind, wird traverse() mit diesen Knoten ( G_graph::omega()) und einer höheren Rekursionstiefe aufgerufen.