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