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]: