Graphviz: Unterschied zwischen den Versionen

Aktuelle Version vom 25. Februar 2015, 19:22 Uhr

Ich möchte euch hier ein Tool zur Erzeugung von Bildern von Graphen (aus der Graphentheorie, also so etwas mit Ecken und Kanten) vorstellen. Das ist keine "Mathe"-Software wie z.B. GeoGebra oder Maxima, obwohl das Tool jede Menge Mathematik verwendet. Graphviz eignet sich auch gut zur automatischen Erstellung von Diagrammen und kann auch in Wikis eingebunden werden. Nach der Installation kann aus einer einfachenTextdatei, z.B.

viereck.dot

digraph G {
Viereck -> Trapez;
Viereck -> Drachen;
Drachen -> Raute;
Trapez -> Parallelogramm;
Parallelogramm -> Rechteck;
Parallelogramm -> Raute;
Rechteck -> Quadrat;
Raute -> Quadrat;
}

mit dem Kommando

dot viereck.dot -Tpng -o viereck.png

ein nettes Bildchen erstellt werden:

Das geht natürlich auch für Mindmaps oder ähnliche Diagramme. Graphviz ist frei verfügbar und kann z.B. hier heruntergeladen werden: http://www.graphviz.org/ (gibt’s auch für den Raspberry Pi) auch in Wikipedia findet ihr einen Artikel darüber http://de.wikipedia.org/wiki/Graphviz und es gibt viele gute Tutorials im Netz.

Ich habe mir insbesondere das dot Tool von Graphviz genauer angeschaut, weil ich eine Software suchte, die aus einem geeigneten Output meiner Programme (speziell für den BWInf) Graphen zeichnen kann.

Es gibt ein altes Rätsel, was als Einstieg zu einer Aufgabe der ersten Runde des 33. Bundeswettbewerbs Informatik geschildert wurde:

Zwei Personen haben drei Krüge mit dem Fassungsvermögen 8, 5 und 3 Liter. In dem größten Krug befinden sich 8 Liter (deines Lieblingsgetränks), das soll durch Umfüllen gerecht aufgeteilt werden, dass jeder vier Liter bekommt. In jedem Schritt kann nur von einem Krug in einen anderen umgefüllt werden. Wie kann man das in den wenigsten Schritten hinbekommen (durch das Umfüllen wird das Getränk nicht besser)?

Die Aufgabe war nun ein Programm zu schreiben, was derartige Probleme lösen kann.

Ich hatte zur Lösung einen Ansatz mit Graphentheorie gewählt, jeder durch Umfüllen mögliche Zustand wird als Knoten und jeder Übergang als Kante eines Graphen betrachtet. Dann kann man das Problem lösen, indem man einen kürzesten Weg zwischen dem Anfangszustand und einem Lösungszustand sucht (oder besser suchen lässt). Dafür hatte ich vorher schon mal Funktionen geschrieben (Mathematiker führen Probleme ja am liebsten auf bereits gelöste Probleme zurück). Was mir noch fehlte war eine ansprechende Ausgabe und die bekommt man nun mit Graphviz. Da mir mein Programm Graph und Lösung liefert, musste ich daraus nur noch eine .dot-Eingabedatei für Graphviz erstellen lassen.

Der Startzustand ist blau angezeigt, Lösungszustände sind grün dargestellt und ein kürzester Pfad ist grün eingezeichnet (hier ist allerdings nicht die Rückrichtung eingezeichnet).