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.tex392
1 files changed, 190 insertions, 202 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
index 4c86aa0ed47..39ecd659a87 100644
--- 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
@@ -10,32 +10,32 @@
% 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
+\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.
-
+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 -- {
@@ -49,6 +49,8 @@ input and then decides where the nodes should go on the page.
\end{codeexample}
\begin{codeexample}[]
+% \usetikzlibrary{graphs,graphdrawing,quotes}
+% \usegdlibrary{force}
\tikz \graph [spring layout,
edge quotes mid,
edges={nodes={font=\scriptsize, fill=white, sloped, inner sep=1pt}}]
@@ -56,49 +58,49 @@ input and then decides where the nodes should go on the page.
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.
+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):
+``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}[]
\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;
+ 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:
+%
+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}
@@ -116,8 +118,10 @@ that is more appropriate for trees:
}
};
\end{codeexample}
-A final example, this time using a ``spring electrical layout''
-(whatever that might be\dots):
+%
+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={
@@ -127,7 +131,7 @@ A final example, this time using a ``spring electrical layout''
{
\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)
@@ -136,39 +140,35 @@ A final example, this time using a ``spring electrical layout''
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.
+%
+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 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
@@ -176,143 +176,131 @@ 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:
-
+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''.
+ \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|.
+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:
+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.
+ \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
+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.