% Copyright 2012 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}[]
\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}[]
\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}[]
\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}[]
\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}[] 
\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}[] 
\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] 
\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}[] 
\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}[] 
\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}[] 
\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}[] 
\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] 
\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}[] 
\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}

\endinput

