使用来自不同来源的 R igraph all_simple_paths 并构建 Origin Destination Step by Step 路径

Question

我有一个连接如下的网络：

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

并且我希望找到每个起点-目的地对的最短路径：

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

我试过用这个：

short <- all_simple_paths(network , data$Origin ,data$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

另外，对于每个结果，我想在“km”列中添加相应的长度：

还有第二列，其中包含路径的每一步。

最后的结果一定是这样的：

我厌倦了使用

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)

但我不知道如何让它发挥作用

提前致谢！

Answer 1

你可以这样

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

这给出了

[[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

最后的效果，你可以试试

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]
            )
          }
        )
      )
    }
  )
)

这给出了

   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

使用来自不同来源的 R igraph all_simple_paths 并构建 Origin Destination Step by Step 路径

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

r

igraph