MSB für planare Graphen nach Cheriton und Tarjan (1976)
Interaktive Version des Verfahrens
Bedienungsanleitung
Allgemeines
Allgemeine Sicherheitsvorkehrungen Ihres Browsers können dazu führen, dass das Applet
blockiert wird. Aus dem gleichen Grunde erscheinen Fenster, die Sie nach
dem Kantengewicht fragen, unter Umständen mit einem Warnton oder sonstigen
Warnhinweisen. Sehen Sie in diesen Fällen in den Browser-Optionen nach,
ob Sie für dieses Applet eine geringere Sicherheitsstufe einstellen können.
Damit das Applet funktioniert, benötigen Sie Java.
Eingabephase (Initialzustand)
Geben Sie mit der Maus einen gewichteten planaren Graphen ein:
- Knoten setzen: Linke Maustaste
- Kante setzen: Knoten 1 mit rechter Maustaste auswählen, dann Knoten 2 mit rechter Maustaste
auswählen. Sie werden dann nach dem Kantengewicht gefragt (muss eine ganze Zahl sein)
- Knoten löschen: Knoten mit rechter Maustaste auswählen, Entf(ernen) drücken
- Kante löschen: Kante mit rechter Maustaste auswählen, Entf(ernen) drücken
- Kantengewicht ändern: Kante mit linker Maustaste auswählen
Alternativ dazu können Sie auch mit dem Button "Graph wählen" einen der vordefinierten
Beispielgraphen laden (und ggf. mit obigen Mauseingaben verändern).
Sie können mit den am oberen Rand befindlichen Kästchen den Ablauf des Verfahrens
ein wenig steuern.
Starten Sie dann den Algorithmus über einen Klick auf den Button "Start".
Das Applet prüft nun, ob der Graph planar ist; falls nicht, erhalten Sie eine
Fehlermeldung und müssen den Graphen korrigieren.
Während der Algorithmus läuft
Die Anzeigefläche ist wie folgt eingeteilt:
- Am oberen Rand sehen Sie nach wie vor die Kästchen für einstellbare Optionen;
Sie können damit auch nach dem Start noch den Ablauf steuern
- Darunter sehen Sie links den Graph, wie ihn der Algorithmus momentan sieht. Da dieser
Knoten zusammfasst und Kanten löscht, verändert sich dieses Bild laufend
- Rechts neben dem Arbeitsgraph sehen Sie den Originalgraph. In diesem wird der
wachsende MSB eingezeichnet, wie ihn das Verfahren berechnet
- Unter der Graph-Anzeige sehen Sie den internen Zustand des Programms, d.h. den momentanen Inhalt
der interessanten Datenstrukturen
- Am unteren Rand befindet sich eine Leiste mit Buttons. Hier können Sie
das Verfahren kurz anhalten und wieder fortsetzen oder auch ganz abbrechen
Bedeutung der einstellbaren Optionen
Mit den Kästchen am oberen Rand können Sie den Ablauf wie folgt beeinflussen:
- vollautomatisch: Das Verfahren läuft alleine vollständig durch, wobei nach jedem
Schritt eine kleine Pause eingelegt wird, damit man das Vorgehen verfolgen kann.
- Einzelschritte: Es wird nur ein einzelner Schritt abgearbeitet und danach angehalten.
Der Benutzer kann dann über den Button "Weiter" selbst bestimmen, wann der
nächste Schritt erfolgen soll.
- clean-up komplett: Prinzipiell entspricht dies der Option "Einzelschritte", aber
die clean-up-Prozedur wird hier ohne anzuhalten vollständig abgearbeitet.
- Schleifendurchlauf komplett: Ist diese Option eingestellt, so wird ein Durchlauf der
Hauptschleife immer am Stück ausgeführt, mit kurzen Pausen nach jedem Einzelschritt.
Ist zugleich die Option "clean-up komplett" aktiviert, so wird clean-up
dabei vollständig abgearbeitet; andernfalls wird clean-up wie im Modus
"Einzelschritte" nicht komplett automatisch durchlaufen.
Sie können diese Einstellungen während der Eingabephase und auch später, während der Algorithmus
bereits läuft, immer wieder verändern.
Erstellt von: Stefan Staiger, 16.10.2004, Studienarbeit "Visualisierung Geometrischer Algorithmen"