Find All Shortest Paths using igraph/R

Question

First off I am not very proficient with R, but I have a network of 100 nodes I'm doing analysis on. I'm looking to find all the shortest paths between every single pair of nodes in the network (100 calculations), and the trick is to return them as integers, path lengths if you will.

#construct a small sample of the graph
g = graph.formula('insert graph') 

#use the function to retrieve shortest paths from a single vertex
get.all.shortest.paths(g, 1, to = V(g))

#output
$res
$res[[1]]
[1] 1

$res[[2]]
[1] 1 2

$res[[3]]
[1] 1 2 3

$res[[4]]
[1] 1 2 3 4

$res[[5]]
[1] 1 2 3 4 5

$res[[6]]
[1]  1 10  9  8  7  6

$res[[7]]
[1] 1 2 3 4 5 6

$res[[8]]
[1]  1 10  9  8  7

$res[[9]]
[1]  1 10  9  8

$res[[10]]
[1]  1 10  9

$res[[11]]
[1]  1 10


$nrgeo
 [1] 1 1 1 1 1 2 1 1 1 1

While this is good it is not practical to manually iterate for all 100 nodes. Is there a way of automating this? A second component to my question is that I wish to output each path as a number, like a path length, instead of being given the actual path. Another thing I want is to calculate the mode path length (or the path length that is more frequently found in the network). Looking at 100 numbers is not feasible so it must be automated.

Any help would be thoroughly appreciated, this might seem like a novice question, I am somewhat of a novice user.

digEmAll digEmAll · Accepted Answer · 2013-11-15T08:57:46

You could use shortest.paths that returns the matrix of the distances between each node:

distMatrix <- shortest.paths(g, v=V(g), to=V(g))

Result:

      cdc42 ste20 mkk2 bul1 mth1 vma6 vma2  ... 
cdc42     0     1  Inf  Inf    4    3    2  
ste20     1     0  Inf  Inf    3    2    1  
mkk2    Inf   Inf    0    1  Inf  Inf  Inf  
bul1    Inf   Inf    1    0  Inf  Inf  Inf  
mth1      4     3  Inf  Inf    0    1    2  
vma6      3     2  Inf  Inf    1    0    1
vma2      2     1  Inf  Inf    2    1    0  
...

And it's very easy to access it:

# e.g. shortest path length between the second node and the fifth
distMatrix[2,5]
>
[1] 3

# or using node names:
distMatrix["ste20", "mth1"]
>
[1] 3

Find All Shortest Paths using igraph/R

2 Answers