使用tidygraph与igraph获取两节点间所有简单路径对应的边ID列表

完整实现代码 #

library(tidyverse)
library(tidygraph)
library(igraph)

# 示例图构建
demo <- tbl_graph(nodes = tibble(name = c("A", "B", "C", "D")),
                  edges = tribble(~from, ~to,~id,
                                  "B", "A", "1",
                                  "D", "C", "2",
                                  "A", "D", "3",
                                  "A", "C", "4"),
                  node_key = "name")

# 获取B到C的所有简单路径
paths <- all_simple_paths(demo, "B", "C")

# 转换为路径对应的边ID列表
edge_path_list <- lapply(paths, function(path_node) {
  # 提取路径的节点名称序列
  node_vec <- names(path_node)
  # 生成路径上所有边对应的<起点,终点>对
  edge_pair <- cbind(from = head(node_vec, -1), to = tail(node_vec, -1))
  # 匹配每对节点对应的边ID，转为数值型和期望输出一致
  apply(edge_pair, 1, function(pair) {
    as.numeric(E(demo)$id[get.edge.ids(demo, vp = pair)])
  })
})

# 输出结果
edge_path_list

输出结果 #

运行上述代码后得到的输出和期望完全一致：

[[1]]
[1] 1 4

[[2]]
[1] 1 3 2

实现逻辑说明 #

• 先从all_simple_paths返回的顶点序列对象中提取节点名称向量
• 滑动取相邻节点生成<起点,终点>对，对应路径上的每一条有向边
• 调用igraph内置的get.edge.ids函数快速匹配节点对对应的边索引，取出边的id属性即可

如果你处理的是无向图，只需要在get.edge.ids参数中添加directed = FALSE即可。

内容的提问来源于stack exchange，提问作者Qzhao