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