summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua111
1 files changed, 57 insertions, 54 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua
index 18670df14e8..63c43f5b14f 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua
@@ -34,38 +34,39 @@ declare {
phase = "cycle removal",
phase_default = true,
- summary = [["
- Selects a cycle removal algorithm that is especially
- appropriate for graphs specified ``by hand''.
+ 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.
- "]]
+ 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.
+ "]]
}
---
@@ -75,12 +76,12 @@ declare {
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.
+ 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.
+ documentation = [["
+ See section 4.1.1 of Pohlmann's Diploma theses for details.
"]]
}
@@ -92,12 +93,12 @@ declare {
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.
+ 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.
+ documentation = [["
+ See section 4.1.1 of Pohlmann's Diploma theses for details.
"]]
}
@@ -108,13 +109,14 @@ declare {
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.
+ 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.
+ documentation = [["
+ See section 4.1.1 of Pohlmann's Diploma theses for details.
"]]
}
@@ -125,12 +127,13 @@ declare {
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.
+ 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.
+ documentation = [["
+ See section 4.1.1 of Pohlmann's Diploma theses for details.
"]]
- } \ No newline at end of file
+ }
+