Algorithmen programmieren
Die Verbindung von CindyScript und Visage ermöglicht es, mit wenig Aufwand eigene Graphenalgorithmen zu programmieren und ihr Ergebnis visuell sichtbar zu machen. Die Visualisierung der einzelnen Schritte der Algorithmen ist dabei in verschieden ausführlichen Stufen machbar. Mit Hilfe der Visage-Erweiterung für CindyScript wird das Programmieren von Graphen-Algorithnen sogar noch einfacher. Programmieren - fast in Umgangssprache!
Obwohl CindyScript bereits alle benötigten Befehle enthält, um die in der Zeichenoberfläche konstruierten Graphen zu beeinflussen und auf ihnen Algorithmen ablaufen zu lassen, wirkt es zum Teil etwas "kryptisch", wie auf die Attribute der Knoten und Kanten zugegriffen werden muss. Deshalb stellen wir eine Bibliothek mit einfachen Funktionen zur Verfügung, die das Programmieren erleichtern sollen. Darüber hinaus werden einige kleine, häufig gebrauchte Algorithmen als fertige Funktionen zur Verfügung gestellt. Diese Bibliothek wir in Zukunft noch stark erweitert, so dass es lohnt, von Zeit zu Zeit nach einem Update zu sehen.
Verwendung der Visage Graphen-Bibliothek
Laden Sie zunächst die folgende Datei herunter:
Download visage.vgl
Speichern Sie diese Datei zum Beispiel in einem Ordner für ihre eigenen Visage-Konstruktionen. Merken Sie sich den Pfad zu dieser Datei!
Wenn Sie nun anfangen wollen, einen eigenen Algorithmus mit Visage zu programmieren, dann starten Sie Cinderella und öffnen dort den ScriptEditor. Geben Sie im Bereich "Initialisierung" als erstes den Befehl import("C:\Dokumente und Einstellungen\Benutzername\Desktop\CinderellaKonstruktionen\visage.vgl"); ein, falls Sie diese Datei z.B. unter Windows in einem Ordner CinderellaKonstruktionen auf dem Desktop gespeichert haben. Passen Sie bitte diese Pfadangabe an Ihren Speicherort an!
Nun können Sie mit der Programmierung beginnen! Dabei empfiehlt es sich, weitere Funktionsdefinitionen ebenfalls in den Initialisierungsbereich zu schreiben, alle Programmschritte, die von dem aktuell gezeichneten Graphen abhängen jedoch in den Bereich Draw zu packen.
Ein Beispiel für eine solche Implementation finden Sie u.a. in dem Artikel über den Algorithmus von Prim im Bereich Minimal Aufspannende Bäume.
Funktionsumfang und Dokumentation der Funktionen
Listen von Objekten des Graphen
Zugriff auf Attribute der Objekte des Graphen
Verschiedene Markierungen an Objekten setzen und lesen
Man kann jedem Cinderella-Objekt (Punkt, Gerade, Knoten, Kante, ...) beliebige Markierungen anfügen. Dies können kleine Texte, Zahlen, oder sonstiges sein, was man sich merken will. Solche Markierungen funktionieren also wie Variablen, nur dass sie an ein Objekt geheftet sind.
Zu einer Markierung gehören immer drei Informationen:
Für einige übliche, oft verwendete Markierungen haben wir schon Funktionen vordefiniert, die uns die Arbeit erleichtern.
Geplante Funktionen für die nächste Version
Obwohl CindyScript bereits alle benötigten Befehle enthält, um die in der Zeichenoberfläche konstruierten Graphen zu beeinflussen und auf ihnen Algorithmen ablaufen zu lassen, wirkt es zum Teil etwas "kryptisch", wie auf die Attribute der Knoten und Kanten zugegriffen werden muss. Deshalb stellen wir eine Bibliothek mit einfachen Funktionen zur Verfügung, die das Programmieren erleichtern sollen. Darüber hinaus werden einige kleine, häufig gebrauchte Algorithmen als fertige Funktionen zur Verfügung gestellt. Diese Bibliothek wir in Zukunft noch stark erweitert, so dass es lohnt, von Zeit zu Zeit nach einem Update zu sehen.
Verwendung der Visage Graphen-Bibliothek
Laden Sie zunächst die folgende Datei herunter:
Download visage.vgl| File Title: |
Wenn Sie nun anfangen wollen, einen eigenen Algorithmus mit Visage zu programmieren, dann starten Sie Cinderella und öffnen dort den ScriptEditor. Geben Sie im Bereich "Initialisierung" als erstes den Befehl import("C:\Dokumente und Einstellungen\Benutzername\Desktop\CinderellaKonstruktionen\visage.vgl"); ein, falls Sie diese Datei z.B. unter Windows in einem Ordner CinderellaKonstruktionen auf dem Desktop gespeichert haben. Passen Sie bitte diese Pfadangabe an Ihren Speicherort an!
Nun können Sie mit der Programmierung beginnen! Dabei empfiehlt es sich, weitere Funktionsdefinitionen ebenfalls in den Initialisierungsbereich zu schreiben, alle Programmschritte, die von dem aktuell gezeichneten Graphen abhängen jedoch in den Bereich Draw zu packen.
Ein Beispiel für eine solche Implementation finden Sie u.a. in dem Artikel über den Algorithmus von Prim im Bereich Minimal Aufspannende Bäume.
Funktionsumfang und Dokumentation der Funktionen
Listen von Objekten des Graphen
| alledges() | Liefert eine Liste mit allen ungerichteten Kanten. |
| allarcs() | Liefert eine Liste mit allen gerichteten Kanten. |
| allvertices() | Liefert eine Liste mit allen Knoten. |
| incidentedges(vertice) | Liefert eine Liste mit allen zu einem Knoten inzidenten, ungerichteten Kanten. |
| incidentvertices(edge) | Liefert eine Liste mit allen zu einer Kante inzidenten Knoten. Die gegebene Kante darf gerichtet oder ungerichtet sein. Es werden beide Endknoten (bzw Start- und Endknoten) zurückgegeben. |
| getweight(edge) | Liefert das Gewicht einer Kante. |
| setweight(edge,w) | Setzt das Gewicht einer Kante auf den gegebenen Wert. |
Man kann jedem Cinderella-Objekt (Punkt, Gerade, Knoten, Kante, ...) beliebige Markierungen anfügen. Dies können kleine Texte, Zahlen, oder sonstiges sein, was man sich merken will. Solche Markierungen funktionieren also wie Variablen, nur dass sie an ein Objekt geheftet sind.
Zu einer Markierung gehören immer drei Informationen:
- Das Objekt, an dem sie gehaftet ist.
- Ein Name der Markierung. Dieser muss immer in " " stehen!
- Der Inhalt, was man sich merken will.
Für einige übliche, oft verwendete Markierungen haben wir schon Funktionen vordefiniert, die uns die Arbeit erleichtern.
Geplante Funktionen für die nächste Version
- Einführung eines Graphenobjekts
- Auswahl induzierter Teilgraphen einer Knotenmenge
- Implementierung von Standard-Algorithmen, die anwendbar auf Graphen oder Teilgraphen sind
- Darstellung und Handling von Pseudocode
- Schrittweises Ausführen von Algorithmen