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.
Java
public class DcalNode
{
DcalNode prev;
DcalNode next;
DcalArc arclist;
V2i info;
// Konstruktor
..
}
public class DcalArc
{
Object prev;
DcalArc next;
DcalNode endnode;
E2i info;
// Konstruktor
..
}
public class Dcal
{
DcalNode root;
DcalNode prevNode; // see findNode
DcalArc currArc; // see findArc, deleteArc
DcalArc prevArc; // see findArc
DcalArc newArc; // see insertArc
public Dcal() {..}
public DcalNode findNode(V2i i, int r) {..}
public DcalNode findNode(V2i i) {..}
public boolean insertNode(V2i i, int r) {..}
public boolean insertNode(V2i i) {..}
public void deleteNode(DcalNode node) {..}
public boolean isSingleNode(DcalNode node) {..}
public DcalArc findArc(DcalNode start, DcalNode end) {..}
public boolean insertArc(DcalNode start, DcalNode end) {..}
public boolean deleteArc(DcalNode start, DcalNode end) {..}
public void create(V2i[] start, V2i[][] end, E2i[][] arcs) {..}
public String toString() {..}
}
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.
Java
public class DcalGraph
{
private boolean fResetCounter;
private int count_insert_arc;
private int count_delete_arc;
private int count_move;
private DcalNode startnode;
private int radius;
private Arrow arrow;
Dcal dcal;
public DcalGraph()
{
this.fResetCounter = false;
this.count_insert_arc = 0;
this.count_delete_arc = 0;
this.count_move = 0;
this.radius = 10;
this.startnode = null;
this.arrow = new Arrow();
this.dcal = new Dcal();
}
public void paint(Graphics g, int width, int height) {..}
public boolean moveNodeStart(V2i o) {..}
public boolean moveNode(int x, int y) {..}
public boolean moveNodeEnd() {..}
public int insertArc(V2i o) {..Dcal::insertArc()..}
public int deleteArc(V2i o) {..Dcal::deleteArc() | Dcal::deleteNode()...}
public boolean insertNode(V2i o) {..Dcal::insertNode()..}
public void initCounter() {..}
public void resetCounter() {..}
}
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().
Java
public class GraphComp
extends JComponent
implements ActionListener, ComponentListener, MouseMotionListener, MouseListener
{
private static final long serialVersionUID = 1L;
Container cpane;
DcalGraph dg; DcalGraph dgZfl; DcalGraph dgBsp;
public void paint(Graphics g)
{dg.paint(g, this.getWidth(), this.getHeight());}
public GraphComp(Container cpane) throws HeadlessException
{
super();
this.cpane = cpane;
this.addComponentListener(this);
this.dgZfl = new DcalGraph();
this.dgBsp = new DcalGraph();
V2i nodes[] = {
/* 0 */new V2i(21, 175),
/* 1 */new V2i(73, 175),
/* 2 */new V2i(162, 61),
/* 3 */new V2i(162, 161),
/* 4 */new V2i(162, 270),
/* 5 */new V2i(251, 175),
/* 6 */new V2i(336, 175) };
V2i arcs[][] = {
/* 0 */{ nodes[1] },
/* 1 */{ nodes[2], nodes[3], nodes[4] },
/* 2 */{ nodes[5] },
/* 3 */{ nodes[5] },
/* 4 */{ nodes[5] },
/* 5 */{ nodes[6] },
/* 6 */{} };
E2i arcsinfo[][] = {
/* 0 */{ new E2i("Wände",15) },
/* 1 */{ new E2i("Putz",10), new E2i("Dach",7), new E2i("Innenausbau",7) },
/* 2 */{ new E2i("Garten",3) },
/* 3 */{ new E2i("decken",5) },
/* 4 */{ new E2i("Möbel",2) },
/* 5 */{ new E2i("Einzug",1) },
/* 6 */{} };
dgBsp.dcal.create(nodes, arcs, arcsinfo);
}
public boolean createFkt(String sfkt)
{
this.dg = this.dgZfl; //Zeichenfläche
this.dg = this.dgBsp; // Beispiel
..
}
public void mousePressed(MouseEvent e)
{
BUTTON3 -> moveNodeStart
}
public void mouseReleased(MouseEvent e)
{
BUTTON1 -> insertArc
BUTTON3 -> insertNode | moveNodeEnd
BUTTON1 & SHIFT_DOWN -> deleteArc
BUTTON1 & CTRL_DOWN -> showMsg(toString)
BUTTON3 & CTRL_DOWN -> showMsg(BEDIENUNG);
resetCounter
}
public void mouseDragged(MouseEvent e)
{
BUTTON3_DOWN -> moveNode
}
public void actionPerformed(ActionEvent e) {..}
}
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.