使用 igraph 和 R 快速找到所有长度为 N 的路径

Question

tl;dr：distances 给了我路径长度，但无法恢复 使用 simple_paths 时这些路径中有哪些节点。

我想在我的网络中找到给定长度的所有最短、简单的路径。我的网络可以比较大（1000个节点，几万条边），由于simple_paths比较慢而distances很快，我想我可以先计算distances作为过滤步骤。

也就是我现在的策略是

计算每对顶点之间的所有简单路径的长度，即dd = distances(my.net)
找到所需长度的路径，即dd[dd == desired.length]
恢复此路径列表中的节点，现在相对较小。

但是，我在第 3 步失败了。也就是说，我无法恢复 distances 给出的路径。 例如，在下面的代码中distances 在节点 D 和 X 之间找到长度为 3 的路径。当我尝试使用 simple_paths 找出该路径实际是什么时，我什么也没得到。 我做错了什么？

require(dplyr)
require(tidyverse)
require(igraph)
set.seed(1)

# make network
fake.net = data.frame(A = sample(LETTERS,50,replace = T),
                      B = sample(LETTERS,50,replace = T),
                      stringsAsFactors = F) %>%
  dplyr::filter(!A==B) %>%
  as.matrix() %>% graph_from_edgelist()

# find one path of length 3
dd = distances(fake.net)
ia = which(dd==3)[1]
v.from = V(fake.net)[ia %% ncol(dd)]
v.to = V(fake.net)[ceiling(ia / ncol(dd))]

# what is that path?
shortest_paths(fake.net, from = v.from, to = v.to)

$vpath
$vpath[[1]]
+ 0/26 vertices, named, from ffb91bb:


$epath
NULL

$predecessors
NULL

$inbound_edges
NULL

Answer 1

我想你需要在which中启用arr.ind，然后尝试下面的代码（如果你的图形是有向的，你应该在distances中使用mode = "out" )

dd <- distances(fake.net, mode = "out")
idx <- which(dd == 3, arr.ind = TRUE)
all_simple_paths <- apply(
  matrix(row.names(dd)[idx], ncol = 2),
  1,
  function(v) shortest_paths(fake.net, from = v[1], to = v[2])$vpath
)

你将获得

> head(all_simple_paths)
[[1]]
[[1]][[1]]
+ 4/26 vertices, named, from 84fcc54:
[1] G A Y D


[[2]]
[[2]][[1]]
+ 4/26 vertices, named, from 84fcc54:
[1] L A Y D


[[3]]
[[3]][[1]]
+ 4/26 vertices, named, from 84fcc54:
[1] G A F W


[[4]]
[[4]][[1]]
+ 4/26 vertices, named, from 84fcc54:
[1] U H I W


[[5]]
[[5]][[1]]
+ 4/26 vertices, named, from 84fcc54:
[1] O H I W


[[6]]
[[6]][[1]]
+ 4/26 vertices, named, from 84fcc54:
[1] L A F W

使用 igraph 和 R 快速找到所有长度为 N 的路径

Quickly find all paths of length N using igraph and R

r

graph

igraph