graph-tool

graph-tool provides a graph class and several algorithms that work with it. The internals of this class and most of the algorithms are written in C++ for performance reasons and use the Boost Graph Library.

Installation

graph-tool is a C++ library wrapped in Python with many C++ dependencies such as Boost, CGAL, CGAL and expat. Therefore, the easiest way to install graph-tool is with a package manager for Linux distributions and macOS:

Linux

For Debian or Ubuntu you can add the following line to your /etc/apt/sources.list:

deb [arch=amd64] https://downloads.skewed.de/apt DISTRIBUTION main

where DISTRIBUTION can be one of the following values:

bullseye, buster, sid, bionic, eoan, focal, groovy

You should then download the public key 612DEFB798507F25 to check the packages with the following command:

$ apt-key adv --keyserver keys.openpgp.org --recv-key 612DEFB798507F25

After running apt update, the package can be installed with

$ apt install python3-graph-tool

macOS

Installation is also straightforward with Homebrew:

$ brew install graph-tool

We then have to tell the Python interpreter where it can find graph-tool:

$ export PYTHONPATH="$PYTHONPATH:/usr/local/Cellar/graph-tool/2.43/lib/python3.9/site-packages"

Testing the installation

[1]:
from graph_tool.all import *

Creating and manipulating graphs

An empty graph can be created by instantiating a graph class:

[2]:
g = Graph()

A graph can be changed from directed to undirected at any time using the set_directed() method. The direction of the graph can be queried using the is_directed() method:

[3]:
ug = Graph()
ug.set_directed(False)
assert ug.is_directed() == False

Once a graph has been created, it can be filled with nodes and edges. A vertex can be added using the add_vertex() method, which returns an instance of a vertex class, also known as a vertex descriptor. For example, the following code creates two nodes and returns vertex descriptors that are stored in the variables v1 and v2:

[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