| 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{The Algorithm Layer} |
| 14 |
\label{section-gd-algorithm-layer} |
| 15 |
|
| 16 |
\noindent{\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{Overview} |
| 26 |
|
| 27 |
The present section is addressed at readers interested in implementing new |
| 28 |
graph drawing algorithms for the graph drawing system. Obviously, in order to |
| 29 |
do so, you need to have an algorithm in mind and also some programming skills; |
| 30 |
but fortunately only in the Lua programming language: Even though the graph |
| 31 |
drawing system was originally developed as an extension of \tikzname, is has |
| 32 |
been restructured so that the ``algorithm layer'' where you define algorithms |
| 33 |
is scrupulously separated from \tikzname. In particular, an algorithm declared |
| 34 |
and implemented on this layer can be used in with every ``display layers'', see |
| 35 |
Section~\ref{section-gd-display-layer}, without change. Nevertheless, in the |
| 36 |
following we will use the \tikzname\ display layer and syntax in our examples. |
| 37 |
|
| 38 |
Normally, new graph drawing algorithms can and must be implemented in the Lua |
| 39 |
programming language, which is a small, easy-to-learn (and quite beautiful) |
| 40 |
language integrated into current versions of \TeX. However, as explained in |
| 41 |
Section~\ref{section-algorithms-in-c}, you can also implement algorithms in C |
| 42 |
or C++ (and, possibly, in the future also in other languages), but this comes |
| 43 |
at a great cost concerning portability. In the present section, I assume that |
| 44 |
you are only interested in writing an algorithm using Lua. |
| 45 |
|
| 46 |
In the following, after a small ``hello world'' example of graph drawing and a |
| 47 |
discussion of technical details like how to name files so that \TeX\ will find |
| 48 |
them, we have a look at the main parts of the algorithm layer: |
| 49 |
% |
| 50 |
\begin{itemize} |
| 51 |
\item Section~\ref{section-gd-namespaces} gives and overview of the |
| 52 |
available namespaces and also of naming conventions used in the graph |
| 53 |
drawing system. |
| 54 |
\item Section~\ref{section-gd-gd-scope} explores what graph drawing scopes |
| 55 |
``look like on the algorithm layer''. As the graph of a graph drawing |
| 56 |
scope is being parsed on the display layer, a lot of information is |
| 57 |
gathered: The nodes and edges of the graph are identified and the |
| 58 |
object-oriented model is built, but other information is also |
| 59 |
collected. For instance, a sequence of \emph{events} is created during |
| 60 |
the parsing process. As another example, numerous kinds of |
| 61 |
\emph{collections} may be identified by the parser. The parsed graph |
| 62 |
together with the event sequence and the collections are all gathered |
| 63 |
in a single table, called the \emph{scope table} of the current graph |
| 64 |
drawing scope. Algorithms can access this table to retrieve information |
| 65 |
that goes beyond the ``pure'' graph model. |
| 66 |
|
| 67 |
One entry in this table is of particular importance: The |
| 68 |
\emph{syntactic digraph.} While most graph drawing algorithms are not |
| 69 |
really interested in the ``details'' of how a graph was specified, for |
| 70 |
some algorithms it makes a big difference whether you write |a -> b| or |
| 71 |
|b <- a| in your specification of the graph. These algorithms can |
| 72 |
access the ``fine details'' of how the input graph was specified |
| 73 |
through the syntactic digraph; all other algorithms can access their |
| 74 |
|digraph| or |ugraph| fields and do not have to worry about the |
| 75 |
difference between |a -> b| and |b <- a|. |
| 76 |
\item Section~\ref{section-gd-models} explains the object-oriented model of |
| 77 |
graphs used throughout the graph drawing system. Graph drawing |
| 78 |
algorithms do not get the ``raw'' specification used by the user to |
| 79 |
specify a graph (like |{a -> {b,c}}| in the |graph| syntax). Instead, |
| 80 |
what a graph drawing algorithm sees is ``just'' a graph object that |
| 81 |
provides methods for accessing the vertices and arcs. |
| 82 |
\item Section~\ref{section-gd-transformations} explains how the information |
| 83 |
in the graph drawing scope is processed. One might expect that we |
| 84 |
simply run the algorithm selected by the user; however, things are more |
| 85 |
involved in practice. When the layout of a graph needs to be computed, |
| 86 |
only very few algorithms will actually be able to compute positions for |
| 87 |
the nodes of \emph{every} graph. For instance, most algorithms |
| 88 |
implicitly assume that the input graph is connected; algorithms for |
| 89 |
computing layouts for trees assume that the input is, well, a tree; and |
| 90 |
so on. For this reason, graph drawing algorithms will not actually need |
| 91 |
the original input graph as their input, but some \emph{transformed} |
| 92 |
version of it. Indeed, \emph{all} graph drawing algorithms are treated |
| 93 |
as graph transformations by the graph drawing engine. |
| 94 |
|
| 95 |
This section explains how transformations are chosen and which |
| 96 |
transformations are applied by default. |
| 97 |
\item Section~\ref{section-gd-interface-to-algorithms} documents the |
| 98 |
interface-to-algorithm class. This interface encapsulates all that an |
| 99 |
algorithm ``sees'' of the graph drawing system (apart from the classes |
| 100 |
in |model| and |lib|). |
| 101 |
\item Section~\ref{section-gd-examples} provides a number of complete |
| 102 |
examples that show how graph drawing algorithms can, actually, be |
| 103 |
implemented. |
| 104 |
\item Section~\ref{section-gd-libs} documents the different libraries |
| 105 |
functions that come with the graph drawing engine. For instance, there |
| 106 |
are library functions for computing the (path) distance of nodes in a |
| 107 |
graph; a parameter that is needed by some algorithms. |
| 108 |
\end{itemize} |
| 109 |
|
| 110 |
|
| 111 |
\subsection{Getting Started} |
| 112 |
|
| 113 |
In this section, a ``hello world'' example of a graph drawing algorithm is |
| 114 |
given, followed by an overview of the organization of the whole engine. |
| 115 |
|
| 116 |
|
| 117 |
\subsubsection{The Hello World of Graph Drawing} |
| 118 |
|
| 119 |
Let us start our tour of the algorithm layer with a ``hello world'' version of |
| 120 |
graph drawing: An algorithm that simply places all nodes of a graph in a circle |
| 121 |
of a fixed radius. Naturally, this is not a particularly impressive or |
| 122 |
intelligent graph drawing algorithm; but neither is the classical ``hello |
| 123 |
world''$\dots$\ Here is a minimal version of the needed code (this is not the |
| 124 |
typical way of formulating the code, but it is the shortest; we will have a |
| 125 |
look at the more standard and verbose way in a moment): |
| 126 |
% |
| 127 |
\begin{codeexample}[code only, tikz syntax=false] |
| 128 |
pgf.gd.interface.InterfaceToAlgorithms.declare { |
| 129 |
key = "very simple demo layout", |
| 130 |
algorithm = { |
| 131 |
run = |
| 132 |
function (self) |
| 133 |
local alpha = (2 * math.pi) / #self.ugraph.vertices |
| 134 |
for i,vertex in ipairs(self.ugraph.vertices) do |
| 135 |
vertex.pos.x = math.cos(i * alpha) * 25 |
| 136 |
vertex.pos.y = math.sin(i * alpha) * 25 |
| 137 |
end |
| 138 |
end |
| 139 |
} |
| 140 |
} |
| 141 |
\end{codeexample} |
| 142 |
\directlua{ |
| 143 |
pgf.gd.interface.InterfaceToAlgorithms.declare { |
| 144 |
key = "very simple demo layout", |
| 145 |
algorithm = { |
| 146 |
run = |
| 147 |
function (self) |
| 148 |
local alpha = (2 * math.pi) / \luaescapestring{#}self.ugraph.vertices |
| 149 |
for i,vertex in ipairs(self.ugraph.vertices) do |
| 150 |
vertex.pos.x = math.cos(i * alpha) * 25 |
| 151 |
vertex.pos.y = math.sin(i * alpha) * 25 |
| 152 |
end |
| 153 |
end |
| 154 |
} |
| 155 |
} |
| 156 |
} |
| 157 |
|
| 158 |
This code \emph {declares} a new algorithm (|very simple demo layout|) and |
| 159 |
includes an implementation of the algorithm (through the |run| field of the |
| 160 |
|algorithm| field). When the |run| method is called, the |self| parameter will |
| 161 |
contain the to-be-drawn graph in its |ugraph| field. It is now the job of the |
| 162 |
code to modify the positions of the vertices in this graph (in the example, |
| 163 |
this is done by assigning values to |vertex.pos.x| and |vertex.pos.y|). |
| 164 |
|
| 165 |
In order to actually \emph{use} the algorithm, the above code first needs to be |
| 166 |
executed somehow. For \tikzname, one can just call |\directlua| on it or put it |
| 167 |
in a file and then use |\directlua| plus |require| (a better alternative) or |
| 168 |
you put it in a file like |simpledemo.lua| and use |\usegdlibrary{simpledemo}| |
| 169 |
(undoubtedly the ``best'' way). For another display layer, like a graphical |
| 170 |
editor, the code could also be executed through the use of |require|. |
| 171 |
|
| 172 |
Executing the code ``just'' declares the algorithm, this is what the |declare| |
| 173 |
function does. Inside some internal tables, the algorithm layer will store the |
| 174 |
fact that a |very simple demo layout| is now available. The algorithm layer |
| 175 |
will also communicate with the display layer through the binding layer to |
| 176 |
advertise this fact to the ``user''. In the case of \tikzname, this means that |
| 177 |
the option key |very simple demo layout| becomes available at this point and we |
| 178 |
can use it like this: |
| 179 |
% |
| 180 |
\begin{codeexample}[] |
| 181 |
\tikz [very simple demo layout] |
| 182 |
\graph { f -> c -> e -> a -> {b -> {c, d, f}, e -> b}}; |
| 183 |
\end{codeexample} |
| 184 |
|
| 185 |
It turns out, that our little algorithm is already more powerful than one might |
| 186 |
expect. Consider the following example: |
| 187 |
% |
| 188 |
\begin{codeexample}[] |
| 189 |
\tikz [very simple demo layout, componentwise] |
| 190 |
\graph { |
| 191 |
1 -> 2 ->[orient=right] 3 -> 1; |
| 192 |
a -- b --[orient=45] c -- d -- a; |
| 193 |
}; |
| 194 |
\end{codeexample} |
| 195 |
|
| 196 |
Note that, in our algorithm, we ``just'' put all nodes on a circle around the |
| 197 |
origin. Nevertheless, the graph gets decomposed into two connected components, |
| 198 |
the components are rotated so that the edge from node |2| to node |3| goes from |
| 199 |
left to right and the edge from |b| to |c| goes up at an angle of $45^\circ$, |
| 200 |
and the components are placed next to each other so that some spacing is |
| 201 |
achieved. |
| 202 |
|
| 203 |
The ``magic'' that achieves all this behind the scenes is called ``graph |
| 204 |
transformations''. They will heavily pre- and postprocess the input and output |
| 205 |
of graph drawing algorithms to achieve the above results. |
| 206 |
|
| 207 |
Naturally, some algorithms may not wish their inputs and/or outputs to be |
| 208 |
``tampered'' with. An algorithm can easily configure which transformations |
| 209 |
should be applied, by passing appropriate options to |declare|. |
| 210 |
|
| 211 |
|
| 212 |
\subsubsection{Declaring an Algorithm} |
| 213 |
|
| 214 |
Let us now have a look at how one would ``really'' implement the example |
| 215 |
algorithm. First of all, we place our algorithm in a separate file called, say, |
| 216 |
|ExampleLayout.lua|. This way, by putting it in a separate file, all display |
| 217 |
layers can easily install the algorithm at runtime by saying |
| 218 |
|require "ExampleLayout"|. |
| 219 |
|
| 220 |
Next, the |declare| function is needed quite often, so it makes sense to create |
| 221 |
a short local name for it: |
| 222 |
% |
| 223 |
\begin{codeexample}[code only, tikz syntax=false] |
| 224 |
-- This is the file ExampleLayout.lua |
| 225 |
local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare |
| 226 |
\end{codeexample} |
| 227 |
|
| 228 |
The |declare| function is the work-horse of the algorithm layer. It takes a |
| 229 |
table that contains at least a |key| field, which must be a unique string, and |
| 230 |
some other fields that specify in more detail what kind of key is declared. |
| 231 |
Once declared through a call of |declare|, the ``key'' can be used on the |
| 232 |
display layer. |
| 233 |
|
| 234 |
For declaring an algorithm, the table passed to |declare| must contain a field |
| 235 |
|algorithm|. This field, in turn, must (normally) be set to a table that will |
| 236 |
become the algorithm class. In the above example, our algorithm was so simple |
| 237 |
that we could place the whole definition of the class inside the call of |
| 238 |
|declare|, but normally the class is defined in more detail after the call to |
| 239 |
|declare|: |
| 240 |
% |
| 241 |
\begin{codeexample}[code only, tikz syntax=false] |
| 242 |
local ExampleClass = {} -- A local variable holding the class table |
| 243 |
|
| 244 |
declare { |
| 245 |
key = "very simple demo layout", |
| 246 |
algorithm = ExampleClass |
| 247 |
} |
| 248 |
|
| 249 |
function ExampleClass:run () |
| 250 |
local alpha = (2 * math.pi) / #self.ugraph.vertices |
| 251 |
... |
| 252 |
end |
| 253 |
\end{codeexample} |
| 254 |
|
| 255 |
The effect of the |declare| will be that the table stored in |ExampleClass| is |
| 256 |
setup to form a class in the sense of object-oriented programming. In |
| 257 |
particular, a static |new| function is installed. |
| 258 |
|
| 259 |
Now, whenever the user uses the key |very simple demo layout| on a graph, at |
| 260 |
some point the graph drawing engine will create a new instance of the |
| 261 |
|ExampleClass| using |new| and will then call the |run| method of this class. |
| 262 |
The class can have any number of other methods, but |new| and |run| are the |
| 263 |
only ones directly called by the graph drawing system. |
| 264 |
|
| 265 |
|
| 266 |
\subsubsection{The Run Method} |
| 267 |
|
| 268 |
The |run| method of an algorithm classes lies at the heart of any graph drawing |
| 269 |
algorithm. This method will be called whenever a graph needs to be laid out. |
| 270 |
Upon this call, the |self| object will have some important fields set: |
| 271 |
% |
| 272 |
\begin{itemize} |
| 273 |
\item |ugraph| This stands for ``undirected graph'' and is the |
| 274 |
``undirected'' version of the to-be-laid out graph. In this graph, |
| 275 |
whenever there is an arc between $u$ and $v$, there is also an arc |
| 276 |
between $v$ and $u$. It is obtained by considering the syntactic |
| 277 |
digraph and then ``forgetting'' about the actual direction of the |
| 278 |
edges. |
| 279 |
|
| 280 |
When you have set certain |preconditions| in your algorithm class, like |
| 281 |
|connected=true|, the |ugraph| will satisfy these conditions. In |
| 282 |
particular, the |ugraph| typically will not be the underlying |
| 283 |
undirected graph of the complete syntactic digraph, but rather of some |
| 284 |
part of it. The use of (sub)layouts will also modify the syntactic |
| 285 |
digraph is fancy ways. |
| 286 |
|
| 287 |
Refer to this graph whenever your algorithm is ``most comfortable'' |
| 288 |
with an undirected graph, as is the case for instance for most |
| 289 |
force-base algorithms. |
| 290 |
\item |digraph| This stands for ``directed graph'' and is the |
| 291 |
``semantically directed'' version of the to-be-laid out graph. |
| 292 |
Basically, when happens is that reverse edges in the syntactic digraph |
| 293 |
(an edge like |b <- a|) will yield an |Arc| from |a| to |b| in the |
| 294 |
|digraph| while they yield a |b| to |a| arc and edge in the syntactic |
| 295 |
digraph. Also, undirected edges like |a -- b| are replaced by directed |
| 296 |
edges in both directions between the vertices. |
| 297 |
\item |scope| The graph drawing scope. |
| 298 |
\item |layout| The layout object for this graph. This is a collection of |
| 299 |
kind |layout|. |
| 300 |
\end{itemize} |
| 301 |
|
| 302 |
|
| 303 |
\subsubsection{Loading Algorithms on Demand} |
| 304 |
|
| 305 |
In order to use the |very simple demo layout| on the display layer, |declare| |
| 306 |
must have been called for this key. However, we just saw that the |declare| |
| 307 |
function takes the actual class table as parameter and, thus, whenever an |
| 308 |
algorithm is declared, it is also completely loaded and compiled at this point. |
| 309 |
|
| 310 |
This is not always desirable. A user may wish to include a number of libraries |
| 311 |
in order to declare a large number of potentially useful algorithms, but will |
| 312 |
not actually use all of them. Indeed, at least for large, complex algorithms, |
| 313 |
it is preferable that the algorithm's code is loaded only when the algorithm is |
| 314 |
used for the first time. |
| 315 |
|
| 316 |
Such a ``loading of algorithms on demand'' is supported through the option of |
| 317 |
setting the |algorithm| field in a |declare| to a string. This string must now |
| 318 |
be the file name of a Lua file that contains the code of the actual algorithm. |
| 319 |
When the key is actually used for the first time, this file will be loaded. It |
| 320 |
must return a table that will be plugged into the |algorithm| field; so |
| 321 |
subsequent usages of the key will not load the file again. |
| 322 |
|
| 323 |
The net effect of all this is that you can place implementations of algorithms |
| 324 |
in files separate from interface files that just contain the |declare| commands |
| 325 |
for these algorithms. You will typically do this only for rather large |
| 326 |
algorithms. |
| 327 |
|
| 328 |
For our example, the code would look like this: |
| 329 |
% |
| 330 |
\begin{codeexample}[code only, tikz syntax=false] |
| 331 |
-- File ExampleLayout.lua |
| 332 |
local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare |
| 333 |
declare { |
| 334 |
key = "very simple demo layout", |
| 335 |
algorithm = "ExampleLayoutImplementation" |
| 336 |
} |
| 337 |
\end{codeexample} |
| 338 |
|
| 339 |
\begin{codeexample}[code only, tikz syntax=false] |
| 340 |
-- File ExampleLayoutImplementation.lua |
| 341 |
local ExampleClass = {} |
| 342 |
function ExampleClass:run () |
| 343 |
local alpha = (2 * math.pi) / #self.ugraph.vertices |
| 344 |
... |
| 345 |
end |
| 346 |
return ExampleClass |
| 347 |
\end{codeexample} |
| 348 |
|
| 349 |
|
| 350 |
\subsubsection{Declaring Options} |
| 351 |
|
| 352 |
Let us now make our example algorithm a bit more ``configurable''. For this, we |
| 353 |
use |declare| once more, but instead of the |algorithm| field, we use a |type| |
| 354 |
field. This tells the display layer that the key is not used to select an |
| 355 |
algorithm, but to configure ``something'' about the graph or about nodes or |
| 356 |
edges. |
| 357 |
|
| 358 |
In our example, we may wish to configure the radius of the graph. So, we |
| 359 |
introduce a |radius| key (actually, this key already exists, so we would not |
| 360 |
need to declare it, but let us do so anyway for example purposes): |
| 361 |
% |
| 362 |
\begin{codeexample}[code only, tikz syntax=false] |
| 363 |
declare { |
| 364 |
key = "radius", |
| 365 |
type = "length", |
| 366 |
initial = "25pt" |
| 367 |
} |
| 368 |
\end{codeexample} |
| 369 |
|
| 370 |
This tells the display layer that there is now an option called |radius|, that |
| 371 |
users set it to some ``length'', and that if it is not set at all, then the |
| 372 |
25pt should be used. |
| 373 |
|
| 374 |
To access what the user has specified for this key, an algorithm can access the |
| 375 |
|options| field of a graph, vertex, or arc at the key's name: |
| 376 |
% |
| 377 |
\begin{codeexample}[code only, tikz syntax=false] |
| 378 |
vertex.pos.x = math.cos(i * alpha) * vertex.options.radius |
| 379 |
vertex.pos.y = math.sin(i * alpha) * vertex.options.radius |
| 380 |
\end{codeexample} |
| 381 |
|
| 382 |
|
| 383 |
\subsubsection{Adding Inline Documentation} |
| 384 |
|
| 385 |
You should always document the keys you |declare|. For this, the |declare| |
| 386 |
function allows you to add three fields to its argument table: |
| 387 |
% |
| 388 |
\begin{itemize} |
| 389 |
\item |summary| This should be a string that succinctly summarizes the |
| 390 |
effect this key has. The idea is that this text will be shown as a |
| 391 |
``tooltip'' in a graphical editor or will be printed out by a command |
| 392 |
line tool when a user requests help about the key. You can profit from |
| 393 |
using Lua's |[[| and |]]| syntax for specifying multi-line strings. |
| 394 |
|
| 395 |
Also, when the file containing the key is parsed for this manual, this |
| 396 |
text will be shown. |
| 397 |
\item |documentation| When present, this field contains a more extensive |
| 398 |
documentation of the key. It will also be shown in this manual, but |
| 399 |
typically not as a tool tip. |
| 400 |
\item |examples| This should either be a single string or an array of |
| 401 |
strings. Each string should be an example demonstrating how the key is |
| 402 |
used in \tikzname. They will all be included in the manual, each |
| 403 |
surrounded by a |codeexample| environment. |
| 404 |
\end{itemize} |
| 405 |
|
| 406 |
Let us augment our |radius| key with some documentation. The three dashes |
| 407 |
before the |declare| are only needed when the declaration is part of this |
| 408 |
manual and they will trigger an inclusion of the key in the manual. |
| 409 |
% |
| 410 |
\begin{codeexample}[code only, tikz syntax=false] |
| 411 |
--- |
| 412 |
declare { |
| 413 |
key = "radius", |
| 414 |
type = "length", |
| 415 |
initial = "25pt", |
| 416 |
summary = [[ |
| 417 |
Specifies the radius of a circle on which the nodes are placed when |
| 418 |
the |very simple example layout| is used. Each vertex can have a |
| 419 |
different radius. |
| 420 |
]], |
| 421 |
examples = [[ |
| 422 |
\tikz \graph [very simple example layout, radius=2cm] { |
| 423 |
a -- b -- c -- d -- e; |
| 424 |
}; |
| 425 |
]] |
| 426 |
} |
| 427 |
\end{codeexample} |
| 428 |
|
| 429 |
As a courtesy, all of the strings given in the documentation can start and end |
| 430 |
with quotation marks, which will be removed. (This helps syntax highlighting |
| 431 |
with editors that do not recognize the |[[| to |]]| syntax.) Also, the |
| 432 |
indentation of the strings is removed (we compute the minimum number of leading |
| 433 |
spaces on any line and remove this many spaces from all lines). |
| 434 |
|
| 435 |
|
| 436 |
\subsubsection{Adding External Documentation} |
| 437 |
\label{section-gd-documentation-in} |
| 438 |
|
| 439 |
As an alternative to inlining documentation, you can also store the |
| 440 |
documentation of keys in a separate file that is loaded only when the |
| 441 |
documentation is actually accessed. Since this happens only rarely (for |
| 442 |
instance, not at all, when \tikzname\ is run, except for this manual), this |
| 443 |
will save time and space. Also, for C code, it is impractical to store |
| 444 |
multi-line documentation strings directly in the C file. |
| 445 |
|
| 446 |
In order to store documentation externally, instead of the |summary|, |
| 447 |
|documentation|, and |examples| keys, you provide the key |documentation_in|. |
| 448 |
The |documentation_in| key must be set to a string that is input using |
| 449 |
|require|. |
| 450 |
|
| 451 |
In detail, when someone tries to access the |summary|, |documentation|, or |
| 452 |
|examples| field of a key and these keys are not (yet) defined, the system |
| 453 |
checks whether the |documentation_in| key is set. If so, we apply |require| to |
| 454 |
the string stored in this field. The file loaded in this way can now setup the |
| 455 |
missing fields of the current key and, typically, also of all other keys |
| 456 |
defined in the same file as the current key. For this purpose, it is advisable |
| 457 |
to use the |pgf.gd.doc| class: |
| 458 |
|
| 459 |
\includeluadocumentationof{pgf.gd.doc} |
| 460 |
|
| 461 |
As a longer example, consider the following declarations: |
| 462 |
% |
| 463 |
\begin{codeexample}[code only, tikz syntax=false] |
| 464 |
--- |
| 465 |
declare { |
| 466 |
key = "very simple demo layout", |
| 467 |
algorithm = ExampleClass, |
| 468 |
documentation_in = "documentation_file" |
| 469 |
} |
| 470 |
|
| 471 |
--- |
| 472 |
declare { |
| 473 |
key = "radius", |
| 474 |
type = "length", |
| 475 |
initial = "25", |
| 476 |
documentation_in = "documentation_file" |
| 477 |
} |
| 478 |
\end{codeexample} |
| 479 |
|
| 480 |
The file |documentation_file.lua| would look like this: |
| 481 |
% |
| 482 |
\begin{codeexample}[code only, tikz syntax=false] |
| 483 |
-- File documentation_file.lua |
| 484 |
local key = require 'pgf.gd.doc'.key |
| 485 |
local documentation = require 'pgf.gd.doc'.documentation |
| 486 |
local summary = require 'pgf.gd.doc'.summary |
| 487 |
local example = require 'pgf.gd.doc'.example |
| 488 |
|
| 489 |
key "very simple demo layout" |
| 490 |
documentation "This layout is a very simple layout that, ..." |
| 491 |
|
| 492 |
key "radius" |
| 493 |
summary "Specifies the radius of a circle on which the nodes are placed." |
| 494 |
documentation |
| 495 |
[[ |
| 496 |
This key can be used together with |very simple example layout|. An |
| 497 |
important feature is that... |
| 498 |
]] |
| 499 |
example |
| 500 |
[[ |
| 501 |
\tikz \graph [very simple example layout, radius=2cm] |
| 502 |
{ a -- b -- c -- d -- e; }; |
| 503 |
]] |
| 504 |
\end{codeexample} |
| 505 |
|
| 506 |
|
| 507 |
\subsection{Namespaces and File Names} |
| 508 |
\label{section-gd-namespaces} |
| 509 |
|
| 510 |
\subsubsection{Namespaces} |
| 511 |
|
| 512 |
All parts of the |graphdrawing| library reside in the Lua ``namespace'' |
| 513 |
|pgf.gd|, which is itself a ``sub-namespace'' of |pgf|. For your own |
| 514 |
algorithms, you are free to place them in whatever namespace you like; only for |
| 515 |
the official distribution of \pgfname\ everything has been put into the correct |
| 516 |
namespace. |
| 517 |
|
| 518 |
Let us now have a more detailed look at these namespaces. A namespace is just a |
| 519 |
Lua table, and sub-namespaces are just subtables of namespace tables. Following |
| 520 |
the Java convention, namespaces are in lowercase letters. The following |
| 521 |
namespaces are part of the core of the graph drawing engine: |
| 522 |
% |
| 523 |
\begin{itemize} |
| 524 |
\item |pgf| This namespace is the main namespace of \pgfname. Other parts |
| 525 |
of \pgfname\ and \tikzname\ that also employ Lua should put an entry |
| 526 |
into this table. Since, currently, only the graph drawing engine |
| 527 |
adheres to this rule, this namespace is declared inside the graph |
| 528 |
drawing directory, but this will change. |
| 529 |
|
| 530 |
The |pgf| table is the \emph{only} entry into the global table of Lua |
| 531 |
generated by the graph drawing engine (or, \pgfname, for that matter). |
| 532 |
If you intend to extend the graph drawing engine, do not even |
| 533 |
\emph{think} of polluting the global namespace. You will be fined. |
| 534 |
\item |pgf.gd| This namespace is the main namespace of the graph drawing |
| 535 |
engine, including the object-oriented models of graphs and the layout |
| 536 |
pipeline. Algorithms that are part of the distribution are also inside |
| 537 |
this namespace, but if you write your own algorithms you do not need |
| 538 |
place them inside this namespace. (Indeed, you probably should not |
| 539 |
before they are made part of the official distribution.) |
| 540 |
\item |pgf.gd.interface| This namespace handles, on the one hand, the |
| 541 |
communication between the algorithm layer and the binding layer and, on |
| 542 |
the other hand, the communication between the display layer (\tikzname) |
| 543 |
and the binding layer. |
| 544 |
\item |pgf.gd.binding| So-called ``bindings'' between display layers and |
| 545 |
the graph drawing system reside in this namespace. |
| 546 |
\item |pgf.gd.lib| Numerous useful classes that ``make an algorithm's your |
| 547 |
life easier'' are collected in this namespace. Examples are a class for |
| 548 |
decomposing a graph into connected components or a class for computing |
| 549 |
the ideal distance between two sibling nodes in a tree, taking all |
| 550 |
sorts of rotations and separation parameters into account. |
| 551 |
\item |pgf.gd.model| This namespace contains all Lua classes that are part |
| 552 |
of the object-oriented model of graphs employed throughout the graph |
| 553 |
drawing engine. For readers familiar with the model--view--controller |
| 554 |
pattern: This is the namespace containing the model-part of this |
| 555 |
pattern. |
| 556 |
\item |pgf.gd.control| This namespace contains the ``control logic'' of the |
| 557 |
graph drawing system. It will transform graphs according to rules, |
| 558 |
disassemble layouts and sublayouts and will call the appropriate |
| 559 |
algorithms. For readers still familiar with the model--view--controller |
| 560 |
pattern: This is the namespace containing the control-part of this |
| 561 |
pattern. |
| 562 |
\item |pgf.gd.trees| This namespace contains classes that are useful for |
| 563 |
dealing with graphs that are trees. In particular, it contains a class |
| 564 |
for computing a spanning tree of an arbitrary connected graph; an |
| 565 |
operation that is an important preprocessing step for many algorithms. |
| 566 |
|
| 567 |
In addition to providing ``utility functions for trees'', the namespace |
| 568 |
\emph{also} includes actual algorithms for computing graph layouts like |
| 569 |
|pgf.gd.trees.ReingoldTilford1981|. It may seem to be a bit of an |
| 570 |
``impurity'' that a namespace mixes utility classes and ``real'' |
| 571 |
algorithms, but experience has shown that it is better to keep things |
| 572 |
together in this way. |
| 573 |
|
| 574 |
Concluding the analogy to the model--view--controller pattern, a graph |
| 575 |
drawing algorithm is, in a loose sense, the ``view'' part of the |
| 576 |
pattern. |
| 577 |
\item |pgf.gd.layered| This namespace provides classes and functions for |
| 578 |
``layered'' layouts; the Sugiyama layout method being the most |
| 579 |
well-known one. Again, the namespace contains both algorithms to be |
| 580 |
used by a user and utility functions. |
| 581 |
\item |pgf.gd.force| Collects force-based algorithms and, again, also |
| 582 |
utility functions and classes. |
| 583 |
\item |pgf.gd.examples| Contains some example algorithms. They are |
| 584 |
\emph{not} intended to be used directly, rather they should serve as |
| 585 |
inspirations for readers wishing to implement their own algorithms. |
| 586 |
\end{itemize} |
| 587 |
|
| 588 |
There are further namespaces that also reside in the |pgf.gd| namespace, these |
| 589 |
namespaces are used to organize different graph drawing algorithms into |
| 590 |
categories. |
| 591 |
|
| 592 |
In Lua, similarly to Java, when a class |SomeClass| is part of, say, the |
| 593 |
namespace |pgf.gd.example|, it is customary to put the class's code in a file |
| 594 |
|SomeClass.lua| and then put this class in a directory |example|, that is a |
| 595 |
subdirectory of a directory |gd|, which is in turn a subdirectory of a |
| 596 |
directory |pgf|. When you write \texttt{require "pgf.gd.example.SomeClass"} the |
| 597 |
so-called \emph{loader} will turn this into a request for the file |
| 598 |
\texttt{pgf/gd/example/SomeClass.lua} (for Unix systems). |
| 599 |
|
| 600 |
|
| 601 |
\subsubsection{Defining and Using Namespaces and Classes} |
| 602 |
|
| 603 |
There are a number of rules concerning the structure and naming of namespaces |
| 604 |
as well as the naming of files. Let us start with the rules for naming |
| 605 |
namespaces, classes, and functions. They follow the ``Java convention'': |
| 606 |
% |
| 607 |
\begin{enumerate} |
| 608 |
\item A namespace is a short lowercase |word|. |
| 609 |
\item A function in a namespace is in |
| 610 |
|lowercase_with_underscores_between_words|. |
| 611 |
\item A class name is in |CamelCaseWithAnUppercaseFirstLetter|. |
| 612 |
\item A class method name is in |camelCaseWithALowercaseFirstLetter|. |
| 613 |
\end{enumerate} |
| 614 |
|
| 615 |
From Lua's point of view, every namespace and every class is just a table. |
| 616 |
However, since these tables will be loaded using Lua's |require| function, each |
| 617 |
namespace and each class must be placed inside a separate file (unless you |
| 618 |
modify the |package.loaded| table, but, then, you know what you are doing |
| 619 |
anyway). Inside such a file, you should first declare a local variable whose |
| 620 |
name is the name of the namespace or class that you intend to define and then |
| 621 |
assign a (possibly empty) table to this variable: |
| 622 |
% |
| 623 |
\begin{codeexample}[code only, tikz syntax=false] |
| 624 |
-- File pgf.gd.example.SomeClass.lua: |
| 625 |
local SomeClass = {} |
| 626 |
\end{codeexample} |
| 627 |
% |
| 628 |
Next, you should add your class to the encompassing namespace. This is achieved |
| 629 |
as follows: |
| 630 |
% |
| 631 |
\begin{codeexample}[code only, tikz syntax=false] |
| 632 |
require("pgf.gd.example").SomeClass = SomeClass |
| 633 |
\end{codeexample} |
| 634 |
% |
| 635 |
The reason this works is that the |require| will return the table that is the |
| 636 |
namespace |pgf.gd.example|. So, inside this namespace, the |SomeClass| field |
| 637 |
will be filled with the table stored in the local variable of the same name -- |
| 638 |
which happens to be the table representing the class. |
| 639 |
|
| 640 |
At the end of the file, you must write |
| 641 |
% |
| 642 |
\begin{codeexample}[code only, tikz syntax=false] |
| 643 |
return SomeClass |
| 644 |
\end{codeexample} |
| 645 |
% |
| 646 |
This ensures that the table that is defined in this file gets stored by Lua in |
| 647 |
the right places. Note that you need and should not use Lua's |module| command. |
| 648 |
The reason is that this command has disappeared in the new version of Lua and |
| 649 |
that it is not really needed. |
| 650 |
|
| 651 |
Users of your class can import and use your class by writing: |
| 652 |
% |
| 653 |
\begin{codeexample}[code only, tikz syntax=false] |
| 654 |
... |
| 655 |
local SomeClass = require "pgf.gd.examples.SomeClass" |
| 656 |
... |
| 657 |
\end{codeexample} |
| 658 |
|
| 659 |
|
| 660 |
\subsection{The Graph Drawing Scope} |
| 661 |
\label{section-gd-gd-scope} |
| 662 |
|
| 663 |
\includeluadocumentationof{pgf.gd.interface.Scope} |
| 664 |
|
| 665 |
|
| 666 |
\subsection{The Model Classes} |
| 667 |
\label{section-gd-models} |
| 668 |
|
| 669 |
All that a graph drawing algorithm will ``see'' of the graph specified by the |
| 670 |
user is a ``graph object''. Such an object is an object-oriented model of the |
| 671 |
user's graph that no longer encodes the specific way in which the user |
| 672 |
specified the graph; it only encodes which nodes and edges are present. For |
| 673 |
instance, the \tikzname\ graph specification |
| 674 |
% |
| 675 |
\begin{codeexample}[code only] |
| 676 |
graph { a -- {b, c} } |
| 677 |
\end{codeexample} |
| 678 |
% |
| 679 |
\noindent and the graph specification |
| 680 |
% |
| 681 |
\begin{codeexample}[code only] |
| 682 |
node (a) { a } |
| 683 |
child { node (b) {b} } |
| 684 |
child { node (c) {c} } |
| 685 |
\end{codeexample} |
| 686 |
% |
| 687 |
will generate exactly the same graph object. |
| 688 |
|
| 689 |
\begin{luanamespace}{pgf.gd.}{model} |
| 690 |
This namespace contains the classes modeling graphs, nodes, and edges. |
| 691 |
Also, the |Coordinate| class is found here, since coordinates are also part |
| 692 |
of the modeling. |
| 693 |
\end{luanamespace} |
| 694 |
|
| 695 |
|
| 696 |
\subsubsection{Directed Graphs (Digraphs)} |
| 697 |
|
| 698 |
Inside the graph drawing engine, the only model of a graph that is available |
| 699 |
treats graphs as |
| 700 |
% |
| 701 |
\begin{enumerate} |
| 702 |
\item directed (all edges have a designated head and a designated tail) and |
| 703 |
\item simple (there can be at most one edge between any pair of nodes). |
| 704 |
\end{enumerate} |
| 705 |
% |
| 706 |
These two properties may appear to be somewhat at odds with what users can |
| 707 |
specify as graphs and with what some graph drawing algorithms might expect as |
| 708 |
input. For instance, suppose a user writes |
| 709 |
% |
| 710 |
\begin{codeexample}[code only] |
| 711 |
graph { a -- b --[red] c, b --[green, bend right] c } |
| 712 |
\end{codeexample} |
| 713 |
% |
| 714 |
In this case, it seems that the input graph for a graph drawing algorithm |
| 715 |
should actually be an \emph{undirected} graph in which there are |
| 716 |
\emph{multiple} edges (namely $2$) between |b| and~|c|. Nevertheless, the graph |
| 717 |
drawing engine will turn the user's input a directed simple graph in ways |
| 718 |
described later. You do not need to worry that information gets lost during |
| 719 |
this process: The \emph{syntactic digraph,} which is available to graph drawing |
| 720 |
algorithms on request, stores all the information about which edges are present |
| 721 |
in the original input graph. |
| 722 |
|
| 723 |
The main reasons for only considering directed, simple graphs are speed and |
| 724 |
simplicity: The implementation of these graphs has been optimized so that all |
| 725 |
operations on these graphs have a guaranteed running time that is small in |
| 726 |
practice. |
| 727 |
|
| 728 |
\includeluadocumentationof{pgf.gd.model.Digraph} |
| 729 |
|
| 730 |
|
| 731 |
\subsubsection{Vertices} |
| 732 |
|
| 733 |
\includeluadocumentationof{pgf.gd.model.Vertex} |
| 734 |
|
| 735 |
|
| 736 |
\subsubsection{Arcs} |
| 737 |
\label{section-gd-arc-model} |
| 738 |
|
| 739 |
\includeluadocumentationof{pgf.gd.model.Arc} |
| 740 |
|
| 741 |
|
| 742 |
\subsubsection{Edges} |
| 743 |
|
| 744 |
\includeluadocumentationof{pgf.gd.model.Edge} |
| 745 |
|
| 746 |
|
| 747 |
\subsubsection{Collections} |
| 748 |
|
| 749 |
\includeluadocumentationof{pgf.gd.model.Collection} |
| 750 |
|
| 751 |
|
| 752 |
\subsubsection{Coordinates, Paths, and Transformations} |
| 753 |
|
| 754 |
\includeluadocumentationof{pgf.gd.model.Coordinate} |
| 755 |
\includeluadocumentationof{pgf.gd.model.Path} |
| 756 |
\includeluadocumentationof{pgf.gd.lib.Transform} |
| 757 |
|
| 758 |
|
| 759 |
\subsubsection{Options and Data Storages for Vertices, Arcs, and Digraphs} |
| 760 |
|
| 761 |
Many objects in the graph drawing system have an |options| table attached to |
| 762 |
them. These tables will contain the different kinds options specified by the |
| 763 |
user for the object. For efficiency reasons, many objects may share the same |
| 764 |
options table (since, more often than not, almost all objects have exactly the |
| 765 |
same |options| table). For this reason, you cannot store anything in an options |
| 766 |
table, indeed, you should never attempt to write anything into an options |
| 767 |
table. Instead, you should use a |Storage|. |
| 768 |
|
| 769 |
\includeluadocumentationof{pgf.gd.lib.Storage} |
| 770 |
|
| 771 |
|
| 772 |
\subsubsection{Events} |
| 773 |
|
| 774 |
\includeluadocumentationof{pgf.gd.lib.Event} |
| 775 |
|
| 776 |
|
| 777 |
\subsection{Graph Transformations} |
| 778 |
\label{section-gd-transformations} |
| 779 |
|
| 780 |
\subsubsection{The Layout Pipeline} |
| 781 |
|
| 782 |
\includeluadocumentationof{pgf.gd.control.LayoutPipeline} |
| 783 |
|
| 784 |
|
| 785 |
\subsubsection{Hints For Edge Routing} |
| 786 |
|
| 787 |
\includeluadocumentationof{pgf.gd.routing.Hints} |
| 788 |
|
| 789 |
|
| 790 |
\subsection{The Interface To Algorithms} |
| 791 |
\label{section-gd-interface-to-algorithms} |
| 792 |
|
| 793 |
\includeluadocumentationof{pgf.gd.interface.InterfaceToAlgorithms} |
| 794 |
|
| 795 |
|
| 796 |
\subsection{Examples of Implementations of Graph Drawing Algorithms} |
| 797 |
\label{section-gd-examples} |
| 798 |
|
| 799 |
\includeluadocumentationof{pgf.gd.examples.library} |
| 800 |
\includeluadocumentationof{pgf.gd.examples.SimpleDemo} |
| 801 |
\includeluadocumentationof{pgf.gd.examples.SimpleEdgeDemo} |
| 802 |
\includeluadocumentationof{pgf.gd.examples.SimpleHuffman} |
| 803 |
|
| 804 |
|
| 805 |
\subsection{Support Libraries} |
| 806 |
\label{section-gd-libs} |
| 807 |
|
| 808 |
The present section lists a number of general-purpose libraries that are used |
| 809 |
by different algorithms. |
| 810 |
|
| 811 |
\subsubsection{Basic Functions} |
| 812 |
|
| 813 |
\includeluadocumentationof{pgf} |
| 814 |
|
| 815 |
\includeluadocumentationof{pgf.gd.lib} |
| 816 |
|
| 817 |
|
| 818 |
\subsubsection{Lookup Tables} |
| 819 |
|
| 820 |
\includeluadocumentationof{pgf.gd.lib.LookupTable} |
| 821 |
|
| 822 |
|
| 823 |
\subsubsection{Computing Distances in Graphs} |
| 824 |
|
| 825 |
\emph{Still needs to be ported to digraph classes!} |
| 826 |
|
| 827 |
%\includeluadocumentationof{pgf.gd.lib.PathLengths} |
| 828 |
|
| 829 |
|
| 830 |
\subsubsection{Priority Queues} |
| 831 |
|
| 832 |
\includeluadocumentationof{pgf.gd.lib.PriorityQueue} |