Debian Codegraph @

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

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