summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua
blob: 950e02ffa361c53fdaa88f9a5707bfb4acca2f08 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
-- 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$



---
-- 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, Universit\"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"