'Shortest Path calculations crashes with igraph r - maximum number of nodes?
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)
Solution 1:[1]
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
.
Solution 2:[2]
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.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|---|
Solution 1 | wake_wake |
Solution 2 | Szabolcs |