Shortest Path calculations crashes with igraph r - maximum number of nodes?

Question

Is there a maximum number of nodes for the igraph::shortest.paths function?

The following code crashes Microsoft R Open 4.0.2 in RStudio Version 1.4.1106 under Windows 10 with 128GB RAM.

Questions:

• Is this because of the functionality of igraph

• Does this have to do with the local RAM?

• What are alternatives? Perhaps using the cppRouting package?

    library(igraph)
    c1 <- sample(1:48000, 293631, replace=TRUE)
    c2 <- sample(1:48000, 293631, replace=TRUE)
  
    # column bind the two vectors
    el <- cbind(c1, c2)
  
    # convert matrix as an edgelist into an undirected graph 
    g <- graph.edgelist(el, directed=FALSE)
  
    # obtain distance matrix with shortest path between all pairs of nodes
    t <- shortest.paths(g)
  

Answer 1

At this moment, igraph does not have robust checks in place for exceeding maximum data structure sizes. However, as a guideline, you can assume that anything that cannot be indexed with signed 32-bit integers will not work. This is the case for the matrix that your computation would return:

> log2(48000^2)
[1] 31.10149

When exceeding these sizes, problems such as crashes are especially likely on Windows, where the size of the long int type (currently used extensively by igraph internals) is 32 bits, even on 64-bit systems.

---

There is ongoing work to make the C core of igraph fully 64-bit ready and let it detect when maximum data structure sizes are exceeded. Unfortunately, it is unclear how or whether 64-bit support can be brought to igraph's R interface because R itself still does not support 64-bit integers. However, future versions should show an error instead of crashing when sizes are exceeded.

Answer 2

It seems that the library cppRouting can handle bigger networks than igraph does on my Windows system.

library(cppRouting)
gr <-makegraph(cbind(el, 1),directed=FALSE) # add one to indicate tie-strength
outcome <- get_distance_pair(gr)

This will get you the shortest paths between the nodes in the edgelist el.