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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
-- 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 {Cycle Removal}
--
-- The Sugiyama method works only on directed \emph{acyclic}
-- graphs. For this reason, if the input graph is not (yet) acyclic, a
-- number of edges need to be redirected so that acyclicity arises. In
-- the following, the different options that allow you to fine-tune
-- this process are documented.
--
-- @end
---
declare {
key = "depth first cycle removal",
algorithm = require "pgf.gd.layered.CycleRemovalGansnerKNV1993",
phase = "cycle removal",
phase_default = true,
summary = [["
Selects a cycle removal algorithm that is especially
appropriate for graphs specified ``by hand''.
"]],
documentation = [["
When graphs are created by humans manually, one can
make assumptions about the input graph that would otherwise not
be possible. For instance, it seems reasonable to assume that the
order in which nodes and edges are entered by the user somehow
reflects the natural flow the user has had in mind for the graph.
In order to preserve the natural flow of the input graph, Gansner
et al.\ propose to remove cycles by performing a series of
depth-first searches starting at individual nodes in the order they
appear in the graph. This algorithm
implicitly constructs a spanning tree of the nodes reached during
the searches. It thereby partitions the edges of the graph into
tree edges and non-tree edges. The non-tree edges are further
subdivided into forward edges, cross edges, and back edges. Forward
edges point from a tree nodes to one of their descendants. Cross
edges connect unrelated branches in
the search tree. Back edges connect descendants to one of their
ancestors. It is not hard to see that reversing back edges will not
only introduce no new cycles but will also make any directed graph
acyclic. Gansner et al.\ argue that this approach is more stable
than others in that fewer inappropriate edges are reversed compared
to other methods, despite the lack of a provable upper bound
for the number of reversed edges.
See section 4.1.1 of Pohlmann's Diplom thesis for more details.
This is the default algorithm for cycle removals.
"]]
}
---
declare {
key = "prioritized greedy cycle removal",
algorithm = "pgf.gd.layered.CycleRemovalEadesLS1993",
phase = "cycle removal",
summary = [["
This algorithm implements a greedy heuristic of Eades et al.\ for
cycle removal that prioritizes sources and sinks.
"]],
documentation = [["
See section 4.1.1 of Pohlmann's Diploma theses for details.
"]]
}
---
declare {
key = "greedy cycle removal",
algorithm = "pgf.gd.layered.CycleRemovalEadesLS1993",
phase = "cycle removal",
summary = [["
This algorithm implements a greedy heuristic of Eades et al.\ for
cycle removal that prioritizes sources and sinks.
"]],
documentation = [["
See section 4.1.1 of Pohlmann's Diploma theses for details.
"]]
}
---
declare {
key = "naive greedy cycle removal",
algorithm = "pgf.gd.layered.CycleRemovalBergerS1990a",
phase = "cycle removal",
summary = [["
This algorithm implements a greedy heuristic of Berger and Shor for
cycle removal. It
is not really compared to the other heuristics and only included
for demonstration purposes.
"]],
documentation = [["
See section 4.1.1 of Pohlmann's Diploma theses for details.
"]]
}
---
declare {
key = "random greedy cycle removal",
algorithm = "pgf.gd.layered.CycleRemovalBergerS1990b",
phase = "cycle removal",
summary = [["
This algorithm implements a randomized greedy heuristic of Berger
and Shor for cycle removal. It, too, is not really compared to
the other heuristics and only included for demonstration purposes.
"]],
documentation = [["
See section 4.1.1 of Pohlmann's Diploma theses for details.
"]]
}
|