| 1 |
% Copyright 2010-2018 by Renée Ahrens |
| 2 |
% Copyright 2010-2018 by Olof Frahm |
| 3 |
% Copyright 2010-2018 by Jens Kluttig |
| 4 |
% Copyright 2010-2018 by Matthias Schulz |
| 5 |
% Copyright 2010-2018 by Stephan Schuster |
| 6 |
% Copyright 2018 by Jannis Pohlmann |
| 7 |
% Copyright 2018 by Till Tantau |
| 8 |
% |
| 9 |
% This file may be distributed and/or modified |
| 10 |
% |
| 11 |
% 1. under the LaTeX Project Public License and/or |
| 12 |
% 2. under the GNU Free Documentation License. |
| 13 |
% |
| 14 |
% See the file doc/generic/pgf/licenses/LICENSE for more details. |
| 15 |
|
| 16 |
|
| 17 |
\section{The Display Layer} |
| 18 |
\label{section-gd-display-layer} |
| 19 |
|
| 20 |
{\noindent {\itshape{by Till Tantau}}} |
| 21 |
|
| 22 |
\ifluatex |
| 23 |
\else |
| 24 |
This section of the manual can only be typeset using Lua\TeX. |
| 25 |
\expandafter\endinput |
| 26 |
\fi |
| 27 |
|
| 28 |
|
| 29 |
\begin{quote} |
| 30 |
\itshape You do not need to read this section in order to write new graph |
| 31 |
drawing algorithms. It is of interest only to those wishing to write |
| 32 |
programs that wish to ``use'' the graph drawing system in a similar way |
| 33 |
that \tikzname\ does for laying out graphs that are generated and then |
| 34 |
passed down from the program to the graph drawing system. |
| 35 |
\end{quote} |
| 36 |
|
| 37 |
|
| 38 |
\subsection{Introduction: The Interplay of the Different Layers} |
| 39 |
|
| 40 |
The job of the graph drawing system is to run graph drawing algorithms on |
| 41 |
graphs. Since graph drawing is useful in many different contexts, not only in |
| 42 |
the context of \tikzname\ for which the present system was originally |
| 43 |
developed, the graph drawing system was designed in such a way that it can be |
| 44 |
used independently of \tikzname. To achieve this, the \emph{display layer} |
| 45 |
provides an interface via which an arbitrary program (\tikzname, a graph |
| 46 |
editor, a command line interface, etc.) ``talk'' to the graph drawing system. |
| 47 |
|
| 48 |
To better understand how this works, let us consider the following setup: |
| 49 |
% |
| 50 |
\begin{itemize} |
| 51 |
\item A program would like to communicate with the graph drawing system. It |
| 52 |
is written in Java and its job is to analyse social networks. This |
| 53 |
software would like to use graph drawing to produce drawings of some |
| 54 |
``social graphs'' arising from its analyses. This software will be |
| 55 |
called ``the display system'' in the following. |
| 56 |
\item There are two algorithms that the display system would like to apply |
| 57 |
to the graphs its produces. Let us call these algorithms ``A'' and |
| 58 |
``B''. However, the display system would also, ideally, wish to make it |
| 59 |
possible that its user chooses other algorithms ``C'' that are not |
| 60 |
necessarily part of its binary. |
| 61 |
\item The display system has internally generated a ``social graph'' that |
| 62 |
it would now like to draw. |
| 63 |
\end{itemize} |
| 64 |
|
| 65 |
For this setup, the communication between the different layers of the graph |
| 66 |
drawing system is as follows: |
| 67 |
% |
| 68 |
\begin{enumerate} |
| 69 |
\item The display system, being written in Java, must embed Lua to use the |
| 70 |
graph drawing system. |
| 71 |
\item The display system must initialize the graph drawing system. For |
| 72 |
this, it must use |require| on the file |InterfaceToDisplay|, which, as |
| 73 |
the name suggests, contains the interface between the display system |
| 74 |
and the graph drawing system. |
| 75 |
|
| 76 |
It must also create a so-called ``binding'' between the graph drawing |
| 77 |
system and the display layer. See |
| 78 |
Section~\ref{section-gd-binding-layer} for more information on |
| 79 |
bindings. |
| 80 |
\item The display system now needs to load the declarations of the |
| 81 |
algorithms A and B. For this, it just needs to apply |require| to the |
| 82 |
files in which the algorithms reside. This will cause the |declare| |
| 83 |
function to be called. This function is declared by |
| 84 |
|InterfaceToAlgorithms| and allows files to declare that certain |
| 85 |
algorithms and options are now available. |
| 86 |
|
| 87 |
Once this is done, the graph drawing system is fully initialized and |
| 88 |
can be used. |
| 89 |
\item Later on, the display system wishes to lay out a social graph. Note |
| 90 |
that this is known as ``drawing the graph'' in the graph drawing |
| 91 |
community, even though this only means the coordinates are computed for |
| 92 |
the nodes of the graph. The actual ``rendering'' of the graph on the |
| 93 |
display is the job of the display system (hence the name ``display |
| 94 |
layer''). |
| 95 |
\item To start the layout process, the display system calls the function |
| 96 |
|beginGraphDrawingScope| of the class |InterfaceToDisplay|. |
| 97 |
\item Next, for each vertex the function |createVertex| of the interface |
| 98 |
class must be called and similarly for each edge. These calls will |
| 99 |
cause an internal model of the graph to be created on the algorithm |
| 100 |
layer. Options that are attached to nodes and edges are also |
| 101 |
communicated to the graph drawing system through function calls like |
| 102 |
|pushOption|. |
| 103 |
\item When the graph is fully specified, the method |
| 104 |
|runGraphDrawingAlgorithm| must be called, which is once more a method |
| 105 |
of the interface class. This function will internally discern which |
| 106 |
algorithms have been chosen (via options) and invoke the code of the |
| 107 |
appropriate algorithms. |
| 108 |
\item Next, the function |renderGraph| must be called. Its job is to |
| 109 |
``communicate back'' which coordinates have been computed. It will use |
| 110 |
the binding for this communication, see |
| 111 |
Section~\ref{section-gd-binding-layer}. |
| 112 |
\item Finally, by calling |endGraphDrawingScope|, the resources needed for |
| 113 |
the layout process for the social graph are freed once more. |
| 114 |
\end{enumerate} |
| 115 |
|
| 116 |
A few points may be noteworthy: |
| 117 |
% |
| 118 |
\begin{itemize} |
| 119 |
\item The whole communication between the display system and the graph |
| 120 |
drawing system goes through the interface class via function calls. |
| 121 |
This makes it easy to communicate with display system whose internal |
| 122 |
model of graphs is quite different from the one used in Lua (as is |
| 123 |
certainly the case for \TeX, but also the ``social graph'' mentioned |
| 124 |
above need not even exist as a separate entity inside the display |
| 125 |
system). |
| 126 |
|
| 127 |
\emph{The display system should only rely on the interface class. All |
| 128 |
communication has to go through this class, the display system may not |
| 129 |
access the internals of the internally constructed graphs directly.} |
| 130 |
\item New algorithms can be loaded at runtime, as long as the |require| |
| 131 |
method is supported. |
| 132 |
\item The display system can also use the interface class to query which |
| 133 |
algorithms and which options are available in principle (and display |
| 134 |
this information to the user). The display system can even get access |
| 135 |
the documentation of the options at runtime since the documentation is |
| 136 |
stored in fields of the declared options. |
| 137 |
\end{itemize} |
| 138 |
|
| 139 |
In the following, we first present a simple display system other than |
| 140 |
\tikzname. The remainder of the section then encompasses a documentation of the |
| 141 |
different functions of the class |InterfaceToDisplay|. |
| 142 |
|
| 143 |
|
| 144 |
\subsection{An Example Display System} |
| 145 |
|
| 146 |
In the following, we present the code of a very simple display system written |
| 147 |
in Lua (another such display system is \tikzname\ itself, but the minimal |
| 148 |
system will allow us to focus on what is really needed). You will also find it |
| 149 |
in |pgf.gd.examples.ASCIIDisplayer|. |
| 150 |
|
| 151 |
The job of this display system is to parse a string that encodes a graph and to |
| 152 |
call the appropriate functions of |InterfaceToDisplay| to lay out the graph. |
| 153 |
The actual calls for rendering the graph are part of the binding, which is |
| 154 |
documented in Section~\ref{section-gd-binding-layer-example}. |
| 155 |
|
| 156 |
The syntax of the to-be-laid-out graph is a reduced version of \tikzname's |
| 157 |
|graph| syntax: The string must start with |graph[|\meta{algorithm's name}|]{| |
| 158 |
and end with |}|. Between the braces, all lines must either be of the form |
| 159 |
\meta{node name}|;| or \meta{name 1}|->|\meta{name 2}|;| with optional spaces |
| 160 |
around the node names. |
| 161 |
|
| 162 |
Let us now have a look at what we must do to use the graph drawing system. |
| 163 |
First, we load some libraries and initialize the binding (see |
| 164 |
Section~\ref{section-gd-binding-layer-example} for details on the binding; we |
| 165 |
can ignore it for now). |
| 166 |
% |
| 167 |
\begin{codeexample}[code only] |
| 168 |
local InterfaceToDisplay = require "pgf.gd.interface.InterfaceToDisplay" |
| 169 |
InterfaceToDisplay.bind(require "pgf.gd.examples.BindingToASCII") |
| 170 |
|
| 171 |
-- Load two libraries that define graph drawing algorithms. We can do this only *after* the binding |
| 172 |
-- has been created since they call the declare function internally. |
| 173 |
require "pgf.gd.layered.library" |
| 174 |
require "pgf.gd.force.library" |
| 175 |
\end{codeexample} |
| 176 |
|
| 177 |
Now comes some preparation code that starts a graph drawing scope and sets up |
| 178 |
the algorithm to the string provided between the square \todosp{should |
| 179 |
\texttt{.pushPhase} be \texttt{.pushOption}? (bug \#396)} brackets: |
| 180 |
|
| 181 |
% |
| 182 |
\begin{codeexample}[code only] |
| 183 |
local algorithm = io.read():match("%s*graph%s*%[(.-)%]") |
| 184 |
|
| 185 |
InterfaceToDisplay.pushPhase(algorithm, "main", 1) |
| 186 |
InterfaceToDisplay.pushOption("level distance", 6, 2) |
| 187 |
InterfaceToDisplay.pushOption("sibling distance", 8, 3) |
| 188 |
InterfaceToDisplay.beginGraphDrawingScope(3) |
| 189 |
InterfaceToDisplay.pushLayout(4) |
| 190 |
\end{codeexample} |
| 191 |
|
| 192 |
The numbers |1| to |4| are the positions on the options stack at which the |
| 193 |
options should be placed. See the description of |pushOption| for more details. |
| 194 |
|
| 195 |
We are now ready to create the vertices and edges via a very simple parser: |
| 196 |
% |
| 197 |
\begin{codeexample}[code only] |
| 198 |
for line in io.lines() do |
| 199 |
if line:match("}") then |
| 200 |
break |
| 201 |
elseif line:find("-") then |
| 202 |
local n1, dir, n2 = string.match(line, "^%s*(.-)%s*(-.)%s*(.-)%s*;") |
| 203 |
InterfaceToDisplay.createEdge(n1, n2, dir, 4) |
| 204 |
else |
| 205 |
local n1 = string.match(line, "^%s*(.-)%s*;") |
| 206 |
InterfaceToDisplay.createVertex(n1, "rectangle", nil, 4) |
| 207 |
end |
| 208 |
end |
| 209 |
\end{codeexample} |
| 210 |
|
| 211 |
The graph is now completely constructed inside the graph drawing system. We can |
| 212 |
now invoke the algorithms: |
| 213 |
% |
| 214 |
\begin{codeexample}[code only] |
| 215 |
InterfaceToDisplay.runGraphDrawingAlgorithm() |
| 216 |
InterfaceToDisplay.renderGraph() |
| 217 |
InterfaceToDisplay.endGraphDrawingScope() |
| 218 |
\end{codeexample} |
| 219 |
|
| 220 |
We can now run the resulting file using the Lua interpreter. If we provide the |
| 221 |
input shown on the left, we get the output shown on the right: |
| 222 |
|
| 223 |
\bigskip |
| 224 |
\noindent |
| 225 |
\begin{minipage}[t]{.5\textwidth} |
| 226 |
\emph{Input given to ASCIIDisplayer:} |
| 227 |
|
| 228 |
\begin{verbatim} |
| 229 |
graph [layered layout] { |
| 230 |
Alice; |
| 231 |
Bob; |
| 232 |
Charly; |
| 233 |
Dave; |
| 234 |
Eve; |
| 235 |
Fritz; |
| 236 |
George; |
| 237 |
Alice -> Bob; |
| 238 |
Alice -> Charly; |
| 239 |
Charly -> Dave; |
| 240 |
Bob -> Dave; |
| 241 |
Dave -> Eve; |
| 242 |
Eve -> Fritz; |
| 243 |
Fritz -> Alice; |
| 244 |
George -> Eve; |
| 245 |
George -> Fritz; |
| 246 |
Alice -> George; |
| 247 |
} |
| 248 |
\end{verbatim} |
| 249 |
\end{minipage}% |
| 250 |
\begin{minipage}[t]{.49\textwidth} |
| 251 |
\emph{Output produced by ASCIIDisplayer:} |
| 252 |
|
| 253 |
\begin{verbatim} |
| 254 |
Alice |
| 255 |
....... |
| 256 |
.. . . . |
| 257 |
... . . . |
| 258 |
... .. . .. |
| 259 |
.. . . . |
| 260 |
Charly Bob . . |
| 261 |
.. . . . |
| 262 |
. . . . |
| 263 |
. . . . |
| 264 |
.. . . . |
| 265 |
.. . . |
| 266 |
Dave George . |
| 267 |
.. . ... . |
| 268 |
. . .. . |
| 269 |
. . ... |
| 270 |
.. . . ... |
| 271 |
.. . .. |
| 272 |
Eve . .. |
| 273 |
.. . .. |
| 274 |
. . . |
| 275 |
. . . |
| 276 |
.. . .. |
| 277 |
... |
| 278 |
Fritz |
| 279 |
\end{verbatim} |
| 280 |
\end{minipage} |
| 281 |
|
| 282 |
|
| 283 |
\subsection{The Interface to Display Systems} |
| 284 |
|
| 285 |
\includeluadocumentationof{pgf.gd.interface.InterfaceToDisplay} |