Graphviz: Unterschied zwischen den Versionen
| (7 dazwischenliegende Versionen von einem Benutzer werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
| + | [[Kategorie:Matheprogramme]] | ||
| + | |||
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. | 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 | viereck.dot | ||
| − | digraph G { | + | digraph G {<br /> |
| − | Viereck -> Trapez; | + | Viereck -> Trapez;<br /> |
| − | Viereck -> Drachen; | + | Viereck -> Drachen; <br /> |
| − | Drachen -> Raute; | + | Drachen -> Raute;<br /> |
| − | Trapez -> Parallelogramm; | + | Trapez -> Parallelogramm;<br /> |
| − | Parallelogramm -> Rechteck; | + | Parallelogramm -> Rechteck;<br /> |
| − | Parallelogramm -> Raute; | + | Parallelogramm -> Raute;<br /> |
| − | Rechteck -> Quadrat; | + | Rechteck -> Quadrat;<br /> |
| − | Raute -> Quadrat; | + | Raute -> Quadrat;<br /> |
| − | } | + | }<br /> |
| + | |||
mit dem Kommando | mit dem Kommando | ||
| Zeile 20: | Zeile 23: | ||
ein nettes Bildchen erstellt werden: | ein nettes Bildchen erstellt werden: | ||
| − | [[Datei: | + | [[Datei:StammbaumViereck.png]] |
| + | |||
| + | 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:<br /> | ||
| + | |||
| + | 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. | ||
| + | |||
| + | [[Datei:Graph zur Lösung des Dreikrügeproblems.gif|Erstellt mit dem dot Tool von Graphviz aus einer automatisch erzeugten .dot-Datei.]] | ||
| + | |||
| + | 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). | ||
Aktuelle Version vom 25. Februar 2015, 18: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).
