diff options
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua')
-rw-r--r-- | graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua | 136 |
1 files changed, 136 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua new file mode 100644 index 0000000000..18670df14e --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/layered/cycle_removal.lua @@ -0,0 +1,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. + "]] + }
\ No newline at end of file |