Using R igraph all_simple_paths from various origins and constructing Origin Destination Step by Step path

Question

I have a network that is coneccted like the following:

library(igraph)
network <- graph_from_literal(1--2,2--3,3--4,4--5,3--6,6--7,3--8,8--9)

and I want fo find the shortes path for each Origin-Destination pair:

data=data.frame(Origin=c(1,8,9,2), Destination=c(4,5,6,9), km=c(22,32,43,52))
  Origin Destination km
1      1           4 22
2      8           5 32
3      9           6 43
4      2           9 52

I tried using this:

short <- all_simple_paths(network , data$Origin ,data$Destination)

But I receive only values from the first Origin to all destination.

[[1]]
+ 4/9 vertices, named, from 7186e74:
[1] 1 2 3 4

[[2]]
+ 5/9 vertices, named, from 7186e74:
[1] 1 2 3 4 5

[[3]]
+ 4/9 vertices, named, from 7186e74:
[1] 1 2 3 6

[[4]]
+ 5/9 vertices, named, from 7186e74:
[1] 1 2 3 8 9

Also for each result I would like to add the corresponding length in the column "km":

as well a second column with the every step of the path as well.

At the end the result must look like something like this:

O D Km
1 2 22
2 3 22
3 4 22 
4 - 22
8 3 32
3 4 32
4 5 32
5 - 32
9 8 43
8 3 43
3 6 43
6 - 43
2 3 52
3 8 52
8 9 52
9 - 52

I tired using

b <-data.frame(unlist(short),unlist(short)) 
names(b)[1] <- "O"
names(b)[2] <- "D"

shift <- function(x, n){
  c(x[-(seq(n))], rep(NA, n))
}

b$D <- shift(b$D,1)

but I can't figure out how to make it work

Thanks in advance!

Answer 1

You can to it like this

asp <- with(
  data,
  Map(all_simple_paths, list(network), Origin, Destination)
)

which gives

[[1]]
[[1]][[1]]
+ 4/9 vertices, named, from b510974:
[1] 1 2 3 4


[[2]]
[[2]][[1]]
+ 4/9 vertices, named, from b510974:
[1] 8 3 4 5


[[3]]
[[3]][[1]]
+ 4/9 vertices, named, from b510974:
[1] 9 8 3 6


[[4]]
[[4]][[1]]
+ 4/9 vertices, named, from b510974:
[1] 2 3 8 9

---

For the final result, you can try

do.call(
  rbind,
  lapply(
    seq_along(asp),
    function(k) {
      plst <- asp[[k]]
      do.call(
        rbind,
        lapply(
          plst,
          function(p) {
            vnm <- names(p)
            data.frame(
              O = vnm,
              D = c(tail(vnm, -1), NA),
              Km = data$km[k]
            )
          }
        )
      )
    }
  )
)

which gives

   O    D Km
1  1    2 22
2  2    3 22
3  3    4 22
4  4 <NA> 22
5  8    3 32
6  3    4 32
7  4    5 32
8  5 <NA> 32
9  9    8 43
10 8    3 43
11 3    6 43
12 6 <NA> 43
13 2    3 52
14 3    8 52
15 8    9 52
16 9 <NA> 52