r - 使用 igraph 和 R 快速找到所有长度为 N 的路径
问题描述
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
解决方案
我猜你需要启用arr.ind
in which
,然后尝试下面的代码(如果你的图表是定向的,你应该使用mode = "out"
in distances
)
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
推荐阅读
- javascript - 循环遍历计算属性 Vue
- android - 第一次没有得到服务器 android volley 的响应
- excel - 当 A 列(帐户代码)相同时,求和 B 列(借方)[Excel]
- java - HttpsURLConnection 的默认请求方法
- vue.js - Vue.js 与 v-model 的双向数据绑定
- java - 改进不同类型的 Iterable 的类型检查
- jquery - ASP.NET Core MVC 引导模式 - 改变内容
- javascript - 在 jquery 中停止其他网络请求
- android - 单个命令可在一个视频中裁剪、动画(效果)和添加图像和文本
- search - 输入搜索关键字后使用drupal搜索获取包含在taxonmoy中的节点数