Debian Codegraph @

texmf-dist/doc/generic/pgf/pgfmanual-en-gd-overview.tex

raw
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.