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