% Copyright 2019 by Renée Ahrens, Olof Frahm, Jens Kluttig, Matthias Schulz, Stephan Schuster
% Copyright 2019 by Till Tantau
% Copyright 2019 by Jannis Pohlmann
%
% 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{Introduction to Algorithmic Graph Drawing}
\label{section-intro-gd}

\emph{by Till Tantau}

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


\subsection{What Is Algorithmic Graph Drawing?}

\emph{Algorithmic graph drawing} (or just \emph{graph drawing} in the
following) is the process of computing algorithmically where the nodes of a
graph are positioned on a page so that the graph ``looks nice''. The idea is
that you, as human (or you, as a machine, if you happen to be a machine and
happen to be reading this document) just specify which nodes are present in a
graph and which edges are present. Additionally, you may add some ``hints''
like ``this node should be near the center'' or ``this edge is pretty
important''. You do \emph{not} specify where, exactly, the nodes and edges
should be. This is something you leave to a \emph{graph drawing algorithm}. The
algorithm gets your description of the graph as an input and then decides where
the nodes should go on the page.
%
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{trees}}]
\tikz \graph [binary tree layout, level distance=5mm] {
  4 -- {
    3 -- 0 -- 1[second],
    10 -- {
      8 -- {
        6 -- {5,7},
        9
  } } }
};
\end{codeexample}

\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing,quotes}
\usegdlibrary{force}}]
\tikz \graph [spring layout,
  edge quotes mid,
  edges={nodes={font=\scriptsize, fill=white, sloped, inner sep=1pt}}]
{
  1 ->["Das"] 2 ->["ist"] 3 ->["das"] 4 ->["Haus"]
  2 ->["vom" near start] 5 ->["Ni"] 4 ->["ko" near start]
  1 ->["laus", orient=right] 5;
};
\end{codeexample}

Naturally, graph drawing is a bit of a (black?) art. There is no ``perfect''
way of drawing a graph, rather, depending on the circumstances there are
several different ways of drawing the same graph and often it will just depend
on the aesthetic sense of the reader which layout he or she would prefer. For
this reason, there are a huge number of graph drawing algorithms ``out there''
and there are scientific conference devoted to such algorithms, where each year
dozens of new algorithms are proposed.

Unlike the rest of \pgfname\ and \tikzname, which is implemented purely in
\TeX, the graph drawing algorithms are simply too complex to be implemented
directly in \TeX. Instead, the programming language Lua is used by the
|graphdrawing| library -- a programming language that has been integrated into
recent versions of \TeX. This means that (a) as a user of the graph drawing
engine you run \TeX\ on your documents in the usual way, no external programs
are called since Lua is already integrated into \TeX, and (b) it is pretty easy
to implement new graph drawing algorithms for \tikzname\ since Lua can be used
and no \TeX\ programming knowledge is needed.


\subsection{Using the Graph Drawing System}

``Users'' of the graph drawing engine can invoke the graph drawing algorithms
often by just adding a single option to their picture. Here is a typical
example, where the |layered layout| option tells \tikzname\ that the graph
should be drawn (``should be laid out'') using a so-called ``layered graph
drawing algorithm'' (what these are will be explained later):
%
\begin{codeexample}[preamble={\usetikzlibrary{arrows.meta,graphs,graphdrawing}
\usegdlibrary{layered}}]
\tikz [>={Stealth[round,sep]}]
  \graph [layered layout, components go right top aligned, nodes=draw, edges=rounded corners]
  {
    first root -> {1 -> {2, 3, 7} -> {4, 5}, 6 }, 4 -- 5;
    second root -> x -> {a -> {u,v}, b, c -> d -> {w,z} };
    third root -> child -> grandchild -> youngster -> third root;
  };
\end{codeexample}
%
Here is another example, where a different layout method is used that is more
appropriate for trees:
%
\begin{codeexample}[preamble={\usetikzlibrary{graphdrawing}
\usegdlibrary{trees}}]
\tikz [grow'=up, binary tree layout, nodes={circle,draw}]
  \node {1}
  child { node {2}
    child { node {3} }
    child { node {4}
      child { node {5} }
      child { node {6} }
    }
  }
  child { node {7}
    child { node {8}
      child[missing]
      child { node {9} }
    }
  };
\end{codeexample}
%
A final example, this time using a ``spring electrical layout'' (whatever that
might be\dots):
%
\begin{codeexample}[
    preamble={\usetikzlibrary{decorations.pathmorphing,graphdrawing}
\usegdlibrary{force}}]
\tikz [spring electrical layout, node distance=1.3cm,
       every edge/.style={
         decoration={coil, aspect=-.5, post length=1mm,
                     segment length=1mm, pre length=2mm},
         decorate, draw}]
{
  \foreach \i in {1,...,6}
    \node (node \i) [fill=blue!50, text=white, circle] {\i};

  \draw (node 1) edge (node 2)
        (node 2) edge (node 3)
                 edge (node 4)
        (node 3) edge (node 4)
                 edge (node 5)
                 edge (node 6);
}
\end{codeexample}
%
In all of the example, the positions of the nodes have only been computed
\emph{after} all nodes have been created and the edges have been specified. For
instance, in the last example, without the option |spring electrical layout|,
all of the nodes would have been placed on top of each other.


\subsection{Extending the Graph Drawing System}

The graph drawing engine is also intended to make is (relatively) easy to
implement new graph drawing algorithms. These algorithms can either be
implemented in the Lua programming language (which is \emph{much} easier to
program than \TeX\ itself) or in C/C++ (but at a great cost regarding
portability). The Lua code for a graph drawing algorithm gets an
object-oriented model of the input graph as an input and must just compute the
desired new positions of the nodes. The complete handling of passing options
and configurations back-and-forth between the different \tikzname\ and
\pgfname\ layers is handled by the graph drawing engine.

As a caveat, the graph drawing engine comes with a library of functions and
methods that simplify the writing of new graph drawing algorithms. As a typical
example, when you implement a graph drawing algorithm for trees, you typically
require that your input is a tree; but you can bet that users will feed all
sorts of graphs to your algorithm, including disjoint unions of cliques. The
graph drawing engine offers you to say that a precondition to running your
algorithm is that the graph is a |tree| and instead of the original graph your
algorithm will be provided with a spanning tree of the graph on which it can
work. There are numerous further automatic pre- and postprocessing steps that
include orienting, anchoring, and packing of components, to name a few.

The bottom line is that the graph drawing engine makes it easy
to try out new graph drawing algorithms for medium sized graphs (up
to a few hundred nodes) in Lua. For larger graphs, C/C++ code must be
used.


\subsection{The Layers of the Graph Drawing System}
\label{section-gd-layers}

Even though the graph drawing system presented in the following sections was
developed as part of \pgfname, it can be used independently of \pgfname\ and
\tikzname: It was (re)designed so that it can be used by arbitrary programs as
long as they are able to run Lua. To achieve this, the graph drawing system
consists of three layers:
%
\begin{enumerate}
    \item At the ``bottom'' we have the \emph{algorithmic layer}. This layer,
        written in Lua, contains all graph drawing algorithms. Interestingly,
        options must also be declared on this layer, so an algorithm together
        with all options it uses can and must be specified entirely on this
        layer. If you intend to implement a new graph drawing algorithm, you
        will only be interested in the functionality of this layer.

        Algorithm ``communicate'' with the graph drawing system through a
        well-defined interface, encapsulated in the class
        |InterfaceToAlgorithms|.
    \item At the ``top'' we have the \emph{display layer}. This layer is not
        actually part of the graph drawing system. Rather, it is a piece of
        software that ``displays'' graphs and \tikzname\ is just one example of
        such a software. Another example might be a graph editor that uses the
        graph drawing system to lay out the graph it displays. Yet another
        example might be a command line tool for drawing graphs described in a
        file. Finally, you may also wish to use the graph drawing system as a
        simple subroutine for rendering graphs produced in a larger program.

        Since the different possible instantiations of the display layer are
        quite heterogeneous, all display layers must communicate with the graph
        drawing system through a special interface, encapsulated in the class
        |InterfaceToDisplay|.

        The main job of this class is to provide a set of methods for
        specifying that a graph has certain nodes and edges and that certain
        options have been set for them. However, this interface also allows you
        to query all options that have been declared by algorithms, including
        their documentation. This way, an editor or a command line tool can
        display a list of all graph drawing algorithms and how they can be
        configured.
    \item The algorithm layer and the display layer are ``bound together''
        through the \emph{binding layer}. Most of the bookkeeping concerning
        the to-be-drawn graphs is done by the graph drawing system
        independently of which algorithm is used and also independently of
        which display layer is used, but some things are still specific to each
        display layer. For instance, some algorithms may create new nodes and
        the algorithms may then need to know how large these nodes will be. For
        this, the display layer must be ``queried'' during a run of the
        algorithm -- and it is the job of the binding layer to achieve this
        callback.

        As a rule, the binding layer implements the ``backward'' communication
        from the graph drawing system back to the display layer, while the
        display layer's interface class provides only functions that are called
        from the display layer but which will not ``talk back''.
\end{enumerate}

All of the files concerned with graph drawing reside in the |graphdrawing|
subdirectory of |generic/pgf|.


\subsection{Organisation of the Graph Drawing Documentation}

The documentation of the graph drawing engine is structured as follows:
%
\begin{enumerate}
    \item Following this overview section, the next section documents the graph
        drawing engine from ``the \tikzname\ user's point of view''. No
        knowledge of Lua or algorithmic graph drawing is needed for this
        section, everyone who intends to use algorithmic graph drawing in
        \tikzname\ may be interested in reading it.
    \item You will normally only use \tikzname's keys and commands in order to
        use the graph drawing system, but, internally, these keys call more
        basic \pgfname\ commands that do the ``hard work'' of binding the world
        of \TeX\ boxes and macros to the object-oriented world of Lua.
        Section~\ref{section-gd-pgf} explains how this works and which commands
        are available for authors of packages that directly need to use the
        graph drawing system inside \pgfname, avoiding the overhead incurred by
        \tikzname.

        Most readers can safely skip this section.
    \item The next sections detail which graph drawing algorithms are currently
        implemented as part of the \tikzname\ distribution, see
        Sections~\ref{section-first-graphdrawing-library-in-manual}
        to~\ref{section-last-graphdrawing-library-in-manual}.
    \item Section~\ref{section-gd-algorithm-layer} is addressed at readers who
        wish to implement their own graph drawing algorithms. For this,
        \emph{no knowledge at all} of \TeX\ programming is needed. The section
        explains the graph model used in Lua, the available libraries, the
        graph drawing pipeline, and everything else that is part of the Lua
        side of the engine.
    \item Section~\ref{section-gd-display-layer} details the display layer of
        the graph drawing system. You should read this section if you wish to
        implement a new display system (that is, a non-\TeX-based program) that
        intends to use the graph drawing system.
    \item Section~\ref{section-gd-binding-layer} explains how binding layers
        can be implemented. This section, too, is of interest only to readers
        who wish to write new display systems.
\end{enumerate}


\subsection{Acknowledgements}

Graph drawing in \tikzname\ began as a student's project under my supervision.
Ren\'ee Ahrens, Olof-Joachim Frahm, Jens Kluttig, Matthias Schulz, and Stephan
Schuster wrote the first prototype of a graph drawing system inside \tikzname\
that uses Lua\TeX\ for the implementation of graph drawing algorithms.

This first, early version was greatly extended on the algorithmic side by
Jannis Pohlmann who wrote his Diploma thesis on graph drawing under my
supervision. He implemented, in particular, the Sugiyama method
(|layered layout|) and force based algorithms. Also, he rewrote some of the
code of the prototype.

At some point it became apparent that the first implementation had a number of
deficiencies, both concerning the structure, the interfaces, and (in
particular) the performance. Because of this, I rewrote the code of the graph
drawing system, both on the \TeX\ side and on the Lua side in its current form.
However, I would like to stress that without the work of the people mentioned
above graph drawing in \tikzname\ would not exist.

The documentation was written almost entirely by myself, though I did copy some
paragraphs from Jannis's Diploma thesis, which I can highly recommend everyone
to read.

In the future, I hope that other people will contribute algorithms, which will
be available as libraries.