diff options
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua')
-rw-r--r-- | graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua | 81 |
1 files changed, 81 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua new file mode 100644 index 0000000000..54a1fafb23 --- /dev/null +++ b/graphics/pgf/base/tex/generic/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$ + + +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. + "]] +} |