graph-tool#
graph-tool stellt eine Graph-Klasse und mehrere Algorithmen zur Verfügung, die mit ihr arbeiten. Die Interna dieser Klasse und der meisten Algorithmen sind aus Leistungsgründen in C++ geschrieben und verwenden die Boost Graph Library.
Installation#
graph-tool ist eine in Python verpackte C++-Bibliothek mit vielen C++-Abhängigkeiten wie Boost, CGAL und expat. Daher lässt sich graph-tool am einfachsten installieren mit einem Paketmanager für Linux-Distributionen und macOS:
Linux#
Für Debian oder Ubuntu könnt ihr die folgende Zeile zu eurer /etc/apt/sources.list hinzufügen:
deb [arch=amd64] https://downloads.skewed.de/apt DISTRIBUTION main
wobei DISTRIBUTION einer der folgenden Werte sein kann:
bullseye, buster, sid, bionic, eoan, focal, groovy
Anschließend solltet ihr den öffentlichen Schlüssel 612DEFB798507F25 herunterladen, um die Pakete mit dem folgenden Befehl zu überprüfen:
$ apt-key adv --keyserver keys.openpgp.org --recv-key 612DEFB798507F25
Nach dem Ausführen von apt update kann das Paket installiert werden mit
$ apt install python3-graph-tool
macOS#
Mit Homebrew ist die Installation ebenfalls unkompliziert:
$ brew install graph-tool
Anschließend müssen wir dem Python-Interpreter noch mitteilen, wo er graph-tool finden kann:
$ export PYTHONPATH="$PYTHONPATH:/usr/local/Cellar/graph-tool/2.43/lib/python3.9/site-packages"
Testen der Installation#
[1]:
from graph_tool.all import *
Erstellen und Manipulieren von Graphen#
Ein leerer Graph kann durch Instanziierung einer Graph-Klasse erstellt werden:
[2]:
g = Graph()
Ein Graph kann mit der Methode set_directed() jederzeit von gerichtet auf ungerichtet umgestellt werden. Dabei kann die Richtung des Graphen mit der Methode is_directed() abgefragt werden:
[3]:
ug = Graph()
ug.set_directed(False)
assert ug.is_directed() == False
Sobald ein Graph erstellt ist, kann er mit Knoten und Kanten gefüllt werden. Ein Knoten kann mit der Methode add_vertex() hinzugefügt werden, die eine Instanz einer Vertex-Klasse, auch vertex descriptor genannt, zurückgibt. Der folgende Code erstellt beispielsweise zwei Knoten und gibt vertex descriptors zurück, die in den
Variablen v1 und v2 gespeichert sind:
[4]:
v1 = g.add_vertex()
v2 = g.add_vertex()
[5]:
e = g.add_edge(v1, v2)
[6]:
graph_draw(g, vertex_text=g.vertex_index, output="two-nodes.svg")
[6]:
<VertexPropertyMap object with value type 'vector<double>', for Graph 0x1814b13d0, at 0x181ea0520>
[7]:
from IPython.display import SVG
SVG('two-nodes.svg')
[7]:
