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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/layout.R
\name{layout_with_dh}
\alias{layout_with_dh}
\alias{with_dh}
\title{The Davidson-Harel layout algorithm}
\usage{
layout_with_dh(
graph,
coords = NULL,
maxiter = 10,
fineiter = max(10, log2(vcount(graph))),
cool.fact = 0.75,
weight.node.dist = 1,
weight.border = 0,
weight.edge.lengths = edge_density(graph)/10,
weight.edge.crossings = 1 - sqrt(edge_density(graph)),
weight.node.edge.dist = 0.2 * (1 - edge_density(graph))
)
with_dh(...)
}
\arguments{
\item{graph}{The graph to lay out. Edge directions are ignored.}
\item{coords}{Optional starting positions for the vertices. If this argument
is not \code{NULL} then it should be an appropriate matrix of starting
coordinates.}
\item{maxiter}{Number of iterations to perform in the first phase.}
\item{fineiter}{Number of iterations in the fine tuning phase.}
\item{cool.fact}{Cooling factor.}
\item{weight.node.dist}{Weight for the node-node distances component of the
energy function.}
\item{weight.border}{Weight for the distance from the border component of
the energy function. It can be set to zero, if vertices are allowed to sit
on the border.}
\item{weight.edge.lengths}{Weight for the edge length component of the
energy function.}
\item{weight.edge.crossings}{Weight for the edge crossing component of the
energy function.}
\item{weight.node.edge.dist}{Weight for the node-edge distance component of
the energy function.}
\item{...}{Passed to \code{layout_with_dh()}.}
}
\value{
A two- or three-column matrix, each row giving the coordinates of a
vertex, according to the ids of the vertex ids.
}
\description{
Place vertices of a graph on the plane, according to the simulated annealing
algorithm by Davidson and Harel.
}
\details{
This function implements the algorithm by Davidson and Harel, see Ron
Davidson, David Harel: Drawing Graphs Nicely Using Simulated Annealing. ACM
Transactions on Graphics 15(4), pp. 301-331, 1996.
The algorithm uses simulated annealing and a sophisticated energy function,
which is unfortunately hard to parameterize for different graphs. The
original publication did not disclose any parameter values, and the ones
below were determined by experimentation.
The algorithm consists of two phases, an annealing phase, and a fine-tuning
phase. There is no simulated annealing in the second phase.
Our implementation tries to follow the original publication, as much as
possible. The only major difference is that coordinates are explicitly kept
within the bounds of the rectangle of the layout.
}
\examples{
set.seed(42)
## Figures from the paper
g_1b <- make_star(19, mode = "undirected") + path(c(2:19, 2)) +
path(c(seq(2, 18, by = 2), 2))
plot(g_1b, layout = layout_with_dh)
g_2 <- make_lattice(c(8, 3)) + edges(1, 8, 9, 16, 17, 24)
plot(g_2, layout = layout_with_dh)
g_3 <- make_empty_graph(n = 70)
plot(g_3, layout = layout_with_dh)
g_4 <- make_empty_graph(n = 70, directed = FALSE) + edges(1:70)
plot(g_4, layout = layout_with_dh, vertex.size = 5, vertex.label = NA)
g_5a <- make_ring(24)
plot(g_5a, layout = layout_with_dh, vertex.size = 5, vertex.label = NA)
g_5b <- make_ring(40)
plot(g_5b, layout = layout_with_dh, vertex.size = 5, vertex.label = NA)
g_6 <- make_lattice(c(2, 2, 2))
plot(g_6, layout = layout_with_dh)
g_7 <- graph_from_literal(1:3:5 -- 2:4:6)
plot(g_7, layout = layout_with_dh, vertex.label = V(g_7)$name)
g_8 <- make_ring(5) + make_ring(10) + make_ring(5) +
edges(
1, 6, 2, 8, 3, 10, 4, 12, 5, 14,
7, 16, 9, 17, 11, 18, 13, 19, 15, 20
)
plot(g_8, layout = layout_with_dh, vertex.size = 5, vertex.label = NA)
g_9 <- make_lattice(c(3, 2, 2))
plot(g_9, layout = layout_with_dh, vertex.size = 5, vertex.label = NA)
g_10 <- make_lattice(c(6, 6))
plot(g_10, layout = layout_with_dh, vertex.size = 5, vertex.label = NA)
g_11a <- make_tree(31, 2, mode = "undirected")
plot(g_11a, layout = layout_with_dh, vertex.size = 5, vertex.label = NA)
g_11b <- make_tree(21, 4, mode = "undirected")
plot(g_11b, layout = layout_with_dh, vertex.size = 5, vertex.label = NA)
g_12 <- make_empty_graph(n = 37, directed = FALSE) +
path(1:5, 10, 22, 31, 37:33, 27, 16, 6, 1) + path(6, 7, 11, 9, 10) + path(16:22) +
path(27:31) + path(2, 7, 18, 28, 34) + path(3, 8, 11, 19, 29, 32, 35) +
path(4, 9, 20, 30, 36) + path(1, 7, 12, 14, 19, 24, 26, 30, 37) +
path(5, 9, 13, 15, 19, 23, 25, 28, 33) + path(3, 12, 16, 25, 35, 26, 22, 13, 3)
plot(g_12, layout = layout_with_dh, vertex.size = 5, vertex.label = NA)
}
\references{
Ron Davidson, David Harel: Drawing Graphs Nicely Using Simulated
Annealing. \emph{ACM Transactions on Graphics} 15(4), pp. 301-331, 1996.
}
\seealso{
\code{\link[=layout_with_fr]{layout_with_fr()}},
\code{\link[=layout_with_kk]{layout_with_kk()}} for other layout algorithms.
Other graph layouts:
\code{\link{add_layout_}()},
\code{\link{component_wise}()},
\code{\link{layout_}()},
\code{\link{layout_as_bipartite}()},
\code{\link{layout_as_star}()},
\code{\link{layout_as_tree}()},
\code{\link{layout_in_circle}()},
\code{\link{layout_nicely}()},
\code{\link{layout_on_grid}()},
\code{\link{layout_on_sphere}()},
\code{\link{layout_randomly}()},
\code{\link{layout_with_fr}()},
\code{\link{layout_with_gem}()},
\code{\link{layout_with_graphopt}()},
\code{\link{layout_with_kk}()},
\code{\link{layout_with_lgl}()},
\code{\link{layout_with_mds}()},
\code{\link{layout_with_sugiyama}()},
\code{\link{merge_coords}()},
\code{\link{norm_coords}()},
\code{\link{normalize}()}
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\concept{graph layouts}
|
