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]:
../_images/matplotlib_graph-tool_12_0.svg