% Copyright 2019 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{Using Graph Drawing in \tikzname}

{\noindent {\emph{by Till Tantau}}}

\begin{tikzlibrary}{graphdrawing}
    This package provides capabilities for automatic graph drawing. It requires
    that the document is typeset using Lua\TeX. This package should work with
    Lua\TeX\ 0.54 or higher.
\end{tikzlibrary}

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


\subsection{Choosing a Layout and a Library}

The graph drawing engine is initialized when you load the library
|graphdrawing|. This library provides the basic framework for graph drawing,
including all options and keys described in the present section. However, this
library does \emph{not} load any actual algorithms for drawing graphs. For
this, you need to use the following command, which is defined by the
|graphdrawing| library:

\begin{command}{\usegdlibrary\marg{list of libraries}}
    This command is used to load the special graph drawing libraries (the |gd|
    in the name of the command stands for ``graph drawing''). The \meta{list of
    libraries} is a comma-separated list of library written in the Lua
    programming language (which is why a special command is needed).

    In detail, this command does the following. For each \meta{name} in the
    \meta{list of libraries} we do:
    %
    \begin{enumerate}
        \item Check whether Lua\TeX\ can call |require| on the library file
            |pgf.gd.|\meta{name}|.library|. Lua\TeX's usual file search
            mechanism  will search the texmf-trees in the usual manner and the
            dots in the file name get converted into directory slashes.
        \item If the above failed, try to |require| the string
            |pgf.gd.|\meta{name}.
        \item If this fails, try to |require| the string \meta{name}|.library|.
        \item If this fails, try to |require| the string \meta{name}. If this
            fails, print an error message.
    \end{enumerate}
    %
    The net effect of the above is the following: Authors of graph drawing
    algorithms can bundle together multiple algorithms in a library by creating
    a |...xyz/library.lua| file that internally just calls |require| for all
    files containing declarations. On the other hand, if a graph drawing
    algorithm completely fits inside a single file, it can also be read
    directly using |\usegdlibrary|.
    %
\begin{codeexample}[code only]
\usetikzlibrary{graphdrawing}
\usegdlibrary{trees,force}
\end{codeexample}

    The different graph drawing libraries are documented in the following
    Sections~\ref{section-first-graphdrawing-library-in-manual} to
    \ref{section-last-graphdrawing-library-in-manual}.
\end{command}

Note that in addition to the graph \emph{drawing} libraries, you may also wish
to load the normal \tikzname\ library |graphs|. It provides the powerful
|graph| path command with its easy-to-use syntax for specifying graphs, but you
can use the graph drawing engine independently of the |graphs| library, for
instance in conjunction with the |child| or the |edge| syntax. Here is a
typical setup:
%
\begin{codeexample}[code only]
\usetikzlibrary{graphs, graphdrawing}
\usegdlibrary{trees, layered}
\end{codeexample}

Having set things up, you must then specify for which scopes the graph drawing
engine should apply a layout algorithm to the nodes in the scope. Typically,
you just add an option ending with |... layout| to the |graph| path operation
and then let the graph drawing do its magic:
%
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{layered}}]
\tikz [rounded corners]
  \graph [layered layout, sibling distance=8mm, level distance=8mm]
  {
    a -> {
      b,
      c -> { d, e }
    } ->
    f ->
    a
  };
\end{codeexample}

Whenever you use such an option, you can:
%
\begin{itemize}
    \item Create nodes in the usual way. The nodes will be created completely,
        but then tucked away in an internal table. This means that all of
        \tikzname's options for nodes can be applied. You can also name a node
        and reference it later.
    \item Create edges using either the syntax of the |graph| command (using
        |--|, |<-|, |->|, or |<->|), or using the |edge| command, or using the
        |child| command. These edges will, however, not be created immediately.
        Instead, the basic layer's command |\pgfgdedge| will be called, which
        stores ``all the information concerning the edge''. The actual drawing
        of the edge will only happen after all nodes have been positioned.
    \item Most of the keys that can be passed to an edge will work as expected.
        In particular, you can add labels to edges using the usual |node|
        syntax for edges.
    \item The |label| and |pin| options can be used in the usual manner with
        nodes inside a graph drawing scope. Only, the labels and nodes will
        play no role in the positioning of the nodes and they are added when
        the nodes are finally positioned.
    \item Similarly, nodes that are placed ``on an edge'' using the implicit
        positioning syntax can be used in the usual manner.
\end{itemize}
%
Here are some things that will \emph{not} work:
%
\begin{itemize}
    \item Only edges created using the graph syntax, the |edge| command, or the
        |child| command will correctly pass their connection information to the
        basic layer. When you write |\draw (a)--(b);| inside a graph drawing
        scope, where |a| and |b| are nodes that have been created inside the
        scope, you will get an error message / things will look wrong. The
        reason is that the usual |--| is not ``caught'' by the graph drawing
        engine and, thus, tries to immediately connect two nodes that do not
        yet exist (except inside some internal table).
    \item The options of edges are executed twice: Once when the edge is
        ``examined'' by the |\pgfgdedge| command (using some magic to shield
        against the side effects) and then once more when the edge is actually
        created. Fortunately, in almost all cases, this will not be a problem;
        but if you do very evil magic inside your edge options, you must roll a
        D100 to see what strange things will happen. (Do no evil, by the way.)
\end{itemize}

If you are really interested in the ``fine print'' of what happens, please see
Section~\ref{section-gd-pgf}.


\subsection{Graph Drawing Parameters}

Graph drawing algorithms can typically be configured in some way. For instance,
for a graph drawing algorithm that visualizes its nodes as a tree, it will
typically be useful when the user can change the so-called \emph{level
distance} and the \emph{sibling distance}. For other algorithms, like
force-based algorithms, a large number of parameters influence the way the
algorithms work. Options that influence graph drawing algorithms will be called
\emph{(graph drawing) parameters} in the following. From the user's point of
view, these parameters look like normal \tikzname\ keys and you set them in the
usual way. Internally, they are treated a bit differently from normal keys
since their ``effect'' becomes apparent only later on, namely during the run of
the graph drawing algorithm.

A graph drawing algorithm may or may not take different graph parameters into
account. After all, these options may even outright contradict each other, so
an algorithm can only try to ``do its best''. While many graph parameters are
very specific to a single algorithm, a number of graph parameters will be
important for many algorithms and they are documented in the course of the
present section. Here is an example of an option the ``always works'':
%
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{force}}]
\tikz \graph [spring layout, vertical=1 to 2] { 1--2--3--1 };
\end{codeexample}

\includeluadocumentationof{pgf.gd.control.Distances}
\includeluadocumentationof{pgf.gd.control.Anchoring}
\includeluadocumentationof{pgf.gd.control.Orientation}

\includeluadocumentationof{pgf.gd.control.FineTune}

\includeluadocumentationof{pgf.gd.control.Components}
\includeluadocumentationof{pgf.gd.control.ComponentOrder}
\includeluadocumentationof{pgf.gd.control.ComponentDirection}
\includeluadocumentationof{pgf.gd.control.ComponentAlign}
\includeluadocumentationof{pgf.gd.control.ComponentDistance}

\includeluadocumentationof{pgf.gd.control.NodeAnchors}

\includeluadocumentationof{pgf.gd.model.Hyperedge}


\subsection{Using Several Different Layouts to Draw a Single Graph}
\label{section-gd-sublayouts}

Inside each graph drawing scope, a main algorithm is used to perform the graph
drawing. However, parts of the graph may be drawn using different algorithms:
For instance, a graph might consist of several, say, cliques that are arranged
in a tree-like fashion. In this case, it might be useful to layout each clique
using a circular layout, but then lay out all laid out cliques using a tree
drawing algorithm.

In order to lay out a graph using multiple algorithms, we need two things:
First, we must be able to \emph{specify} which algorithms should be used where
and, second, we must be able to \emph{resolve} conflicts that may result from
different algorithms ``having different ideas'' concerning where nodes should
be placed.


\subsubsection{Sublayouts}

Specifying different layouts for a graph is easy: Inside a graph drawing scope,
simply open scopes, in which you use an option like |tree layout| for the nodes
mentioned in this scope. Inside these scopes, you can open even subscopes for
sublayouts, and so on. Furthermore, the |graphs| library has special support
for sublayouts.

Let us start with the ``plain'' syntax for opening sublayouts: You pass a key
for creating layouts to a |scope|:
%
\begin{codeexample}[preamble={\usetikzlibrary{graphdrawing}
\usegdlibrary{force,trees}}]
\tikz [spring layout] {
  \begin{scope}[tree layout]
    \node (a) {a};
    \node (b) {b};
    \node (c) {c};
    \draw (a) edge (b) edge (c);
  \end{scope}

  \begin{scope}[tree layout]
    \node (1) {1};
    \node (2) {2};
    \draw (1) edge (2);
  \end{scope}

  \draw (a) edge (1);
}
\end{codeexample}

Let us see, what is going on here. The main layout (|spring layout|) contains
two sublayouts (the two |tree layouts|). Both of them are laid out
independently (more on the details in a moment). Then, from the main layout's
point of view, the sublayouts behave like ``large nodes'' and, thus, the edge
between |a| and |1| is actually the only edge that is used by the
|spring layout| -- resulting in a simple layout consisting of one big node at
the top and a big node at the bottom.

The |graphs| library has a special support for sublayouts: The syntax is as
follows: wherever a normal node would go, you can write
%
\begin{quote}
    |//| \opt{\oarg{layout options}} |{|\meta{sublayout}|}|
\end{quote}

Following the double slash, you may provide \meta{layout options} in square
brackets. However, you \emph{must} provide a sublayout in braces. The contents
of \meta{sublayout} will be parsed using the usual |graph| syntax, but will
form a sublayout.
%
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{force,trees}}]
\tikz \graph [spring layout] {
  // [tree layout] { a -- {b, c} };
  // [tree layout] { 1 -- 2 };
  a -- 1;
};
\end{codeexample}

In the above example, there is no node before the double slash, which means
that the two sublayouts will be part of the main graph, but will not be
indicated otherwise.
%
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{circular,trees}}]
\tikz \graph [simple necklace layout] {
 // [simple necklace layout] { a -> b -> c -> d -> e -> f -> a };

 // [tree layout] { % first tentacle
   a -> {1, 2};
 };

 // [tree layout] {% second tentacle
   d -> {3, 4 -> {5, 6}}
 };
};
\end{codeexample}

In the above example, the first sublayout is the one for the nodes with letter
names. These nodes are arranged using a simple necklace layout as the sublayout
inherits this option from the main layout. The two small trees (|a -> {1, 2}|
and the tree starting at the |d| node) are also sublayouts, triggered by the
|tree layout| option. They are also arranged. Then, all of the layouts are
merged (as described later). The result is actually a single node, so the main
layout does nothing here.

Compare the above to the following code:
%
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{circular,trees}}]
\tikz \graph [simple necklace layout] {
  // [tree layout] { % first ``giant node''
    a -> {1, 2};
  };

  a -> b -> c -> d;

  // [tree layout] {% second ``giant node''
    d -> {3, 4 -> {5, 6}}
  },

  d -> e -> f -> a;
};
\end{codeexample}

Here, only the two trees are laid out first. They are then contracted into
``giant nodes'' and these are then part of the set of nodes that are arranged
by the |simple necklace layout|. For details of how this contracting works, see
below.


\subsubsection{Subgraph Nodes}

A \emph{subgraph node} is a special kind of node that ``surrounds'' the
vertices of a subgraph. The special property of a subgraph node opposed to a
normal node is that it is created only after the subgraph has been laid out.
However, the difference to a collection like |hyper| is that the node is
available immediately as a normal node in the sense that you can connect edges
to it.

The syntax used to declare a subgraph node in a |graph| specification is as
follows:
%
\begin{quote}
    \opt{|"|}\meta{node name}\opt{|"|}\opt{|/|\opt{|"|}\meta{text}\opt{|"|}}
    \opt{\oarg{node options}} |//| \opt{\oarg{layout options}} |{|\meta{subgraph}|}|
\end{quote}

The idea ist that a subgraph node is declared like a normal node specification,
but is followed by a double slash and a subgraph:
%
\begin{codeexample}[
    width=5cm,
    preamble={\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{circular,trees}},
]
\tikz \graph [simple necklace layout] {
     tree 1[draw, circle] // [tree layout] { a -> {1, 2}; }
  -> b
  -> c
  -> tree 2[draw] // [tree layout] { d -> {3, 4 -> {5, 6} } }
  -> e
  -> f
  -> tree 1;
};
\end{codeexample}

Note how the two subgraph nodes |tree 1| and |tree 2| surround the two smaller
trees. In the example, both had trees as contents and these trees were rendered
using a sublayout. However, a subgraph layout does not need to have its own
layout: If you do \emph{not} provide a layout name after the double slash, the
subgraph node will simply surround all nodes that were placed by the main
layout wherever they were placed:
%
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{trees}}]
\tikz [subgraph text bottom=text centered,
       subgraph nodes={font=\itshape}]
  \graph [tree layout] {
    a -> { b -> {c, d}, e -> {f, g -> h} };

    left [draw]  // { b, c, d };
    right [draw] // { e, f, g, h};

    left <-> right;
  };
\end{codeexample}

Every time a subgraph node is created, the following style is execute:

\begin{key}{/tikz/every subgraph node}
    Set a subgraph node style.
\end{key}

\begin{key}{/tikz/subgraph nodes=\meta{style}}
    Sets the |every subgraph node| style to \meta{style}.
    %
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{trees}}]
\tikz [subgraph text bottom=text centered,
       subgraph nodes=red]
  \graph [tree layout] {
    a -> { b -> {c, d}, e -> {f, g -> h} };

    left [draw]  // { b, c, d };
    right [draw] // { e, f, g, h};

    left <-> right;
  };
\end{codeexample}
    %
\end{key}

\begin{key}{/tikz/subgraph text none}
    When this option is used, the text of a subgraph node is not shown. Adding
    a slash after the node name achieves roughly the same effect, but this
    option is useful in situations when subgraph nodes generally should not
    have any text inside them.
    %
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{trees}}]
\tikz [subgraph text none]
  \graph [tree layout] {
    a -> { b -> {c, d}, e -> {f, g -> h} };

    left [draw]  // { b, c, d };
    right [draw] // { e, f, g, h};

    left <-> right;
  };
\end{codeexample}
    %
\end{key}

\begin{key}{/tikz/subgraph text top=\meta{text alignment options} (default text ragged right)}
    Specifies that the text of a subgraph node should be placed at the top of
    the subgraph node: Still inside the node, but above all nodes inside the
    subgraph node.
    %
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{trees}}]
\tikz [subgraph text top=text ragged left]
  \graph [tree layout] {
    a -> { b -> {c, d}, e -> {f, g -> h} };

    left [draw]  // { b, c, d };
    right [draw] // { e, f, g, h};

    left <-> right;
  };
\end{codeexample}
    %
    You can pass any of the \meta{text alignment options} understood by
    \tikzname, such as |text centered|:
    %
\begin{codeexample}[
    width=5cm,
    preamble={\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{trees}},
]
\tikz [subgraph text top=text centered]
  \graph [tree layout] {
    a -> { b -> {c, d}, e -> {f, g -> h} };

    left [draw, circle] // { b, c, d };
  };
\end{codeexample}
    %
    To place a label \emph{outside} the subgraph node, use a label, typically
    defined using the |quotes| library:
    %
\begin{codeexample}[preamble={\usetikzlibrary{graphs,graphdrawing,quotes}
\usegdlibrary{trees}}]
\tikz \graph [tree layout] {
    a -> { b -> {c, d}, e -> {f, g -> h} };

    / ["left", draw]  // { b, c, d } <->
    / ["right", draw] // { e, f, g, h};
  };
\end{codeexample}
    %
\end{key}

\begin{key}{/tikz/subgraph text bottom=\meta{text alignment options} (default ragged right)}
    Works like |subgraph text top|, only the text placed at the bottom.
\end{key}

Note that there are no keys |subgraph text left| or |... right|, for somewhat
technical reasons.

\begin{key}{/tikz/subgraph text sep=\meta{dimension} (initially .1em)}
    Some space added between the inner nodes of a subgraph node and the text
    labels.
\end{key}


\subsubsection{Overlapping Sublayouts}
\label{section-gd-layout-resolve}

Nodes and edges can be part of several layouts. This will inevitably lead to
conflicts because algorithm will disagree on where a node should be placed on
the canvas. For this reason, there are some rules governing how such conflicts
are resolved: Given a layout, starting with the main layout, the graph drawing
system does the following:
%
\begin{enumerate}
    \item We start by first processing the (direct) sublayouts of the current
        layout (recursively). Sublayouts may overlap (they may share one or
        more nodes), but we run the specified layout algorithm for each
        sublayout independently on a ``fresh copy'' of all the nodes making up
        the sublayout. In particular, different, conflicting positions may be
        computed for nodes when they are present in several sublayouts.
    \item Once all nodes in the sublayouts have been laid out in this way, we
        \emph{join} overlapping elements. The idea is that if two layouts share
        exactly one vertex, we can shift them around so that his vertex is at
        the same position in both layouts. In more detail, the following
        happens:

        We build a (conceptual) graph whose nodes are the sublayouts and in
        which there is an edge between two nodes if the sublayouts represented
        by these elements have a node in common. Inside the resulting graph, we
        treat each connected component separately. Each component has the
        property that the sublayouts represented by the nodes in the component
        overlap by at least one node. We now \emph{join} them as follows: We
        start with the first sublayout in the component (``first'' with respect
        to the order in which they appear in the input graph) and ``mark'' this
        sublayout. We loop the following instructions as long as possible:
        Search for the first sublayout (again, with respect to the order in
        which they appear in the input) that is connect by an edge to a marked
        sublayout. The sublayout will now have at least one node in common with
        the marked sublayouts (possibly, even more). We consider the first such
        node (again, first respect to the input ordering) and shift the whole
        sublayout is such a way that this particular node is at the position is
        has in the marked sublayouts. Note that after the shift, other nodes
        that are also present in the marked sublayouts may lie at a different
        position in the current sublayout. In this case, the position in the
        marked sublayouts ``wins''. We then mark the sublayout.
    \item When the above algorithm has run, we will have computed positions for
        all nodes in all sublayouts of each of the components. For each
        component, we contract all nodes of the component to a single node.
        This new node will be ``large'' in the sense that its convex hull is
        the convex hull of all the nodes in the component. All nodes that used
        to be part of the component are removed and the new large node is added
        (with arcs adjusted appropriately).
    \item We now run the layout's algorithm on the resulting nodes (the
        remaining original nodes and the contracted nodes).
    \item In a last step, once the graph has been laid out, we expand the nodes
        that were previously contracted. For this, the nodes that were deleted
        earlier get reinserted, but shifted by whatever amount the contraction
        node got shifted.
\end{enumerate}


\subsection{Miscellaneous Options}

\includeluadocumentationof{pgf.gd.control.library}