Tutorial : Java-Applet

Gerichtete Gaphen - eine Implementierungsskizze

Erstes Kernstück ist schlicht der Punkt im kartesischen Koordinatensystem. Ein paar Überlegungen führen dazu alle Punkte am Bildschirm als Kreisflächen mit ein-und-demselben Radius darzustellen. Schon hat man eine erste Klasse, wobei der Radius darin nur als Methoden-Parameter vorkommt: die „V2i” genannte Klasse hat mit den Punktkoordinaten die Eigenschaften x und y und zur Identifikation die Methoden equals() und hit().

Damit ist bereits eine Komponente realisierbar, die mit jedem Klick auf einen Bildschirmbereich einen Kreis zeichnet. Um beliebig viele Punkte zu zeichnen, werden Punktobjekte dynamisch erzeugt, die dann verstreut im Speicher liegen und die daher durch doppelte Verkettung erreichbar gemacht werden. Das ergibt die Klasse „DcalNode” mit einem Objekt der Klasse „V2i” und zwei Objekte (voriger, nächster Punkt) derselben Klasse „DcalNode” als Eigenchaften.

Zweites Kernstück sind Beziehungen zwischen Punkten. Die visuelle Repräsentation kann einfach eine gerade Linie zwischen jeweils zwei Punkten sein. Relevant ist die Bildung von Punktemengen: da potentiell jeder (Start-)Punkt mit einer beliebigen Anzahl von (End-)Punkten in Beziehung stehen kann, werden Beziehungen ebenfalls als doppelt verkettete Listen implementiert. Das ergibt die Klasse „DcalArc” mit den Eigenschaften prev, next, endnode und info. Das erste Listenelement zeigt mit prev zum Startpunkt, alle folgenden Listenelemente zeigen zur vorigen Beziehung zurück. Die Eigenschaft info, als Klasse „E2i” implementiert, hat hier keine identifizierende Bedeutung, wie die anloge Eigenschaft info der Klasse „V2i” bei den Punkten. Beziehungen werden mit den oben erwähnten Methoden equals() und hit() durch ihre Start- und Endpunkte idenifiziert.

Eine zusammenfassende Klasse „Dcal” mit der einzig wesentlichen Eigenschaft root, ein Objekt der Klasse „DcalNode”, stellt alle Methoden zur Verfügung, womit ein gerichteter Graph „numerisch” implementiert werden kann.

Die skizzierte Datenstruktur ist in der Literatur ausreichend dokumentiert. Stichwort: „doubly connected arc list”.

Zwei weitere Klassen machen diese Datenstruktur bedienbar: eine Klasse „DcalGraph” ist Schnittstelle zwischen Datenstruktur und Benutzer und übernimmt die grapische Darstellung und eine Klasse "GraphComp" realisiert schließlich die Schnittstelle zwischen Benutzer und dem Java-API.

Die Klasse „DcalGraph” hat im wesentlichen mit radius den Radius der Punkte, mit arrow ein Objekt der Klasse „Arrow” zum Zeichnen der Pfeilspitzen und mit dcal ein Objekt der Klasse „Dcal” als Eigenschaften. Die Methoden insertArc() und deleteArc() haben hier jeweils nur eine Punktinformation als Parameter, denn zum Einfügen oder Löschen von Beziehungen werden diese Methoden zweimal aufgerufen: erster Aufruf mit der Punktinformation für den Startpunkt, zweiter Aufruf mit der Punktinformation für den Endpunkt. Diese Vorgehensweise spielt der Benutzerschnittstelle in die Hände. Und bis auf die Methode paint() haben auch die übrigen Methoden eigentlich nichts direkt mit der graphischen Implementierung am Hut.

Die als Java-Komponente ausgelegte Klasse "GraphComp" bildet die Senke für Ereignisse, die durch Benutzeraktionen beim Einsatz der Geräte Maus, Tastatur, Bildschirm ausgelöst wurden.

In dem Fall wurden darin zwei gerichtete Graphen eingebaut: ein leerer Graph (dgZfl) und ein Beispiel (dgBsp), beides Objekte der Klasse „DcalGraph”. Die weitere Eigenschaft dg derselben Klasse repräsentiert den aktuellen Graphen. Aus Benutzersicht stehen damit zwei Funktionen zur Verfügung. Die Funktionsauswahl erfolgt durch die Methoden actionPerformed() und createFkt().

In einer bottom-up-Betrachtung wurde damit eine Implementierung gerichteter Graphen mittels doppelt verketteter Listen skizziert.

Als Anwendungsfall sehen Sie im nächsten Kapitel eine Implementierungsskizze der Methode des kritischen Pfades (CPM) und der dafür erforderlichen topologischen Sortierung der Punkte des Graphen.