1
2#' The DrL graph layout generator
3#'
4#' DrL is a force-directed graph layout toolbox focused on real-world
5#' large-scale graphs, developed by Shawn Martin and colleagues at Sandia
6#' National Laboratories.
7#'
8#' This function implements the force-directed DrL layout generator.
9#'
10#' The generator has the following parameters: \describe{ \item{edge.cut}{Edge
11#' cutting is done in the late stages of the algorithm in order to achieve less
12#' dense layouts.  Edges are cut if there is a lot of stress on them (a large
13#' value in the objective function sum). The edge cutting parameter is a value
14#' between 0 and 1 with 0 representing no edge cutting and 1 representing
15#' maximal edge cutting. } \item{init.iterations}{Number of iterations in the
16#' first phase.} \item{init.temperature}{Start temperature, first phase.}
17#' \item{init.attraction}{Attraction, first phase.}
18#' \item{init.damping.mult}{Damping, first phase.}
19#' \item{liquid.iterations}{Number of iterations, liquid phase.}
20#' \item{liquid.temperature}{Start temperature, liquid phase.}
21#' \item{liquid.attraction}{Attraction, liquid phase.}
22#' \item{liquid.damping.mult}{Damping, liquid phase.}
23#' \item{expansion.iterations}{Number of iterations, expansion phase.}
24#' \item{expansion.temperature}{Start temperature, expansion phase.}
25#' \item{expansion.attraction}{Attraction, expansion phase.}
26#' \item{expansion.damping.mult}{Damping, expansion phase.}
27#' \item{cooldown.iterations}{Number of iterations, cooldown phase.}
28#' \item{cooldown.temperature}{Start temperature, cooldown phase.}
29#' \item{cooldown.attraction}{Attraction, cooldown phase.}
30#' \item{cooldown.damping.mult}{Damping, cooldown phase.}
31#' \item{crunch.iterations}{Number of iterations, crunch phase.}
32#' \item{crunch.temperature}{Start temperature, crunch phase.}
33#' \item{crunch.attraction}{Attraction, crunch phase.}
34#' \item{crunch.damping.mult}{Damping, crunch phase.}
35#' \item{simmer.iterations}{Number of iterations, simmer phase.}
36#' \item{simmer.temperature}{Start temperature, simmer phase.}
37#' \item{simmer.attraction}{Attraction, simmer phase.}
38#' \item{simmer.damping.mult}{Damping, simmer phase.}
39#'
40#' There are five pre-defined parameter settings as well, these are called
41#' \code{drl_defaults$default}, \code{drl_defaults$coarsen},
42#' \code{drl_defaults$coarsest}, \code{drl_defaults$refine} and
43#' \code{drl_defaults$final}.  }
44#'
45#' @aliases layout.drl drl_defaults igraph.drl.coarsen
46#'  igraph.drl.coarsest igraph.drl.default igraph.drl.final
47#'  igraph.drl.refine
48#' @param graph The input graph, in can be directed or undirected.
49#' @param use.seed Logical scalar, whether to use the coordinates given in the
50#' \code{seed} argument as a starting point.
51#' @param seed A matrix with two columns, the starting coordinates for the
52#' vertices is \code{use.seed} is \code{TRUE}. It is ignored otherwise.
53#' @param options Options for the layout generator, a named list. See details
54#' below.
55#' @param weights Optional edge weights. Supply \code{NULL} here if you want to
56#' weight edges equally. By default the \code{weight} edge attribute is used if
57#' the graph has one. Larger weights correspond to stronger connections,
58#' and the vertices will be placed closer to each other.
59#' @param fixed Logical vector, it can be used to fix some vertices. All
60#' vertices for which it is \code{TRUE} are kept at the coordinates supplied in
61#' the \code{seed} matrix. It is ignored it \code{NULL} or if \code{use.seed}
62#' is \code{FALSE}.
63#' @param dim Either \sQuote{2} or \sQuote{3}, it specifies whether we want a
64#' two dimensional or a three dimensional layout. Note that because of the
65#' nature of the DrL algorithm, the three dimensional layout takes
66#' significantly longer to compute.
67#' @return A numeric matrix with two columns.
68#' @author Shawn Martin (\url{http://www.cs.otago.ac.nz/homepages/smartin/})
69#' and Gabor Csardi \email{csardi.gabor@@gmail.com} for the R/igraph interface
70#' and the three dimensional version.
71#' @seealso \code{\link{layout}} for other layout generators.
72#' @references See the following technical report: Martin, S., Brown, W.M.,
73#' Klavans, R., Boyack, K.W., DrL: Distributed Recursive (Graph) Layout. SAND
74#' Reports, 2008. 2936: p. 1-10.
75#' @export
76#' @importFrom stats runif
77#' @keywords graphs
78#' @examples
79#'
80#' g <- as.undirected(sample_pa(100, m=1))
81#' l <- layout_with_drl(g, options=list(simmer.attraction=0))
82#' \dontrun{
83#' plot(g, layout=l, vertex.size=3, vertex.label=NA)
84#' }
85#'
86layout_with_drl <- function(graph, use.seed = FALSE,
87                       seed=matrix(runif(vcount(graph)*2), ncol=2),
88                       options=drl_defaults$default,
89                       weights=E(graph)$weight,
90                       fixed=NULL,
91                       dim=2)
92{
93    if (!is_igraph(graph)) {
94        stop("Not a graph object")
95    }
96    if (dim != 2 && dim != 3) {
97      stop("`dim' must be 2 or 3")
98    }
99    use.seed <- as.logical(use.seed)
100    seed <- as.matrix(seed)
101    options.tmp <- drl_defaults$default
102    options.tmp[names(options)] <- options
103    options <- options.tmp
104    if (!is.null(weights)) {
105      weights <- as.numeric(weights)
106    }
107    if (!is.null(fixed)) {
108      fixed <- as.logical(fixed)
109    }
110    on.exit(.Call(C_R_igraph_finalizer))
111    if (dim==2) {
112      res <- .Call(C_R_igraph_layout_drl, graph, seed, use.seed, options,
113                   weights, fixed)
114    } else {
115      res <- .Call(C_R_igraph_layout_drl_3d, graph, seed, use.seed, options,
116                   weights, fixed)
117    }
118    res
119}
120
121
122#' @rdname layout_with_drl
123#' @param ... Passed to \code{layout_with_drl}.
124#' @export
125
126with_drl <- function(...) layout_spec(layout_with_drl, ...)
127
128
129#' @export
130
131igraph.drl.default <- list(edge.cut=32/40,
132                           init.iterations=0,
133                           init.temperature=2000,
134                           init.attraction=10,
135                           init.damping.mult=1.0,
136                           liquid.iterations=200,
137                           liquid.temperature=2000,
138                           liquid.attraction=10,
139                           liquid.damping.mult=1.0,
140                           expansion.iterations=200,
141                           expansion.temperature=2000,
142                           expansion.attraction=2,
143                           expansion.damping.mult=1.0,
144                           cooldown.iterations=200,
145                           cooldown.temperature=2000,
146                           cooldown.attraction=1,
147                           cooldown.damping.mult=.1,
148                           crunch.iterations=50,
149                           crunch.temperature=250,
150                           crunch.attraction=1,
151                           crunch.damping.mult=0.25,
152                           simmer.iterations=100,
153                           simmer.temperature=250,
154                           simmer.attraction=.5,
155                           simmer.damping.mult=0)
156
157#' @export
158
159igraph.drl.coarsen <- list(edge.cut=32/40,
160                           init.iterations=0,
161                           init.temperature=2000,
162                           init.attraction=10,
163                           init.damping.mult=1.0,
164                           liquid.iterations=200,
165                           liquid.temperature=2000,
166                           liquid.attraction=2,
167                           liquid.damping.mult=1.0,
168                           expansion.iterations=200,
169                           expansion.temperature=2000,
170                           expansion.attraction=10,
171                           expansion.damping.mult=1.0,
172                           cooldown.iterations=200,
173                           cooldown.temperature=2000,
174                           cooldown.attraction=1,
175                           cooldown.damping.mult=.1,
176                           crunch.iterations=50,
177                           crunch.temperature=250,
178                           crunch.attraction=1,
179                           crunch.damping.mult=0.25,
180                           simmer.iterations=100,
181                           simmer.temperature=250,
182                           simmer.attraction=.5,
183                           simmer.damping.mult=0)
184
185#' @export
186
187igraph.drl.coarsest <- list(edge.cut=32/40,
188                            init.iterations=0,
189                            init.temperature=2000,
190                            init.attraction=10,
191                            init.damping.mult=1.0,
192                            liquid.iterations=200,
193                            liquid.temperature=2000,
194                            liquid.attraction=2,
195                            liquid.damping.mult=1.0,
196                            expansion.iterations=200,
197                            expansion.temperature=2000,
198                            expansion.attraction=10,
199                            expansion.damping.mult=1.0,
200                            cooldown.iterations=200,
201                            cooldown.temperature=2000,
202                            cooldown.attraction=1,
203                            cooldown.damping.mult=.1,
204                            crunch.iterations=200,
205                            crunch.temperature=250,
206                            crunch.attraction=1,
207                            crunch.damping.mult=0.25,
208                            simmer.iterations=100,
209                            simmer.temperature=250,
210                            simmer.attraction=.5,
211                            simmer.damping.mult=0)
212
213#' @export
214
215igraph.drl.refine <- list(edge.cut=32/40,
216                          init.iterations=0,
217                          init.temperature=50,
218                          init.attraction=.5,
219                          init.damping.mult=1.0,
220                          liquid.iterations=0,
221                          liquid.temperature=2000,
222                          liquid.attraction=2,
223                          liquid.damping.mult=1.0,
224                          expansion.iterations=50,
225                          expansion.temperature=500,
226                          expansion.attraction=.1,
227                          expansion.damping.mult=.25,
228                          cooldown.iterations=50,
229                          cooldown.temperature=250,
230                          cooldown.attraction=1,
231                          cooldown.damping.mult=.1,
232                          crunch.iterations=50,
233                          crunch.temperature=250,
234                          crunch.attraction=1,
235                          crunch.damping.mult=0.25,
236                          simmer.iterations=0,
237                          simmer.temperature=250,
238                          simmer.attraction=.5,
239                          simmer.damping.mult=0)
240
241#' @export
242
243igraph.drl.final <- list(edge.cut=32/40,
244                         init.iterations=0,
245                         init.temperature=50,
246                         init.attraction=.5,
247                         init.damping.mult=0,
248                         liquid.iterations=0,
249                         liquid.temperature=2000,
250                         liquid.attraction=2,
251                         liquid.damping.mult=1.0,
252                         expansion.iterations=50,
253                         expansion.temperature=2000,
254                         expansion.attraction=2,
255                         expansion.damping.mult=1.0,
256                         cooldown.iterations=50,
257                         cooldown.temperature=200,
258                         cooldown.attraction=1,
259                         cooldown.damping.mult=.1,
260                         crunch.iterations=50,
261                         crunch.temperature=250,
262                         crunch.attraction=1,
263                         crunch.damping.mult=0.25,
264                         simmer.iterations=25,
265                         simmer.temperature=250,
266                         simmer.attraction=.5,
267                         simmer.damping.mult=0)
268
269#' @export
270
271drl_defaults <- list(
272  coarsen = igraph.drl.coarsen,
273  coarsest = igraph.drl.coarsest,
274  default = igraph.drl.default,
275  final = igraph.drl.final,
276  refine = igraph.drl.refine
277)
278