summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-display-layer.tex
blob: d5848375067e9d38b4cfac7fb7dededa57b13bb0 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
% Copyright 2010-2011 by Renée Ahrens
% Copyright 2010-2011 by Olof Frahm
% Copyright 2010-2011 by Jens Kluttig
% Copyright 2010-2011 by Matthias Schulz
% Copyright 2010-2011 by Stephan Schuster
% Copyright 2011 by Jannis Pohlmann
% Copyright 2011 by Till Tantau
%
% This file may be distributed and/or modified
%
% 1. under the LaTeX Project Public License and/or
% 2. under the GNU Free Documentation License.
%
% See the file doc/generic/pgf/licenses/LICENSE for more details.


\section{The Display Layer}

{\noindent {\itshape{by Till Tantau}}}

\ifluatex\else This section of the manual can only be typeset using Lua\TeX.\expandafter\endinput\fi

\label{section-gd-display-layer}

\begin{quote}
  \itshape You do not need to read this section in order to write new
  graph drawing algorithms. It is of interest only to those wishing to
  write programs that wish to ``use'' the graph drawing system in a
  similar way that \tikzname\ does for laying out graphs that are
  generated and then passed down from the program to the graph drawing
  system.
\end{quote}


\subsection{Introduction: The Interplay of the Different Layers}

The job of the graph drawing system is to run graph drawing algorithms
on graphs. Since graph drawing is useful in many different contexts,
not only in the context of \tikzname\ for which the present system was
originally developed, the graph drawing system was designed in such a
way that it can be used independently of \tikzname. To achieve this,
the \emph{display layer} provides an interface via which an arbitrary
program (\tikzname, a graph editor, a command line interface, etc.)
``talk'' to the graph drawing system.

To better understand how this works, let us consider the following
setup: 

\begin{itemize}
\item A program would like to communicate with the graph
  drawing system. It is written in Java and its job is to analyse social
  networks. This software would like to use graph drawing to produce
  drawings of some ``social graphs'' arising from its analyses. This
  software will be called ``the display system'' in the following.
\item There are two algorithms that the display system would like to apply to
  the graphs its produces. Let us call these algorithms ``A'' and
  ``B''. However, the display system would also, ideally, wish to make it
  possible that its user chooses other algorithms ``C'' that are not
  necessarily part of its binary.
\item The display system has internally generated a ``social graph'' that it
  would now like to draw.
\end{itemize}

For this setup, the communication between the different layers of the
graph drawing system is as follows:

\begin{enumerate}
\item The display system, being written in Java, must embed Lua to use the
  graph drawing system.
\item The display system must initialize the graph drawing system. For this,
  it must use |require| on the file |InterfaceToDisplay|, which, as
  the name suggests, contains the interface between the display
  system and the graph drawing system.
  
  It must also create a so-called ``binding'' between the
  graph drawing system and the display layer. See
  Section~\ref{section-gd-binding-layer} for more information on
  bindings.
\item The display system now needs to load the declarations of the
  algorithms A and B. For this, it just needs to apply |require| to
  the files in which the algorithms reside. This will cause the
  |declare| function to be called. This function is declared by
  |InterfaceToAlgorithms| and allows files to declare that certain
  algorithms and options are now available.

  Once this is done, the graph drawing system is fully initialized and
  can be used.
\item Later on, the display system wishes to lay out a social graph. Note
  that this is known as ``drawing the graph'' in the graph drawing
  community, even though this only means the coordinates are computed
  for the nodes of the graph. The actual ``rendering'' of the graph on
  the display is the job of the display system (hence the name ``display
  layer'').
\item To start the layout process, the display system calls the function
  |beginGraphDrawingScope| of the class |InterfaceToDisplay|.
\item Next, for each vertex the function |createVertex| of the
  interface class must be called and similarly for each edge. These
  calls will cause an internal model of the graph to be created on the
  algorithm layer. Options that are attached to nodes and edges are
  also communicated to the graph drawing system through function calls
  like |pushOption|.
\item When the graph is fully specified, the method
  |runGraphDrawingAlgorithm| must be called, which is once more a
  method of the interface class. This function will internally discern
  which algorithms have been chosen (via options) and invoke the code
  of the appropriate algorithms.
\item Next, the function |renderGraph| must be called. Its job is to
  ``communicate back'' which coordinates have been computed. It will
  use the binding for this communication, see
  Section~\ref{section-gd-binding-layer}.
\item Finally, by calling |endGraphDrawingScope|, the resources needed
  for the layout process for the social graph are freed once more.
\end{enumerate}

A few points may be noteworthy:
\begin{itemize}
\item The whole communication between the display system and the graph
  drawing system goes through the interface class via function
  calls. This makes it easy to communicate with display system whose
  internal model of graphs is quite different from the one used in Lua
  (as is certainly the case for \TeX, but also the ``social graph''
  mentioned above need not even exist as a separate entity inside the
  display system).
  
  \emph{The display system should only rely on the interface
    class. All communication has to go through this class, the
    display system may not access the internals of the internally
    constructed graphs directly.}
\item New algorithms can be loaded at runtime, as long as the
  |require| method is supported.
\item The display system can also use the interface class to query which
  algorithms and which options are available in principle (and display
  this information to the user). The display system can even get access the
  documentation of the options at runtime since the documentation is
  stored in fields of the declared options.
\end{itemize}


In the following, we first present a simple display system other than
\tikzname. The remainder of the section then encompasses a
documentation of the different functions of the class
|InterfaceToDisplay|. 



\subsection{An Example Display System}

In the following, we present the code of a very simple display system
written in Lua (another such display system is \tikzname\ itself, but
the minimal system will allow us to focus on what is really
needed). You will also find it in |pgf.gd.examples.ASCIIDisplayer|. 

The job of this display system is to parse a string that encodes a graph
and to call the appropriate functions of |InterfaceToDisplay| to lay
out the graph. The actual calls for rendering the graph are part of
the binding, which is documented in
Section~\ref{section-gd-binding-layer-example}.

The syntax of the to-be-laid-out graph is a reduced version of
\tikzname's |graph| syntax: The string must start with
|graph[|\meta{algorithm's name}|]{| and end with |}|. Between the
braces, all lines must either be of the form \meta{node name}|;| or
\meta{name 1}|->|\meta{name 2}|;| with optional spaces around the node
names.

Let us now have a look at what we must do to use the graph drawing
system. First, we load some libraries and initialize the binding (see
Section~\ref{section-gd-binding-layer-example} for details on the
binding; we can ignore it for now).

\begin{codeexample}[code only]
local InterfaceToDisplay = require "pgf.gd.interface.InterfaceToDisplay"
InterfaceToDisplay.bind(require "pgf.gd.examples.BindingToASCII")

-- Load two libraries that define graph drawing algorithms. We can do this only *after* the binding
-- has been created since they call the declare function internally.
require "pgf.gd.layered.library"
require "pgf.gd.force.library"
\end{codeexample}

Now comes some preparation code that starts a graph drawing scope and
sets up the algorithm to the string provided between the square
brackets:

\begin{codeexample}[code only]
local algorithm = io.read():match("%s*graph%s*%[(.-)%]")
  
InterfaceToDisplay.pushPhase(algorithm, "main", 1)
InterfaceToDisplay.pushOption("level distance", 6, 2)
InterfaceToDisplay.pushOption("sibling distance", 8, 3)
InterfaceToDisplay.beginGraphDrawingScope(3)
InterfaceToDisplay.pushLayout(4)
\end{codeexample}

The numbers |1| to |4| are the positions on the options stack at which
the options should be placed. See the description of |pushOption| for
more details.

We are now ready to create the vertices and edges via a very simple
parser:

\begin{codeexample}[code only]
for line in io.lines() do
  if line:match("}") then
    break
  elseif line:find("-") then
    local n1, dir, n2 = string.match(line, "^%s*(.-)%s*(-.)%s*(.-)%s*;")
    InterfaceToDisplay.createEdge(n1, n2, dir, 4)
  else
    local n1 = string.match(line, "^%s*(.-)%s*;")
    InterfaceToDisplay.createVertex(n1, "rectangle", nil, 4)
  end
end
\end{codeexample}

The graph is now completely constructed inside the graph drawing
system. We can now invoke the algorithms:

\begin{codeexample}[code only]
InterfaceToDisplay.runGraphDrawingAlgorithm()
InterfaceToDisplay.renderGraph()
InterfaceToDisplay.endGraphDrawingScope()
\end{codeexample}

We can now run the resulting file using the Lua interpreter. If we
provide the input shown on the left, we get the output shown on the
right:

\bigskip
\noindent
\begin{minipage}[t]{.5\textwidth}
\emph{Input given to ASCIIDisplayer:}  
  
\begin{verbatim}
graph [layered layout] {
  Alice;
  Bob;
  Charly;
  Dave;
  Eve;
  Fritz;
  George;
  Alice -> Bob;
  Alice -> Charly;
  Charly -> Dave;
  Bob -> Dave;
  Dave -> Eve;
  Eve -> Fritz;
  Fritz -> Alice;
  George -> Eve;
  George -> Fritz;
  Alice -> George;
}  
\end{verbatim}
\end{minipage}%
\begin{minipage}[t]{.49\textwidth}
\emph{Output produced by ASCIIDisplayer:}  
  
\begin{verbatim}
                   Alice                            
                 .......                            
               .. .  .  .                           
            ...  .   .   .                          
         ...   ..    .    ..                        
       ..     .      .      .                       
  Charly    Bob      .       .                      
      ..     .       .       .                      
        .    .       .       .                      
         .   .       .       .                      
          .. .       .       .                      
            ..       .       .                      
           Dave   George     .                      
              ..     . ...   .                      
                .    .    .. .                      
                 .   .      ...                     
                  .. .       . ...                  
                    ..       .    ..                
                    Eve      .      ..              
                      ..     .     ..               
                        .    .    .                 
                         .   .   .                  
                          .. . ..                   
                            ...                     
                           Fritz                    
\end{verbatim}
\end{minipage}


\subsection{The Interface to Display Systems}

\includeluadocumentationof{pgf.gd.interface.InterfaceToDisplay}