summaryrefslogtreecommitdiff
path: root/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2023-01-16 03:03:27 +0000
committerNorbert Preining <norbert@preining.info>2023-01-16 03:03:27 +0000
commit6f9e1680085e7bb4d258f6f8116369d122e196e1 (patch)
tree9ac0ecb239240d1d672b188f29c1479de215074b /graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered
parentb8345f39630408bb198e7636381ce4240154ca9b (diff)
CTAN sync 202301160303
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered')
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/BarycenterHeuristic.lua23
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/CoffmanGrahamRanking.lua35
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/DfsAcyclicSubgraph.lua27
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/FastHierarchyLayout.lua99
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/FastSimpleHierarchyLayout.lua99
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/GreedyCycleRemoval.lua27
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/GreedyInsertHeuristic.lua23
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/LongestPathRanking.lua57
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/MedianHeuristic.lua24
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/OptimalRanking.lua35
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/SiftingHeuristic.lua34
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/SplitHeuristic.lua24
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/SugiyamaLayout.lua113
13 files changed, 620 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/BarycenterHeuristic.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/BarycenterHeuristic.lua
new file mode 100644
index 0000000000..5e4138eece
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/BarycenterHeuristic.lua
@@ -0,0 +1,23 @@
+-- Copyright 2013 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$
+
+
+local key = require 'pgf.gd.doc'.key
+local documentation = require 'pgf.gd.doc'.documentation
+local summary = require 'pgf.gd.doc'.summary
+local example = require 'pgf.gd.doc'.example
+
+
+
+--------------------------------------------------------------------
+key "BarycenterHeuristic"
+summary "The barycenter heuristic for 2-layer crossing minimization."
+--------------------------------------------------------------------
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/CoffmanGrahamRanking.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/CoffmanGrahamRanking.lua
new file mode 100644
index 0000000000..fd13e9bd4b
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/CoffmanGrahamRanking.lua
@@ -0,0 +1,35 @@
+-- Copyright 2013 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$
+
+
+local key = require 'pgf.gd.doc'.key
+local documentation = require 'pgf.gd.doc'.documentation
+local summary = require 'pgf.gd.doc'.summary
+local example = require 'pgf.gd.doc'.example
+
+
+--------------------------------------------------------------------
+key "CoffmanGrahamRanking"
+summary "The ranking algorithm due to Coffman and Graham."
+documentation
+[[
+|CoffmanGrahamRanking| implements a node ranking algorithm based on
+the Coffman--Graham scheduling algorithm, which can be used as first
+phase in |SugiyamaLayout|. The aim of the algorithm is to ensure that
+the height of the ranking (the number of layers) is kept small.
+]]
+--------------------------------------------------------------------
+
+
+--------------------------------------------------------------------
+key "CoffmanGrahamRanking.width"
+summary "A mysterious width parameter..."
+--------------------------------------------------------------------
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/DfsAcyclicSubgraph.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/DfsAcyclicSubgraph.lua
new file mode 100644
index 0000000000..eced60b2ed
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/DfsAcyclicSubgraph.lua
@@ -0,0 +1,27 @@
+-- Copyright 2013 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$
+
+
+local key = require 'pgf.gd.doc'.key
+local documentation = require 'pgf.gd.doc'.documentation
+local summary = require 'pgf.gd.doc'.summary
+local example = require 'pgf.gd.doc'.example
+
+
+
+--------------------------------------------------------------------
+key "DfsAcyclicSubgraph"
+summary "DFS-based algorithm for computing a maximal acyclic subgraph."
+documentation
+[[
+The algorithm simply removes all DFS-backedges and works in linear-time.
+]]
+--------------------------------------------------------------------
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/FastHierarchyLayout.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/FastHierarchyLayout.lua
new file mode 100644
index 0000000000..a7baad7e10
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/FastHierarchyLayout.lua
@@ -0,0 +1,99 @@
+-- Copyright 2013 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$
+
+
+local key = require 'pgf.gd.doc'.key
+local documentation = require 'pgf.gd.doc'.documentation
+local summary = require 'pgf.gd.doc'.summary
+local example = require 'pgf.gd.doc'.example
+
+
+--------------------------------------------------------------------
+key "FastHierarchyLayout"
+summary "Coordinate assignment phase for the Sugiyama algorithm by Buchheim et al."
+documentation
+[[
+This class implements a hierarchy layout algorithm, that is, it
+layouts hierarchies with a given order of nodes on each
+layer. It is used as a third phase of the Sugiyama algorithm.
+
+All edges of the layout will have at most two
+bends. Additionally, for each edge having exactly two bends, the
+segment between them is drawn vertically. This applies in
+particular to the long edges arising in the first phase of the
+Sugiyama algorithm.
+
+The implementation is based on:
+%
+\begin{itemize}
+ \item
+ Christoph Buchheim, Michael Jünger, Sebastian Leipert: A Fast
+ Layout Algorithm for k-Level Graphs. \emph{Proc. Graph
+ Drawing 2000}, volume 1984 of LNCS, pages 229--240, 2001.
+\end{itemize}
+]]
+
+example
+[[
+\tikz \graph [SugiyamaLayout, FastHierarchyLayout] {
+ a -- {b,c,d} -- e -- a;
+};
+]]
+--------------------------------------------------------------------
+
+
+
+--------------------------------------------------------------------
+key "FastHierarchyLayout.fixedLayerDistance"
+summary "If true, the distance between neighbored layers is fixed, otherwise variable."
+--------------------------------------------------------------------
+
+
+
+
+--------------------------------------------------------------------
+key "FastHierarchyLayout.layerDistance"
+summary "Separation distance (padding) between two consecutive layers."
+
+documentation
+[[
+Sets the (minimum?) padding between nodes on two consecutive
+layers. It defaults to the sum of the keys
+|level pre sep| and |level post sep|.
+]]
+
+example
+[[
+\tikz \graph [SugiyamaLayout, FastHierarchyLayout,
+ level sep=1cm] {
+ a -- {b,c,d} -- e -- a;
+};
+]]
+--------------------------------------------------------------------
+
+--------------------------------------------------------------------
+key "FastHierarchyLayout.nodeDistance"
+summary "Separation distance (padding) between two consecutive nodes on the same layer."
+
+documentation
+[[
+Sets the (minimum?) padding between sibling nodes. It defaults to the
+sum of the keys |sibling pre sep| and |sibling post sep|.
+]]
+
+example
+[[
+\tikz \graph [SugiyamaLayout, FastHierarchyLayout,
+ sibling sep=5mm] {
+ a -- {b,c,d} -- e -- a;
+};
+]]
+--------------------------------------------------------------------
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/FastSimpleHierarchyLayout.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/FastSimpleHierarchyLayout.lua
new file mode 100644
index 0000000000..4af6daa620
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/FastSimpleHierarchyLayout.lua
@@ -0,0 +1,99 @@
+-- Copyright 2013 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$
+
+
+local key = require 'pgf.gd.doc'.key
+local documentation = require 'pgf.gd.doc'.documentation
+local summary = require 'pgf.gd.doc'.summary
+local example = require 'pgf.gd.doc'.example
+
+
+--------------------------------------------------------------------
+key "FastSimpleHierarchyLayout"
+summary "Coordinate assignment phase for the Sugiyama algorithm by Ulrik Brandes and Boris Köpf."
+
+documentation
+[[
+This class implements a hierarchy layout algorithm, that is, it
+layouts hierarchies with a given order of nodes on each
+layer. It is used as a third phase of the Sugiyama algorithm.
+
+The algorithm runs in three phases:
+%
+\begin{enumerate}
+ \item Alignment (4x)
+ \item Horizontal Compactation (4x)
+ \item Balancing
+\end{enumerate}
+%
+The alignment and horizontal compactification phases are calculated
+downward, upward, left-to-right and right-to-left. The four
+resulting layouts are combined in a balancing step.
+
+Warning: The implementation is known to not always produce a
+correct layout. Therefore this Algorithm is for testing purpose
+only.
+
+The implementation is based on:
+%
+\begin{itemize}
+ \item
+ Ulrik Brandes, Boris Köpf: Fast and Simple Horizontal
+ Coordinate Assignment. \emph{LNCS} 2002, Volume 2265/2002,
+ pp. 33--36
+\end{itemize}
+]]
+
+example
+[[
+\tikz \graph [SugiyamaLayout, FastSimpleHierarchyLayout] {
+ a -- {b,c,d} -- e -- a;
+};
+]]
+--------------------------------------------------------------------
+
+
+
+--------------------------------------------------------------------
+key "FastSimpleHierarchyLayout.layerDistance"
+summary "Distance between the centers of nodes of two consecutive layers."
+
+documentation
+[[
+Sets the (minimum?) distance between nodes on two consecutive
+layers. It defaults to the key |level distance|.
+]]
+example
+[[
+\tikz \graph [SugiyamaLayout, FastSimpleHierarchyLayout,
+ level distance=2cm] {
+ a -- {b,c,d} -- e -- a;
+};
+]]
+--------------------------------------------------------------------
+
+--------------------------------------------------------------------
+key "FastSimpleHierarchyLayout.siblingDistance"
+summary "Distance between the centers of nodes of sibling nodes."
+
+documentation
+[[
+Sets the (minimum?) padding between sibling nodes. It defaults to
+|sibling distance|.
+]]
+example
+[[
+\tikz \graph [SugiyamaLayout, FastSimpleHierarchyLayout,
+ sibling distance=5mm] {
+ a -- {b,c,d} -- e -- a;
+};
+]]
+--------------------------------------------------------------------
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/GreedyCycleRemoval.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/GreedyCycleRemoval.lua
new file mode 100644
index 0000000000..d2f1d8eeea
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/GreedyCycleRemoval.lua
@@ -0,0 +1,27 @@
+-- Copyright 2013 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$
+
+
+local key = require 'pgf.gd.doc'.key
+local documentation = require 'pgf.gd.doc'.documentation
+local summary = require 'pgf.gd.doc'.summary
+local example = require 'pgf.gd.doc'.example
+
+
+--------------------------------------------------------------------
+key "GreedyCycleRemoval"
+summary "Greedy algorithm for computing a maximal acyclic subgraph."
+documentation
+[[
+ The algorithm applies a greedy heuristic to compute a maximal
+ acyclic subgraph and works in linear-time.
+]]
+--------------------------------------------------------------------
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/GreedyInsertHeuristic.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/GreedyInsertHeuristic.lua
new file mode 100644
index 0000000000..a8cd94ef19
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/GreedyInsertHeuristic.lua
@@ -0,0 +1,23 @@
+-- Copyright 2013 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$
+
+
+local key = require 'pgf.gd.doc'.key
+local documentation = require 'pgf.gd.doc'.documentation
+local summary = require 'pgf.gd.doc'.summary
+local example = require 'pgf.gd.doc'.example
+
+
+
+--------------------------------------------------------------------
+key "GreedyInsertHeuristic"
+summary "The greedy-insert heuristic for 2-layer crossing minimization."
+--------------------------------------------------------------------
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/LongestPathRanking.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/LongestPathRanking.lua
new file mode 100644
index 0000000000..3d98fbe9c6
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/LongestPathRanking.lua
@@ -0,0 +1,57 @@
+-- Copyright 2013 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$
+
+
+local key = require 'pgf.gd.doc'.key
+local documentation = require 'pgf.gd.doc'.documentation
+local summary = require 'pgf.gd.doc'.summary
+local example = require 'pgf.gd.doc'.example
+
+
+--------------------------------------------------------------------
+key "LongestPathRanking"
+summary "The longest-path ranking algorithm."
+documentation
+[[
+ |LongestPathRanking| implements the well-known longest-path ranking
+ algorithm, which can be used as first phase in |SugiyamaLayout|. The
+ implementation contains a special optimization for reducing edge
+ lengths, as well as special treatment of mixed-upward graphs (for
+ instance, \textsc{uml} class diagrams).
+]]
+--------------------------------------------------------------------
+
+
+--------------------------------------------------------------------
+key "LongestPathRanking.separateDeg0Layer"
+summary "If set to true, isolated nodes are placed on a separate layer."
+--------------------------------------------------------------------
+
+
+--------------------------------------------------------------------
+key "LongestPathRanking.separateMultiEdges"
+summary "If set to true, multi-edges will span at least two layers."
+--------------------------------------------------------------------
+
+
+
+--------------------------------------------------------------------
+key "LongestPathRanking.optimizeEdgeLength"
+summary
+[[
+ If set to true the ranking algorithm tries to reduce edge
+ length even if this might increase the height of the layout. Choose
+ false, if the longest-path ranking known from the literature should be
+ used.
+]]
+--------------------------------------------------------------------
+
+
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/MedianHeuristic.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/MedianHeuristic.lua
new file mode 100644
index 0000000000..b37480ac78
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/MedianHeuristic.lua
@@ -0,0 +1,24 @@
+-- Copyright 2013 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$
+
+
+local key = require 'pgf.gd.doc'.key
+local documentation = require 'pgf.gd.doc'.documentation
+local summary = require 'pgf.gd.doc'.summary
+local example = require 'pgf.gd.doc'.example
+
+
+
+--------------------------------------------------------------------
+key "MedianHeuristic"
+summary "The median heuristic for 2-layer crossing minimization."
+--------------------------------------------------------------------
+
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/OptimalRanking.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/OptimalRanking.lua
new file mode 100644
index 0000000000..25a8dd5262
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/OptimalRanking.lua
@@ -0,0 +1,35 @@
+-- Copyright 2013 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$
+
+
+local key = require 'pgf.gd.doc'.key
+local documentation = require 'pgf.gd.doc'.documentation
+local summary = require 'pgf.gd.doc'.summary
+local example = require 'pgf.gd.doc'.example
+
+
+--------------------------------------------------------------------
+key "OptimalRanking"
+summary "The optimal ranking algorithm."
+documentation
+[[
+ The |OptimalRanking| implements the LP-based algorithm for
+ computing a node ranking with minimal edge lengths, which can
+ be used as first phase in |SugiyamaLayout|.
+]]
+--------------------------------------------------------------------
+
+
+
+--------------------------------------------------------------------
+key "OptimalRanking.separateMultiEdges"
+summary "If set to true, multi-edges will span at least two layers."
+--------------------------------------------------------------------
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/SiftingHeuristic.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/SiftingHeuristic.lua
new file mode 100644
index 0000000000..d0815a5b76
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/SiftingHeuristic.lua
@@ -0,0 +1,34 @@
+-- Copyright 2013 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$
+
+
+local key = require 'pgf.gd.doc'.key
+local documentation = require 'pgf.gd.doc'.documentation
+local summary = require 'pgf.gd.doc'.summary
+local example = require 'pgf.gd.doc'.example
+
+
+
+--------------------------------------------------------------------
+key "SiftingHeuristic"
+summary "The sifting heuristic for 2-layer crossing minimization."
+--------------------------------------------------------------------
+
+
+--------------------------------------------------------------------
+key "SiftingHeuristic.strategy"
+summary "Sets a so-called ``sifting strategy''."
+documentation
+[[
+ The following values are permissible: |left_to_right|, |desc_degree|,
+ and |random|.
+]]
+--------------------------------------------------------------------
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/SplitHeuristic.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/SplitHeuristic.lua
new file mode 100644
index 0000000000..1579c7153d
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/SplitHeuristic.lua
@@ -0,0 +1,24 @@
+-- Copyright 2013 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$
+
+
+local key = require 'pgf.gd.doc'.key
+local documentation = require 'pgf.gd.doc'.documentation
+local summary = require 'pgf.gd.doc'.summary
+local example = require 'pgf.gd.doc'.example
+
+
+
+--------------------------------------------------------------------
+key "SplitHeuristic"
+summary "The split heuristic for 2-layer crossing minimization."
+--------------------------------------------------------------------
+
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/SugiyamaLayout.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/SugiyamaLayout.lua
new file mode 100644
index 0000000000..ec75fa7e6e
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/doc/ogdf/layered/SugiyamaLayout.lua
@@ -0,0 +1,113 @@
+-- Copyright 2013 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$
+
+
+local key = require 'pgf.gd.doc'.key
+local documentation = require 'pgf.gd.doc'.documentation
+local summary = require 'pgf.gd.doc'.summary
+local example = require 'pgf.gd.doc'.example
+
+
+--------------------------------------------------------------------------------
+key "SugiyamaLayout"
+summary "The OGDF implementation of the Sugiyama algorithm."
+
+documentation [[
+ This layout represents a customizable implementation of Sugiyama's
+ layout algorithm. The implementation used in |SugiyamaLayout| is based
+ on the following publications:
+
+ \begin{itemize}
+ \item Emden R. Gansner, Eleftherios Koutsofios, Stephen
+ C. North, Kiem-Phong Vo: A technique for drawing directed
+ graphs. \emph{IEEE Trans. Software Eng.} 19(3):214--230, 1993.
+ \item Georg Sander: \emph{Layout of compound directed graphs.}
+ Technical Report, Universität des Saarlandes, 1996.
+ \end{itemize}
+]]
+
+example
+[[
+\tikz \graph [SugiyamaLayout] { a -- {b,c,d} -- e -- a };
+]]
+
+example
+[[
+\tikz \graph [SugiyamaLayout, grow=right] {
+ a -- {b,c,d} -- e -- a
+};
+]]
+
+example
+[[
+\tikz [nodes={text height=.7em, text depth=.2em,
+ draw=black!20, thick, fill=white, font=\footnotesize},
+ >={Stealth[round,sep]}, rounded corners, semithick]
+ \graph [SugiyamaLayout, FastSimpleHierarchyLayout, grow=-80,
+ level distance=1.5cm, sibling distance=7mm] {
+ "5th Edition" -> { "6th Edition", "PWB 1.0" };
+ "6th Edition" -> { "LSX", "1 BSD", "Mini Unix", "Wollongong", "Interdata" };
+ "Interdata" -> { "Unix/TS 3.0", "PWB 2.0", "7th Edition" };
+ "7th Edition" -> { "8th Edition", "32V", "V7M", "Ultrix-11", "Xenix", "UniPlus+" };
+ "V7M" -> "Ultrix-11";
+ "8th Edition" -> "9th Edition";
+ "1 BSD" -> "2 BSD" -> "2.8 BSD" -> { "Ultrix-11", "2.9 BSD" };
+ "32V" -> "3 BSD" -> "4 BSD" -> "4.1 BSD" -> { "4.2 BSD", "2.8 BSD", "8th Edition" };
+ "4.2 BSD" -> { "4.3 BSD", "Ultrix-32" };
+ "PWB 1.0" -> { "PWB 1.2" -> "PWB 2.0", "USG 1.0" -> { "CB Unix 1", "USG 2.0" }};
+ "CB Unix 1" -> "CB Unix 2" -> "CB Unix 3" -> { "Unix/TS++", "PDP-11 Sys V" };
+ { "USG 2.0" -> "USG 3.0", "PWB 2.0", "Unix/TS 1.0" } -> "Unix/TS 3.0";
+ { "Unix/TS++", "CB Unix 3", "Unix/TS 3.0" } ->
+ "TS 4.0" -> "System V.0" -> "System V.2" -> "System V.3";
+ };
+]]
+--------------------------------------------------------------------------------
+
+
+
+--------------------------------------------------------------------------------
+key "SugiyamaLayout.runs"
+summary "Determines, how many times the crossing minimization is repeated."
+documentation
+[[
+Each repetition (except for the first) starts with
+randomly permuted nodes on each layer. Deterministic behavior can
+be achieved by setting |SugiyamaLayout.runs| to 1.
+]]
+--------------------------------------------------------------------------------
+
+
+
+--------------------------------------------------------------------------------
+key "SugiyamaLayout.transpose"
+documentation [[
+ Determines whether the transpose step is performed
+ after each 2-layer crossing minimization; this step tries to
+ reduce the number of crossings by switching neighbored nodes on
+ a layer.
+]]
+--------------------------------------------------------------------------------
+
+
+
+--------------------------------------------------------------------------------
+key "SugiyamaLayout.fails"
+documentation [[
+ The number of times that the number of crossings may
+ not decrease after a complete top-down bottom-up traversal,
+ before a run is terminated.
+]]
+--------------------------------------------------------------------------------
+
+
+-- Local Variables:
+-- mode:latex
+-- End: