| 1 |
% Copyright 2019 by Renée Ahrens, Olof Frahm, Jens Kluttig, Matthias Schulz, Stephan Schuster |
| 2 |
% Copyright 2019 by Till Tantau |
| 3 |
% Copyright 2019 by Jannis Pohlmann |
| 4 |
% |
| 5 |
% This file may be distributed and/or modified |
| 6 |
% |
| 7 |
% 1. under the LaTeX Project Public License and/or |
| 8 |
% 2. under the GNU Free Documentation License. |
| 9 |
% |
| 10 |
% See the file doc/generic/pgf/licenses/LICENSE for more details. |
| 11 |
|
| 12 |
|
| 13 |
\section{Introduction to Algorithmic Graph Drawing} |
| 14 |
\label{section-intro-gd} |
| 15 |
|
| 16 |
\emph{by Till Tantau} |
| 17 |
|
| 18 |
\ifluatex |
| 19 |
\else |
| 20 |
This section of the manual can only be typeset using Lua\TeX. |
| 21 |
\expandafter\endinput |
| 22 |
\fi |
| 23 |
|
| 24 |
|
| 25 |
\subsection{What Is Algorithmic Graph Drawing?} |
| 26 |
|
| 27 |
\emph{Algorithmic graph drawing} (or just \emph{graph drawing} in the |
| 28 |
following) is the process of computing algorithmically where the nodes of a |
| 29 |
graph are positioned on a page so that the graph ``looks nice''. The idea is |
| 30 |
that you, as human (or you, as a machine, if you happen to be a machine and |
| 31 |
happen to be reading this document) just specify which nodes are present in a |
| 32 |
graph and which edges are present. Additionally, you may add some ``hints'' |
| 33 |
like ``this node should be near the center'' or ``this edge is pretty |
| 34 |
important''. You do \emph{not} specify where, exactly, the nodes and edges |
| 35 |
should be. This is something you leave to a \emph{graph drawing algorithm}. The |
| 36 |
algorithm gets your description of the graph as an input and then decides where |
| 37 |
the nodes should go on the page. |
| 38 |
% |
| 39 |
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing} |
| 40 |
\usegdlibrary{trees}}] |
| 41 |
\tikz \graph [binary tree layout, level distance=5mm] { |
| 42 |
4 -- { |
| 43 |
3 -- 0 -- 1[second], |
| 44 |
10 -- { |
| 45 |
8 -- { |
| 46 |
6 -- {5,7}, |
| 47 |
9 |
| 48 |
} } } |
| 49 |
}; |
| 50 |
\end{codeexample} |
| 51 |
|
| 52 |
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing,quotes} |
| 53 |
\usegdlibrary{force}}] |
| 54 |
\tikz \graph [spring layout, |
| 55 |
edge quotes mid, |
| 56 |
edges={nodes={font=\scriptsize, fill=white, sloped, inner sep=1pt}}] |
| 57 |
{ |
| 58 |
1 ->["Das"] 2 ->["ist"] 3 ->["das"] 4 ->["Haus"] |
| 59 |
2 ->["vom" near start] 5 ->["Ni"] 4 ->["ko" near start] |
| 60 |
1 ->["laus", orient=right] 5; |
| 61 |
}; |
| 62 |
\end{codeexample} |
| 63 |
|
| 64 |
Naturally, graph drawing is a bit of a (black?) art. There is no ``perfect'' |
| 65 |
way of drawing a graph, rather, depending on the circumstances there are |
| 66 |
several different ways of drawing the same graph and often it will just depend |
| 67 |
on the aesthetic sense of the reader which layout he or she would prefer. For |
| 68 |
this reason, there are a huge number of graph drawing algorithms ``out there'' |
| 69 |
and there are scientific conference devoted to such algorithms, where each year |
| 70 |
dozens of new algorithms are proposed. |
| 71 |
|
| 72 |
Unlike the rest of \pgfname\ and \tikzname, which is implemented purely in |
| 73 |
\TeX, the graph drawing algorithms are simply too complex to be implemented |
| 74 |
directly in \TeX. Instead, the programming language Lua is used by the |
| 75 |
|graphdrawing| library -- a programming language that has been integrated into |
| 76 |
recent versions of \TeX. This means that (a) as a user of the graph drawing |
| 77 |
engine you run \TeX\ on your documents in the usual way, no external programs |
| 78 |
are called since Lua is already integrated into \TeX, and (b) it is pretty easy |
| 79 |
to implement new graph drawing algorithms for \tikzname\ since Lua can be used |
| 80 |
and no \TeX\ programming knowledge is needed. |
| 81 |
|
| 82 |
|
| 83 |
\subsection{Using the Graph Drawing System} |
| 84 |
|
| 85 |
``Users'' of the graph drawing engine can invoke the graph drawing algorithms |
| 86 |
often by just adding a single option to their picture. Here is a typical |
| 87 |
example, where the |layered layout| option tells \tikzname\ that the graph |
| 88 |
should be drawn (``should be laid out'') using a so-called ``layered graph |
| 89 |
drawing algorithm'' (what these are will be explained later): |
| 90 |
% |
| 91 |
\begin{codeexample}[preamble={\usetikzlibrary{arrows.meta,graphs,graphdrawing} |
| 92 |
\usegdlibrary{layered}}] |
| 93 |
\tikz [>={Stealth[round,sep]}] |
| 94 |
\graph [layered layout, components go right top aligned, nodes=draw, edges=rounded corners] |
| 95 |
{ |
| 96 |
first root -> {1 -> {2, 3, 7} -> {4, 5}, 6 }, 4 -- 5; |
| 97 |
second root -> x -> {a -> {u,v}, b, c -> d -> {w,z} }; |
| 98 |
third root -> child -> grandchild -> youngster -> third root; |
| 99 |
}; |
| 100 |
\end{codeexample} |
| 101 |
% |
| 102 |
Here is another example, where a different layout method is used that is more |
| 103 |
appropriate for trees: |
| 104 |
% |
| 105 |
\begin{codeexample}[preamble={\usetikzlibrary{graphdrawing} |
| 106 |
\usegdlibrary{trees}}] |
| 107 |
\tikz [grow'=up, binary tree layout, nodes={circle,draw}] |
| 108 |
\node {1} |
| 109 |
child { node {2} |
| 110 |
child { node {3} } |
| 111 |
child { node {4} |
| 112 |
child { node {5} } |
| 113 |
child { node {6} } |
| 114 |
} |
| 115 |
} |
| 116 |
child { node {7} |
| 117 |
child { node {8} |
| 118 |
child[missing] |
| 119 |
child { node {9} } |
| 120 |
} |
| 121 |
}; |
| 122 |
\end{codeexample} |
| 123 |
% |
| 124 |
A final example, this time using a ``spring electrical layout'' (whatever that |
| 125 |
might be\dots): |
| 126 |
% |
| 127 |
\begin{codeexample}[ |
| 128 |
preamble={\usetikzlibrary{decorations.pathmorphing,graphdrawing} |
| 129 |
\usegdlibrary{force}}] |
| 130 |
\tikz [spring electrical layout, node distance=1.3cm, |
| 131 |
every edge/.style={ |
| 132 |
decoration={coil, aspect=-.5, post length=1mm, |
| 133 |
segment length=1mm, pre length=2mm}, |
| 134 |
decorate, draw}] |
| 135 |
{ |
| 136 |
\foreach \i in {1,...,6} |
| 137 |
\node (node \i) [fill=blue!50, text=white, circle] {\i}; |
| 138 |
|
| 139 |
\draw (node 1) edge (node 2) |
| 140 |
(node 2) edge (node 3) |
| 141 |
edge (node 4) |
| 142 |
(node 3) edge (node 4) |
| 143 |
edge (node 5) |
| 144 |
edge (node 6); |
| 145 |
} |
| 146 |
\end{codeexample} |
| 147 |
% |
| 148 |
In all of the example, the positions of the nodes have only been computed |
| 149 |
\emph{after} all nodes have been created and the edges have been specified. For |
| 150 |
instance, in the last example, without the option |spring electrical layout|, |
| 151 |
all of the nodes would have been placed on top of each other. |
| 152 |
|
| 153 |
|
| 154 |
\subsection{Extending the Graph Drawing System} |
| 155 |
|
| 156 |
The graph drawing engine is also intended to make is (relatively) easy to |
| 157 |
implement new graph drawing algorithms. These algorithms can either be |
| 158 |
implemented in the Lua programming language (which is \emph{much} easier to |
| 159 |
program than \TeX\ itself) or in C/C++ (but at a great cost regarding |
| 160 |
portability). The Lua code for a graph drawing algorithm gets an |
| 161 |
object-oriented model of the input graph as an input and must just compute the |
| 162 |
desired new positions of the nodes. The complete handling of passing options |
| 163 |
and configurations back-and-forth between the different \tikzname\ and |
| 164 |
\pgfname\ layers is handled by the graph drawing engine. |
| 165 |
|
| 166 |
As a caveat, the graph drawing engine comes with a library of functions and |
| 167 |
methods that simplify the writing of new graph drawing algorithms. As a typical |
| 168 |
example, when you implement a graph drawing algorithm for trees, you typically |
| 169 |
require that your input is a tree; but you can bet that users will feed all |
| 170 |
sorts of graphs to your algorithm, including disjoint unions of cliques. The |
| 171 |
graph drawing engine offers you to say that a precondition to running your |
| 172 |
algorithm is that the graph is a |tree| and instead of the original graph your |
| 173 |
algorithm will be provided with a spanning tree of the graph on which it can |
| 174 |
work. There are numerous further automatic pre- and postprocessing steps that |
| 175 |
include orienting, anchoring, and packing of components, to name a few. |
| 176 |
|
| 177 |
The bottom line is that the graph drawing engine makes it easy |
| 178 |
to try out new graph drawing algorithms for medium sized graphs (up |
| 179 |
to a few hundred nodes) in Lua. For larger graphs, C/C++ code must be |
| 180 |
used. |
| 181 |
|
| 182 |
|
| 183 |
\subsection{The Layers of the Graph Drawing System} |
| 184 |
\label{section-gd-layers} |
| 185 |
|
| 186 |
Even though the graph drawing system presented in the following sections was |
| 187 |
developed as part of \pgfname, it can be used independently of \pgfname\ and |
| 188 |
\tikzname: It was (re)designed so that it can be used by arbitrary programs as |
| 189 |
long as they are able to run Lua. To achieve this, the graph drawing system |
| 190 |
consists of three layers: |
| 191 |
% |
| 192 |
\begin{enumerate} |
| 193 |
\item At the ``bottom'' we have the \emph{algorithmic layer}. This layer, |
| 194 |
written in Lua, contains all graph drawing algorithms. Interestingly, |
| 195 |
options must also be declared on this layer, so an algorithm together |
| 196 |
with all options it uses can and must be specified entirely on this |
| 197 |
layer. If you intend to implement a new graph drawing algorithm, you |
| 198 |
will only be interested in the functionality of this layer. |
| 199 |
|
| 200 |
Algorithm ``communicate'' with the graph drawing system through a |
| 201 |
well-defined interface, encapsulated in the class |
| 202 |
|InterfaceToAlgorithms|. |
| 203 |
\item At the ``top'' we have the \emph{display layer}. This layer is not |
| 204 |
actually part of the graph drawing system. Rather, it is a piece of |
| 205 |
software that ``displays'' graphs and \tikzname\ is just one example of |
| 206 |
such a software. Another example might be a graph editor that uses the |
| 207 |
graph drawing system to lay out the graph it displays. Yet another |
| 208 |
example might be a command line tool for drawing graphs described in a |
| 209 |
file. Finally, you may also wish to use the graph drawing system as a |
| 210 |
simple subroutine for rendering graphs produced in a larger program. |
| 211 |
|
| 212 |
Since the different possible instantiations of the display layer are |
| 213 |
quite heterogeneous, all display layers must communicate with the graph |
| 214 |
drawing system through a special interface, encapsulated in the class |
| 215 |
|InterfaceToDisplay|. |
| 216 |
|
| 217 |
The main job of this class is to provide a set of methods for |
| 218 |
specifying that a graph has certain nodes and edges and that certain |
| 219 |
options have been set for them. However, this interface also allows you |
| 220 |
to query all options that have been declared by algorithms, including |
| 221 |
their documentation. This way, an editor or a command line tool can |
| 222 |
display a list of all graph drawing algorithms and how they can be |
| 223 |
configured. |
| 224 |
\item The algorithm layer and the display layer are ``bound together'' |
| 225 |
through the \emph{binding layer}. Most of the bookkeeping concerning |
| 226 |
the to-be-drawn graphs is done by the graph drawing system |
| 227 |
independently of which algorithm is used and also independently of |
| 228 |
which display layer is used, but some things are still specific to each |
| 229 |
display layer. For instance, some algorithms may create new nodes and |
| 230 |
the algorithms may then need to know how large these nodes will be. For |
| 231 |
this, the display layer must be ``queried'' during a run of the |
| 232 |
algorithm -- and it is the job of the binding layer to achieve this |
| 233 |
callback. |
| 234 |
|
| 235 |
As a rule, the binding layer implements the ``backward'' communication |
| 236 |
from the graph drawing system back to the display layer, while the |
| 237 |
display layer's interface class provides only functions that are called |
| 238 |
from the display layer but which will not ``talk back''. |
| 239 |
\end{enumerate} |
| 240 |
|
| 241 |
All of the files concerned with graph drawing reside in the |graphdrawing| |
| 242 |
subdirectory of |generic/pgf|. |
| 243 |
|
| 244 |
|
| 245 |
\subsection{Organisation of the Graph Drawing Documentation} |
| 246 |
|
| 247 |
The documentation of the graph drawing engine is structured as follows: |
| 248 |
% |
| 249 |
\begin{enumerate} |
| 250 |
\item Following this overview section, the next section documents the graph |
| 251 |
drawing engine from ``the \tikzname\ user's point of view''. No |
| 252 |
knowledge of Lua or algorithmic graph drawing is needed for this |
| 253 |
section, everyone who intends to use algorithmic graph drawing in |
| 254 |
\tikzname\ may be interested in reading it. |
| 255 |
\item You will normally only use \tikzname's keys and commands in order to |
| 256 |
use the graph drawing system, but, internally, these keys call more |
| 257 |
basic \pgfname\ commands that do the ``hard work'' of binding the world |
| 258 |
of \TeX\ boxes and macros to the object-oriented world of Lua. |
| 259 |
Section~\ref{section-gd-pgf} explains how this works and which commands |
| 260 |
are available for authors of packages that directly need to use the |
| 261 |
graph drawing system inside \pgfname, avoiding the overhead incurred by |
| 262 |
\tikzname. |
| 263 |
|
| 264 |
Most readers can safely skip this section. |
| 265 |
\item The next sections detail which graph drawing algorithms are currently |
| 266 |
implemented as part of the \tikzname\ distribution, see |
| 267 |
Sections~\ref{section-first-graphdrawing-library-in-manual} |
| 268 |
to~\ref{section-last-graphdrawing-library-in-manual}. |
| 269 |
\item Section~\ref{section-gd-algorithm-layer} is addressed at readers who |
| 270 |
wish to implement their own graph drawing algorithms. For this, |
| 271 |
\emph{no knowledge at all} of \TeX\ programming is needed. The section |
| 272 |
explains the graph model used in Lua, the available libraries, the |
| 273 |
graph drawing pipeline, and everything else that is part of the Lua |
| 274 |
side of the engine. |
| 275 |
\item Section~\ref{section-gd-display-layer} details the display layer of |
| 276 |
the graph drawing system. You should read this section if you wish to |
| 277 |
implement a new display system (that is, a non-\TeX-based program) that |
| 278 |
intends to use the graph drawing system. |
| 279 |
\item Section~\ref{section-gd-binding-layer} explains how binding layers |
| 280 |
can be implemented. This section, too, is of interest only to readers |
| 281 |
who wish to write new display systems. |
| 282 |
\end{enumerate} |
| 283 |
|
| 284 |
|
| 285 |
\subsection{Acknowledgements} |
| 286 |
|
| 287 |
Graph drawing in \tikzname\ began as a student's project under my supervision. |
| 288 |
Ren\'ee Ahrens, Olof-Joachim Frahm, Jens Kluttig, Matthias Schulz, and Stephan |
| 289 |
Schuster wrote the first prototype of a graph drawing system inside \tikzname\ |
| 290 |
that uses Lua\TeX\ for the implementation of graph drawing algorithms. |
| 291 |
|
| 292 |
This first, early version was greatly extended on the algorithmic side by |
| 293 |
Jannis Pohlmann who wrote his Diploma thesis on graph drawing under my |
| 294 |
supervision. He implemented, in particular, the Sugiyama method |
| 295 |
(|layered layout|) and force based algorithms. Also, he rewrote some of the |
| 296 |
code of the prototype. |
| 297 |
|
| 298 |
At some point it became apparent that the first implementation had a number of |
| 299 |
deficiencies, both concerning the structure, the interfaces, and (in |
| 300 |
particular) the performance. Because of this, I rewrote the code of the graph |
| 301 |
drawing system, both on the \TeX\ side and on the Lua side in its current form. |
| 302 |
However, I would like to stress that without the work of the people mentioned |
| 303 |
above graph drawing in \tikzname\ would not exist. |
| 304 |
|
| 305 |
The documentation was written almost entirely by myself, though I did copy some |
| 306 |
paragraphs from Jannis's Diploma thesis, which I can highly recommend everyone |
| 307 |
to read. |
| 308 |
|
| 309 |
In the future, I hope that other people will contribute algorithms, which will |
| 310 |
be available as libraries. |