summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2014-02-27 00:01:50 +0000
committerKarl Berry <karl@freefriends.org>2014-02-27 00:01:50 +0000
commit90ae413a94da014dbf7a6a8ab584f7c668483a5a (patch)
tree4e0528a2b2fb2004988e7fc804ea2f1354f1f5d5 /Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua
parent800cc56380d1edfe567a6a66bef13e8950eb2b0c (diff)
pgf 3.0.0
git-svn-id: svn://tug.org/texlive/trunk@33057 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua148
1 files changed, 148 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua
new file mode 100644
index 00000000000..330f401d5b5
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua
@@ -0,0 +1,148 @@
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed an/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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua,v 1.3 2013/05/23 20:01:27 tantau Exp $
+
+
+-- Imports
+local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
+
+
+
+---
+-- @section subsubsection {Coarsening}
+--
+-- @end
+
+
+---
+
+declare {
+ key = "coarsen",
+ type = "boolean",
+ initial = "true",
+
+ summary = [["
+ Defines whether or not a multilevel approach is used that
+ iteratively coarsens the input graph into graphs $G_1,\dots,G_l$
+ with a smaller and smaller number of nodes. The coarsening stops as
+ soon as a minimum number of nodes is reached, as set via the
+ |minimum coarsening size| option, or if, in the last iteration, the
+ number of nodes was not reduced by at least the ratio specified via
+ |downsize ratio|.
+ "]],
+ documentation = [["
+ A random initial layout is computed for the coarsest graph $G_l$ first.
+ Afterwards, it is laid out by computing the attractive and repulsive
+ forces between its nodes.
+
+ In the subsequent steps, the previous coarse graph $G_{l-1}$ is
+ restored and its node positions are interpolated from the nodes
+ in~$G_l$. The graph $G_{l-1}$ is again laid out by computing the forces
+ between its nodes. These steps are repeated with $G_{l-2},\dots,G_1$ until
+ the original input graph $G_0$ has been restored, interpolated
+ and laid out.
+
+ The idea behind this approach is that, by arranging recursively
+ formed supernodes first and then interpolating and arranging their
+ subnodes step by step, the algorithm is less likely to settle in a
+ local energy minimum (of which there can be many, particularly for
+ large graphs). The quality of the drawings with coarsening enabled is
+ expected to be higher than graphics where this feature is not applied.
+
+ The following example demonstrates how coarsening can improve the
+ quality of graph drawings generated with Walshaw's algorihtm
+ |spring electrical layout'|.
+ "]],
+ examples = [["
+ \tikz \graph [spring electrical layout', coarsen=false, vertical=3 to 4]
+ {
+ { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 }
+ };
+
+ \tikz \graph [spring electrical layout', coarsen, vertical=3 to 4]
+ {
+ { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 }
+ };
+ "]]
+}
+
+---
+
+declare {
+ key = "minimum coarsening size",
+ type = "number",
+ initial = 2,
+
+ summary = [["
+ Defines the minimum number of nodes down to which the graph is
+ coarsened iteratively. The first graph that has a smaller or equal
+ number of nodes becomes the coarsest graph $G_l$, where $l$ is the
+ number of coarsening steps. The algorithm proceeds with the steps
+ described in the documentation of the |coarsen| option.
+ "]],
+ documentation = [["
+ In the following example the same graph is coarsened down to two
+ and four nodes, respectively. The layout of the original graph is
+ interpolated from the random initial layout and is not improved
+ further because the forces are not computed (0 iterations). Thus,
+ in the two graphs, the nodes are placed at exactly two and four
+ coordinates in the final drawing.
+ "]],
+ examples = [["
+ \tikz \graph [spring layout, iterations=0,
+ minimum coarsening size=2]
+ { subgraph C_n [n=8] };
+
+ \tikz \graph [spring layout, iterations=0,
+ minimum coarsening size=4]
+ { subgraph C_n [n=8] };
+ "]]
+}
+
+---
+
+declare {
+ key = "downsize ratio",
+ type = "number",
+ initial = "0.25",
+
+ summary = [["
+ Minimum ratio between 0 and 1 by which the number of nodes between
+ two coarse graphs $G_i$ and $G_{i+1}$ need to be reduced in order for
+ the coarsening to stop and for the algorithm to use $G_{i+1}$ as the
+ coarsest graph $G_l$. Aside from the input graph, the optimal value
+ of |downsize ratio| mostly depends on the coarsening scheme being
+ used. Possible schemes are |collapse independent edges| and
+ |connect independent nodes|.
+ "]],
+ documentation = [["
+ Increasing this option possibly reduces the number of coarse
+ graphs computed during the coarsening phase as coarsening will stop as
+ soon as a coarse graph does not reduce the number of nodes
+ substantially. This may speed up the algorithm but if the size of the
+ coarsest graph $G_l$ is much larger than |minimum coarsening size|, the
+ multilevel approach may not produce drawings as good as with a lower
+ |downsize ratio|.
+ "]],
+ examples = [["
+ % 1. ratio too high, coarsening stops early, benefits are lost
+ \tikz \graph [spring electrical layout',
+ downsize ratio=1.0,
+ node distance=7mm, vertical=3 to 4]
+ { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } };
+
+ % 2. ratio set to default, coarsening benefits are visible
+ \tikz \graph [spring electrical layout',
+ downsize ratio=0.2,
+ node distance=7mm, vertical=3 to 4]
+ { { [clique] 1, 2 } -- 3 -- 4 -- { 5, 6, 7 } };
+ "]]
+}
+