summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua
blob: 9f681929ecb89bfca2cff6fbb27938cbdb57b453 (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
-- 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, 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"