R Igraph Route Performance

igraph071.txt

> for(i in c(1,10,25,50, 100)){ print(system.time(x <- do_work(300, i, 50)))}
   user  system elapsed 
   0.03    0.02    0.08 
   user  system elapsed 
   0.03    0.02    0.05 
   user  system elapsed 
   0.04    0.00    0.06 
   user  system elapsed 
   0.03    0.00    0.05 
   user  system elapsed 
   0.05    0.02    0.06 
   
   
Package: igraph
Version: 0.7.1
Date: 2014-04-22
Title: Network analysis and visualization
Author: See AUTHORS file.
Maintainer: Gabor Csardi <[email protected]>
Description: Routines for simple graphs and network analysis. igraph can handle large
          graphs very well and provides functions for generating random and regular
          graphs, graph visualization, centrality indices and much more.
Depends: methods
Imports: Matrix
Suggests: igraphdata, stats4, rgl, tcltk, graph, ape
License: GPL (>= 2)
URL: http://igraph.org
SystemRequirements: gmp, libxml2
BugReports: https://github.com/igraph/igraph/issues
Packaged: 2014-04-22 21:51:12 UTC; jenkins
Built: R 3.1.0; i386-w64-mingw32; 2014-04-22 21:51:38 UTC; windows

igraph101.txt

for(i in c(1,10,25,50, 100)){ print(system.time(x <- do_work(300, i, 50)))}
   user  system elapsed 
   0.09    0.02    0.24 
   user  system elapsed 
   0.66    0.14    1.34 
   user  system elapsed 
   1.36    0.59    2.85 
   user  system elapsed 
   3.27    1.02    6.28 
   user  system elapsed 
   5.94    1.98    8.70 
   
   Package: igraph
Version: 1.0.1
Title: Network Analysis and Visualization
Author: See AUTHORS file.
Maintainer: Gabor Csardi <[email protected]>
Description: Routines for simple graphs and network analysis. It can handle large graphs
          very well and provides functions for generating random and regular graphs,
          graph visualization, centrality methods and much more.
Depends: methods
Imports: Matrix, magrittr, NMF, irlba
Suggests: igraphdata, stats4, rgl, tcltk, graph, ape, scales
License: GPL (>= 2)
URL: http://igraph.org
SystemRequirements: gmp, libxml2
BugReports: https://github.com/igraph/igraph/issues
Collate: 'adjacency.R' 'auto.R' 'assortativity.R' 'attributes.R' 'basic.R' 'bipartite.R'
          .....
NeedsCompilation: yes
Packaged: 2015-06-26 01:04:44 UTC; gaborcsardi
Repository: CRAN
Date/Publication: 2015-06-26 11:13:24
Built: R 3.3.0; i386-w64-mingw32; 2016-04-15 21:20:42 UTC; windows

runBench.R

for(i in c(1,10,25,50, 100)){ 
  print(system.time(x <- do_work(300, i, 50)))
}

packageDescription('igraph')

shortestPathBenchmark.R

library('igraph')

# create randomly weighted graph of n nodes
random_graph = function(n){
  a <- matrix(runif(n*n, min=0, max=10), ncol=n)
  diag(a) <- 0
  g <- graph.adjacency(a, mode='directed', weighted = TRUE)
  return(g)
}

# repeatedly get shortest paths
# graph_size:    nodes in the graph
# to_count:      how many destinations to route
# repeat_count:  repeat the calculation for timing
do_work = function(graph_size, to_count, repeat_count){
  set.seed(12345)
  g = random_graph(graph_size)
  toNodes = sample(1:graph_size, to_count)
  for(i in 1:repeat_count){
    get.shortest.paths(g, from = 1, to = toNodes, weights = NA, output = 'both', mode='in')
  }
}