% 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}
\label{section-gd-display-layer}

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

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


\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 \todosp{should
\texttt{.pushPhase} be \texttt{.pushOption}? (bug \#396)} 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}
