summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua81
1 files changed, 81 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua
new file mode 100644
index 00000000000..16e3b1653de
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua
@@ -0,0 +1,81 @@
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed and/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/crossing_minimization.lua,v 1.3 2013/05/23 20:01:27 tantau Exp $
+
+
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+---
+-- @section subsection {Crossing Minimization (Node Ordering)}
+--
+-- The number of edge crossings in a layered drawing is determined by
+-- the ordering of nodes at each of its layers. Therefore, crossing
+-- minimization is the problem of reordering the nodes at each layer
+-- so that the overall number of edge crossings is minimized. The
+-- crossing minimization step takes a proper layering where every edge
+-- connects nodes in neighbored layers, allowing algorithms to
+-- minimize crossings layer by layer rather than all at once. While
+-- this does not reduce the complexity of the problem, it does make it
+-- considerably easier to understand and implement. Techniques based
+-- on such an iterative approach are also known as layer-by-layer
+-- sweep methods. They are used in many popular heuristics due to
+-- their simplicity and the good results they produce.
+--
+-- Sweeping refers to moving up and down from one layer to the next,
+-- reducing crossings along the way. In layer-by-layer sweep methods,
+-- an initial node ordering for one of the layers is computed
+-- first. Depending on the sweep direction this can either be the
+-- first layer or the last; in rare occasions the layer in the middle
+-- is used instead. Followed by this, the actual layer-by-layer sweep
+-- is performed. Given an initial ordering for the first layer $L_1$, a
+-- downward sweep first holds the nodes in $L_1$ fixed while reordering
+-- the nodes in the second layer $L_2$ to reduce the number of
+-- crossings between $L_1$ and $L_2$. It then goes on to reorder the
+-- third layer while holding the second layer fixed. This is continued
+-- until all layers except for the first one have been
+-- examined. Upward sweeping and sweeping from the middle work
+-- analogous.
+--
+-- Obviously, the central aspect of the layer-by-layer sweep is how
+-- the nodes of a specific layer are reordered using a neighbored
+-- layer as a fixed reference. This problem is known as one-sided
+-- crossing minimization, which unfortunately is NP-hard. In the
+-- following various heuristics to solve this problem are
+-- presented.
+--
+-- For more details, please see Section 4.1.4 of Pohlmann's Diploma
+-- thesis.
+--
+-- @end
+
+
+
+---
+
+declare {
+ key = "sweep crossing minimization",
+ algorithm = require "pgf.gd.layered.CrossingMinimizationGansnerKNV1993",
+ phase = "crossing minimization",
+ phase_default = true,
+
+ summary = [["
+ Gansner et al. combine an initial ordering based on a depth-first
+ search with the median and greedy switch heuristics applied in the
+ form of an alternating layer-by-layer sweep based on a weighted
+ median.
+ "]],
+ documentation = [["
+ For more details, please see Section 4.1.4 of Pohlmann's Diploma
+ thesis.
+
+ This is the default algorithm for crossing minimization.
+ "]]
+ }