使用 igraph 高效提取 duplicate/multiple 路径

Question

如何从 igraph 中提取重复路径？是否有比下面示例中的双循环更有效的方法？ duplicate/multiple 路径是指结果应同时包含 B1 -> B2a -> B3 和 B1 -> B2b -> B3。但是我的代码不会产生那个。数据：

library(dplyr)
library(igraph)

d <- tribble(~input, ~output,
             "A1", "A2",
             "A2", "A3a",
             "A2", "A3b",
             "B1", "B2a",
             "B1", "B2b",
             "B2a", "B3",
             "B2b", "B3")

我的分析：

g <- graph_from_data_frame(d, directed = TRUE)
(finals <- V(g)[degree(g, mode = "out") == 0])
(starts <- V(g)[degree(g, mode = "in") == 0])
res_collect <- vector("list", length(starts) * length(finals))
tmp <- 1
for (i_s in seq_along(starts)) {
  for (i_f in seq_along(finals)) {
    res <- tryCatch(
      {
        all_simple_paths(g, from = starts[[i_s]], to = finals[[i_f]])[[1]]
      },
      error = function(cond) {
        message("failed at starts-nr=", i_s, ", finals-nr=", i_f); return(as.integer(NA))
      }
    )
    res_collect[[tmp]] <- res
    tmp <- tmp + 1
  }
}

问题：

res_collect[!is.na(res_collect)]
# [[1]]
# + 3/8 vertices, named, from 60df173:
#   [1] A1  A2  A3a
# 
# [[2]]
# + 3/8 vertices, named, from 60df173:
#   [1] A1  A2  A3b
# 
# [[3]]
# + 3/8 vertices, named, from 60df173:
#   [1] B1  B2a B3

缺少 1 个路径：B1 -> B2b -> B3。

Answer 1

您可以试试下面的代码

do.call(
  c,
  lapply(
    starts,
    all_simple_paths,
    graph = g,
    to = finals
  )
)

这给出了

[[1]]
+ 3/4 vertices, named, from fb6335c:
[1] A1  A2  A3a

[[2]]
+ 3/4 vertices, named, from fb6335c:
[1] A1  A2  A3b

[[3]]
+ 3/4 vertices, named, from fb6335c:
[1] B1  B2a B3

[[4]]
+ 3/4 vertices, named, from fb6335c:
[1] B1  B2b B3

使用 igraph 高效提取 duplicate/multiple 路径

Efficiently extract duplicate/multiple paths with igraph

r

igraph