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
140
141
142
143
144
145
146
147
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 } };
"]]
}
|