summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua
blob: 6bede7eb015fee575f14573075a833bd112cc864 (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
-- 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.
   "]]
 }