{ "cells": [ { "cell_type": "markdown", "id": "fe3ccc19", "metadata": {}, "source": [ "# graph-tool\n", "\n", "[graph-tool](https://graph-tool.skewed.de/) 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](https://www.boost.org)." ] }, { "cell_type": "markdown", "id": "bc1f8a93", "metadata": {}, "source": [ "## Installation\n", "\n", "graph-tool ist eine in Python verpackte C++-Bibliothek mit vielen C++-Abhängigkeiten wie [Boost](https://www.boost.org), [CGAL](https://www.cgal.org) und [expat](https://libexpat.github.io). Daher lässt sich graph-tool am einfachsten installieren mit einem Paketmanager für Linux-Distributionen und macOS:\n", "\n", "### Linux\n", "\n", "Für Debian oder Ubuntu könnt ihr die folgende Zeile zu eurer `/etc/apt/sources.list` hinzufügen:\n", "\n", "```\n", "deb [arch=amd64] https://downloads.skewed.de/apt DISTRIBUTION main\n", "```\n", "wobei `DISTRIBUTION` einer der folgenden Werte sein kann:\n", "```\n", "bullseye, buster, sid, bionic, eoan, focal, groovy\n", "```\n", "Anschließend solltet ihr den öffentlichen Schlüssel [612DEFB798507F25](https://keys.openpgp.org/search?q=612DEFB798507F25) herunterladen, um die Pakete mit dem folgenden Befehl zu überprüfen:\n", "\n", "``` bash\n", "$ apt-key adv --keyserver keys.openpgp.org --recv-key 612DEFB798507F25\n", "```\n", "\n", "Nach dem Ausführen von `apt update` kann das Paket installiert werden mit\n", "\n", "``` bash\n", "$ apt install python3-graph-tool\n", "```\n", "\n", "### macOS\n", "\n", "Mit [Homebrew](https://brew.sh/) ist die Installation ebenfalls unkompliziert:\n", "\n", "``` bash\n", "$ brew install graph-tool\n", "```\n", "\n", "Anschließend müssen wir dem Python-Interpreter noch mitteilen, wo er `graph-tool` finden kann:\n", "\n", "``` bash\n", "$ export PYTHONPATH=\"$PYTHONPATH:/usr/local/Cellar/graph-tool/2.43/lib/python3.9/site-packages\"\n", "```" ] }, { "cell_type": "markdown", "id": "37efd152", "metadata": {}, "source": [ "### Testen der Installation" ] }, { "cell_type": "code", "execution_count": 1, "id": "08e6ea3d", "metadata": {}, "outputs": [], "source": [ "from graph_tool.all import *" ] }, { "cell_type": "markdown", "id": "88f81a8a", "metadata": {}, "source": [ "## Erstellen und Manipulieren von Graphen\n", "\n", "Ein leerer Graph kann durch Instanziierung einer Graph-Klasse erstellt werden:" ] }, { "cell_type": "code", "execution_count": 2, "id": "3872c84f", "metadata": {}, "outputs": [], "source": [ "g = Graph()" ] }, { "cell_type": "markdown", "id": "f12cc83e", "metadata": {}, "source": [ "Ein Graph kann mit der Methode [set_directed()](https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.set_directed) jederzeit von gerichtet auf ungerichtet umgestellt werden. Dabei kann die Richtung des Graphen mit der Methode [is_directed()](https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.is_directed) abgefragt werden:" ] }, { "cell_type": "code", "execution_count": 3, "id": "0a25db83", "metadata": {}, "outputs": [], "source": [ "ug = Graph()\n", "ug.set_directed(False)\n", "assert ug.is_directed() == False" ] }, { "cell_type": "markdown", "id": "ea48046c", "metadata": {}, "source": [ "Sobald ein Graph erstellt ist, kann er mit Knoten und Kanten gefüllt werden. Ein Knoten kann mit der Methode [add_vertex()](https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.add_vertex) hinzugefügt werden, die eine Instanz einer [Vertex](https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.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:" ] }, { "cell_type": "code", "execution_count": 4, "id": "91d2b7e2", "metadata": {}, "outputs": [], "source": [ "v1 = g.add_vertex()\n", "v2 = g.add_vertex()" ] }, { "cell_type": "code", "execution_count": 5, "id": "46575a65", "metadata": {}, "outputs": [], "source": [ "e = g.add_edge(v1, v2)" ] }, { "cell_type": "code", "execution_count": 6, "id": "e3294c6b", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "', for Graph 0x1814b13d0, at 0x181ea0520>" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graph_draw(g, vertex_text=g.vertex_index, output=\"two-nodes.svg\")" ] }, { "cell_type": "code", "execution_count": 7, "id": "a551f87f", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", "\n", " \n", "\n", "\n", "" ], "text/plain": [ "" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from IPython.display import SVG\n", "SVG('two-nodes.svg')" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3.11 Kernel", "language": "python", "name": "python311" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.11.4" }, "latex_envs": { "LaTeX_envs_menu_present": true, "autoclose": false, "autocomplete": true, "bibliofile": "biblio.bib", "cite_by": "apalike", "current_citInitial": 1, "eqLabelWithNumbers": true, "eqNumInitial": 1, "hotkeys": { "equation": "Ctrl-E", "itemize": "Ctrl-I" }, "labels_anchors": false, "latex_user_defs": false, "report_style_numbering": false, "user_envs_cfg": false } }, "nbformat": 4, "nbformat_minor": 5 }