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: /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.
"]]
}
|