Graph
und der Graphen-EditorGraph.complete(12)
Die folgenden Beispiele zeigen einige Möglichkeiten der Klasse Graph
,
des Graphen-Editors und des Wechselspiels zwischen beiden.
Ein Graph besteht aus Knoten und Kanten. Eine Kante verbindet zwei Knoten.
Zwar gehört zur Definiton eines Graphen keine Information über eine geometrische Anordnung. In der Praxis hilft es aber oft,
wenn man einen Graphen als Punkte (Knoten) und Verbindungslinien (Kanten) zeichnet.
Wir wollen zunächst einen Graphen mit drei Knoten (1, 2, 3) und zwei Kanten definieren, die Knoten 1 mit den beiden anderen Kanten verbinden:
g = Graph.fromShortRepr("1; 2; 3 | 1,2; 1,3")
Da dieser "reine" Graph keine geometrischen Informationen enthält, werden Sie enttäuscht sein, wenn Sie ihn im Graphen-Editor betrachten:
g.display()
Klicken sie nun bitte im Graphen-Editor auf das Zeigefingersymbol
und bewegen Sie die Knoten an drei verschiedene Plätze, so dass die zwei Kanten sichtbar werden.
Versuchen Sie, einen vierten Knoten und eine weitere Kante hinzuzufügen
(Wählen Sie dafür aus der Graphen-Symbolleiste das Knoten- und dann das Kantenwerkzeug aus!).
Jetzt wollen wir den umgekehrten Weg gehen und den erweiterten Graphen in ein Objekt verwandeln.
Dazu klicken Sie in der Graphen-Symbolleiste auf das Bleistiftsymbol (rechts).
Nun sollte etwas Ähnliches im Eingabefenster stehen:
Graph.fromShortRepr("1,26,165;2,153,124;3,50,50;4,159,49|1,3;1,2;3,4")
Nun definieren wir einen gewichteten Graphen. Dazu wird bei den Kanten als dritter Wert das Gewicht angegeben
# Beispiel für einen gewichteten Graphen: g = Graph.fromShortRepr(""" 1,100, 20; 2,260,20; 3,20,100; 4,180,100; 5,340,100; 6, 20,180; 7,180,180; 8,340,180; 9,100,260; 10,260,260 | 1,2,36; 1,4,15; 2,4,69; 2,5,1; 4,5,53; 3,4,92; 1,3,99; 3,6,37; 6,7,21; 7,8,88; 4,6,27; 4,7,32; 5,7,10; 5,8,66; 6,9,3; 7,9,18; 7,10,49; 8,10,43; 9,10,74""") g.display(1) # Anzeige im 1. Graphen-Fenster
Wir lassen uns einen minimalen Spannbaum (mit Hilfe des Kruskal-Algorithmus) berechnen...
g.highlightMinimalSpanTree(trace=True)
... und im 2. Graphen-Fenster anzeigen.
g.display(2)
Mit dem Dijkstra-Algorithmus berechnen wir einen kürzesten Weg von Knoten 2 nach Knoten 9 ...
g.highlightShortestPath(2,9)
... und zeigen ihn im 3. Graphen-Fenster an.
g.display(3)