Graf Propagations-Applet Weiter Unten >>

Disclaimer: Den hier beschriebenen Algorithmus benutzen wir zur Zeit nicht bei meinem Arbeitgeber, und ich habe ihn in meiner Freizeit entwickelt. Die Aufgabe wurde lediglich durch meine Arbeit inspiriert.

Übrigens, Sie können per Email benachrichtigt werden, wenn ein neuer Newsletter veröffentlicht wird. Einfach ein Profil einrichten – keine Sorge, ich verspreche, nicht zu Spammen!

Was ist überhaupt das Problem? Rechts ist ein Molekül abgebildet. Falls Sie sich wundern, daß viele Verbindungen kein Atomzeichen haben: Es ist üblich, Kohlenstoff (C) implizit durch die Ecken darzustellen, und Wasserstoff (H) wird nie gezeichnet. Aber das berührt unser Problem nicht.

Wieviele Ringe hat dieses Molekül? Auf den ersten Blick wissen wir, daß es vier sind. Allerdings würde ein Algorithmus wahrscheinlich fünf sehen. Warum? Der Doppelring links oben enthält zwei kleine Ringe, und einen beide kleinen Ringe umspannenden größeren Ring. Wie ich weiter unten beschreiben werde, müssen wir diese Ringe später wieder entfernen.

Wie sollen wir Ringe repräsentieren? Dazu zog ich Robert Sedgewick’s “Algorithms in C++” zu Rate (eine uralte Edition – inzwischen gibt’s auch eine Java Ausgabe). Denn ein Molekül kann als Graf dargestellt werden. Ein Graf besteht aus Punkten (Atomen), und Kanten zwischen diesen Punkten (Bindungen). Sedgewick schlägt zwei Datenstrukturen vor, um Grafen intern zu speichern. Für dieses Problem bietet sich die “adjacency-structure” Representation an. Bei dieser Representation haben wir eine Liste mit allen Punkten, die wiederum mit einer Liste von verbundenen Punkten assoziiert sind. Zum Beispiel würden wir die folgende Datenstruktur für Wasser (H1-O-H2) bekommen:

 H1 -> [ O ] H2 -> [ O ] O  -> [ H1 H2 ] 

Beachten Sie, daß jede Bindung zweimal auftaucht. Den “verschwendeten” Speicherplatz nehmen wir gerne in Kauf. In einem Molekül sind nicht alle Bindungen gleich (einfach, doppelt, etc.). Das könnten wir speichern, indem die Einträge in der Liste Datenstrukturen sind, die diese Information auch noch aufnehmen. Um unsere Ringe zu finden, ist der Bindungstyp allerdings unwichtig.

Unser erstes Ziel ist es, den gesamten Graf abzugrasen, und zwar immer entlang der Kanten. Dabei gibt es natürlich viele, viele Wege. Sedgewick bietet zwei Algorithmen an mögliche Wege zu finden: der eine geht in die Tiefe, der andere in die Breite. Hier ist ein Diagram aus seinem Buch das den Unterschied visualisiert:

Die roten Linien zeigen die ersten Schritte eines tiefen bzw. breiten Wanderalgorithmusses. Der tiefe springt so schnell wie möglich von Punkt zu Punkt, und kehrt nur dann zu Abzweigungen zurück, wenn es nicht weiter geht. Der breite folgt allen möglichen Abzweigungen, und geht erst dann weiter vorwärts, wenn alle Abzweigungen besucht wurden. Ich denke, es ist intuitiv klar, daß der breite Algorithmus kleine, geschlossene Ringe findet. Mit dem folgenden Applet können Sie selbst Grafen erstellen, und sie mit dem gleich beschriebenen Algorithmus propagieren lassen:

Ihr Browser unterstützt nicht das <APPLET> tag! Klicken erzeugt einen Punkt. Ziehen von einem Punkt zum anderen erzeugt eine Kante. Zum Propagieren, einen Punkt anklicken. Weiß: Noch nicht besucht Rot: Punkt wird besucht Gelb: Punkt wird untersucht Grau: Punkt wurde besucht

Aber wie funktionieren die Algorithmen, und wie benutzen wir sie? Ich werde hier nur den breiten beschreiben, weil wir den benutzen. Hier soll nur bemerkt werden, daß die Algorithmen sich ähneln, und daß der tiefe Algorithmus leicht rekursiv zu programmieren ist, während der breite sich gut als Schleife schreiben läßt. Und hier ist der Algorithmus:

Map graf; // Object -> Set von verbundenen Objekten Set visited; // Set von besuchten Objekten void visit(Object head) { List queue = new ArrayList(); queue.add(head); while (! queue.isEmpty()) { Object entry = queue.remove(0); visited.add(entry); // hier entry verarbeiten Set neighbors = (Set)graf.get(entry); for (Iterator i = neighbors.iterator(); i.hasNext();) { Object neighbor = i.next(); boolean wasVisited = visited.contains(neighbor); if (! wasVisited) queue.add(neighbor); } } } 

Ein paar Kommentare:

• Der Graf ist in der Variablen graf in der form einer Map gespeichert. Die keys sind die Knoten, die mit einem Set assoziiert sind, welches die verbundenen Knoten enthält.
• Das Set visited enthält die Knoten, die bereits besucht wurden, und muss vor jeder neuen iteration zurückgesetzt werden.
• Wenn die Funktion “visit” aufgerufen wird, werden alle verbundenen Punkte entlang ihrer Kanten berührt. Sollte der Graf nicht verbunden sein, so kann man einfach für alle Punkte im Graf (also über graf.getkeys() iterieren) visit aufrufen.

Ich hoffe, daß dieser Algorithmus, im Zusammenhang mit dem Applet die Zusammenhänge verständlich macht. der gesamte Code für das Applet ist verfügbar. Falls Sie mit dem Code experimentieren möchten, können Sie weitere Implementierungen des Interfaces Crawler erstellen.

• Crawler – ein Interface für die Implementierung von Algorithmen.
• WidthCrawler – Implementierung eines Crawlers, der in der Breite sucht.
• Visitor – Das Visitor Interface ist ein Argument für den Crawler, um beim Besuch eines Knoten Code ausführen zu können.
• DrawingCanvas – Die Benutzeroberfläche: Swing Canvas der es dem Benutzer ermöglicht, Grafen zu zeichnen und die Propagation visuell auszuführen.
• GrafDemo – Die Klasse stellt den Einstiegspunkt ins Programm zur Verfügung, das als Applet oder als Java Anwendung ausgeführt werden kann.

Wir haben zwar eine Menge geschafft heute, aber es gibt noch einiges zu tun, bis wir die Ringe haben. Vielleicht werde ich das Thema in der Zukunft noch einmal ansprechen. Falls nicht, hier sind die Schritte, die wir durchführen müssen, um die Ringe zu finden:

• Den Propagator anhalten, sobald der Anfangspunkt wiedergefunden wurde, ohne Ecken zweimal zu benutzen (einmal vor und zurück gilt nicht!). Dann haben wir nämlich einen Ring gefunden.
• Den Propagator für jedes Atom einmal ausführen. Damit finden wir alle Ringe, denn jeder Ring hat mindestens ein Atom, daß mit keinem anderen Ring geteilt wird.
• Ringduplikate ausfiltern!
• Doppelringe wie oben beschrieben rausfiltern. Das machen wir, indem wir Ringe suchen, die zwei oder mehr Kanten gemeinsam haben. Den größeren von den zweien entfernen wir.

Bleibt nur noch die Frage, ob wir mit diesem Algorithmus wirklich alle Ringe finden. Außerdem könnten wir noch die Performance des Algorithmus untersuchen. Ich überlasse dies gerne dem Leser.