Algorithmen animieren - wie vorgehen?

[RalU]

Hallo Forum!

Ich bearbeite ein kleines JAVA-Projekt, bei dem bestimmte Flussalgorithmen animiert werden sollen. Auf einem Flussnetzwerk (bestehend aus Knoten und Kanten), dass in einer GUI (JAVA-Swing) angezeigt wird, soll zunächst ein bestimmter Algorithmus ausgeführt werden. Dabei soll jede Änderung im Flussnetzwerk (z.B. Änderung des maximalen Flusses, Flusswerte, etc.) für den User sichtbar gemacht werden. So sollen z.B. betreffende Kanten gefärbt werden, und/oder die Kantenbeschriftungen geändert werden.

Jetzt stell ich mir die Frage, wie man grundsätzlich vorgehen kann, um diese "Einzelschritte" des Algorithmus entsprechend zu animieren.
Eine Möglichkeit wäre ja, mit Threads zu arbeiten. Also ein Thread führt den Algorithmus ganz normal aus, wobei dann mit "sleep(...)" nach jedem "Einzelschritt" unterbrochen wird, um die Änderungen im Netzwerk vorzunehmen - sprich Kantenfärbungen, etc.

Gibt es noch andere Möglichkeiten/Vorgehensweisen, außer mit Threads zu arbeiten?
Welche Vor- und Nachteile gibt es?

Mit freundlichen Grüßen,
Ralf

 

[Thomas Darimont]

Hallo,

mit sowas habe ich auch schon mal herumgespielt.
Im Prinzip musst du deine zu Visualisierenden Algorithmen so abstrahieren, dass du die Berechnungsschritte einzelnen aufrufen kannst.

Sprich du hättest im Prinzip sowas wie:

interface IAlgorithm{

        void step();

    }

Ein Algorithmus besteht natürlich nicht nur aus Schritten sondern er arbeitet natürlich auch auf einem gewissen Kontext nämlich den Daten.

Die initiale Belegung des Kontexts stellt die Ausgangslage dar. Zur Visualisierung stellt man einfach den aktuellen Kontext grafisch dar. Bei jedem Aufruf von step() wird nun ein weiterer Berechungsschritt auf dem Kontext ausgeführt. Nach jedem Berechnungsschritt (oder bei jeder "relevanten" Kontextänderung) aktualisiert man die Kontext Darstellung. Der Aufruf von step() kann nun durch Benutzerinteraktion oder Timer-gesteuert erfolgen.

Ein einfacher aber auch sehr aufwendiger und wenig wiederverwendbarer Ansatz wäre auch den Algorithmus in einer abstrakten Objektstruktur zu repräsentieren. Dann könnte man auch dort die nötigen Hooks zur Aktualisierung der Darstellung realsieren.

Ein weiterer Ansatz wäre eine Sprache (Pseudocode vielleicht direkt aus dem Cormen -> http://www.amazon.de/Introduction-A...ie=UTF8&s=books-intl-de&qid=1255507722&sr=8-1 ;-) oder auch ,... in Java) zu interpertieren und sich in den Interpreter reinzuhängen und dort die Ausführungsschritte zu intercepten (Beispielsweise Zuweisungen die den relevanten Kontext ändern).

Noch cooler wäre allerdings folgendes.

Man schreibt seinen Algorithmus ganz normal in Java.
Die Attribute welche die für die Visualisierung relevanten Daten enthalten werden im Code (via Annotations) oder außerhalb vom Code (XML Metadaten) besonders ausgezeichnet.

Nun läd man die Klasse über einen speziellen Classloader der den Bytecode der Klasse so manipuliert / instrumentiert, dass bei bei Änderungen an relevanten Daten im Kontext eine Methode aufgerufen wird. Diese Methode könnte die oben zitierte step() Methode sein.

Die Instrumentierung könnte man mit BCEL, ASM oder via AspectJ durchführen.

Nun könnte man einen generischen Visualisier bauen der über eine Reihe von Visualisierungsstrategien (für Listen/Felder bei Sortieralgorithmen, für Knoten / Kanten bei Graphenalgorithmen, etc...) kennt die anhand der Metadaten zum Algorithmus die Darstellung durchführen. Eine Aktualisierung der Darstellung geschieht dann über einen Aufruf von step();

Hier mal ein Beispiel wie so was ausschauen kann.
http://links.math.rpi.edu/applets/appindex/graphtheory.html
http://codeidol.com/java/java-algorithms/Elementary-Sorting-Methods/Algorithm-Visualization/

Gruß Tom