summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2014-02-27 00:01:50 +0000
committerKarl Berry <karl@freefriends.org>2014-02-27 00:01:50 +0000
commit90ae413a94da014dbf7a6a8ab584f7c668483a5a (patch)
tree4e0528a2b2fb2004988e7fc804ea2f1354f1f5d5 /Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua
parent800cc56380d1edfe567a6a66bef13e8950eb2b0c (diff)
pgf 3.0.0
git-svn-id: svn://tug.org/texlive/trunk@33057 c570f23f-e606-0410-a88d-b1316a301751
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.lua91
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"
+