summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-overview.tex
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-overview.tex')
-rw-r--r--Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-overview.tex317
1 files changed, 317 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-overview.tex b/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-overview.tex
new file mode 100644
index 00000000000..cae05728476
--- /dev/null
+++ b/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-gd-overview.tex
@@ -0,0 +1,317 @@
+% Copyright 2010 by Renée Ahrens, Olof Frahm, Jens Kluttig, Matthias Schulz, Stephan Schuster
+% Copyright 2011 by Till Tantau
+% Copyright 2011 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}
+
+\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}[]
+\tikz \graph [binary tree layout, level distance=5mm] {
+ 4 -- {
+ 3 -- 0 -- 1[second],
+ 10 -- {
+ 8 -- {
+ 6 -- {5,7},
+ 9
+ } } }
+};
+\end{codeexample}
+
+\begin{codeexample}[]
+\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 graph drawing 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 layed
+out'') using a so-called ``layered graph drawing algorithm'' (what
+these are will be explained later):
+\begin{codeexample}[]
+\tikz [>=spaced stealth']
+ \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}[]
+\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}[]
+\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. \ No newline at end of file