summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/force/ControlCoarsening.lua
blob: 17cd121b85ec4c7693e8bcfeabc3218cc9682a54 (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
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$


-- 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 } };
  "]]
}