diff options
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua')
-rw-r--r-- | Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua | 91 |
1 files changed, 91 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua new file mode 100644 index 00000000000..a3c03b7283e --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua @@ -0,0 +1,91 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua,v 1.3 2013/04/04 20:43:45 tantau Exp $ + + + +--- +-- A ``layered'' layout of a graph tries to arrange the nodes in +-- consecutive horizontal layers (naturally, by rotating the graph, this +-- can be changed in to vertical layers) such that edges tend to be only +-- between nodes on adjacent layers. Trees, for instance, can always be +-- laid out in this way. This method of laying out a graph is especially +-- useful for hierarchical graphs. +-- +-- The method implemented in this library is often called the +-- \emph{Sugiyama method}, which is a rather advanced method of +-- assigning nodes to layers and positions on these layers. The same +-- method is also used in the popular GraphViz program, indeed, the +-- implementation in \tikzname\ is based on the same pseudo-code from the +-- same paper as the implementation used in GraphViz and both programs +-- will often generate the same layout (but not always, as explained +-- below). The current implementation is due to Jannis Pohlmann, who +-- implemented it as part of his Diploma thesis. Please consult this +-- thesis for a detailed explanation of the Sugiyama method and its +-- history: +-- +-- \begin{itemize} +-- \item +-- Jannis Pohlmann, +-- \newblock \emph{Configurable Graph Drawing Algorithms +-- for the \tikzname\ Graphics Description Language,} +-- \newblock Diploma Thesis, +-- \newblock Institute of Theoretical Computer Science, Univerist\"at +-- zu L\"ubeck, 2011.\\[.5em] +-- \newblock Available online via +-- \url{http://www.tcs.uni-luebeck.de/downloads/papers/2011/}\\ \url{2011-configurable-graph-drawing-algorithms-jannis-pohlmann.pdf} +-- \\[.5em] +-- (Note that since the publication of this thesis some option names +-- have been changed. Most noticeably, the option name +-- |layered drawing| was changed to |layered layout|, which is somewhat +-- more consistent with other names used in the graph drawing +-- libraries. Furthermore, the keys for choosing individual +-- algorithms for the different algorithm phases, have all changed.) +-- \end{itemize} +-- +-- The Sugiyama methods lays out a graph in five steps: +-- \begin{enumerate} +-- \item Cycle removal. +-- \item Layer assignment (sometimes called node ranking). +-- \item Crossing minimization (also referred to as node ordering). +-- \item Node positioning (or coordinate assignment). +-- \item Edge routing. +-- \end{enumerate} +-- It turns out that behind each of these steps there lurks an +-- NP-complete problem, which means, in practice, that each step is +-- impossible to perform optimally for larger graphs. For this reason, +-- heuristics and approximation algorithms are used to find a ``good'' +-- way of performing the steps. +-- +-- A distinctive feature of Pohlmann's implementation of the Sugiyama +-- method for \tikzname\ is that the algorithms used for each of the +-- steps can easily be exchanged, just specify a different option. For +-- the user, this means that by specifying a different +-- option and thereby using a different heuristic for one of the steps, a +-- better layout can often be found. For the researcher, this means that +-- one can very easily test new approaches and new heuristics without +-- having to implement all of the other steps anew. +-- +-- @library + +local layered + + +-- Load declarations from: +require "pgf.gd.layered" + +-- Load algorithms from: +require "pgf.gd.layered.Sugiyama" +require "pgf.gd.layered.cycle_removal" +require "pgf.gd.layered.node_ranking" +require "pgf.gd.layered.crossing_minimization" +require "pgf.gd.layered.node_positioning" +require "pgf.gd.layered.edge_routing" + |