从 igraph all_simple_paths 中检索路径名列表

Question

我有一个有向循环矩阵，需要提取任意 i 和 j 之间的所有简单路径。

以下是我的前任。矩阵：

>M2<-matrix(c(1,1,0,0,0,1,1,1,1,0,0,1,1,1,0,0,1,0,1,1,0,0,0,1,1), 5, byrow=T)
>colnames(M2)<-c("A", "B", "C", "D", "E")
>row.names(M2)=colnames(M2)
>M2
  A B C D E
A 1 1 0 0 0
B 1 1 1 1 0
C 0 1 1 1 0
D 0 1 0 1 1
E 0 0 0 1 1

我使用 igraph 使用 graph_from_adjency_matrix 函数将矩阵转换为图形对象。

>graph<-graph_from_adjacency_matrix(M2, mode=c("directed"), weighted=NULL, diag=F, add.colnames=NULL, add.rownames=NA)
>graph
IGRAPH DN-- 5 9 -- 
+ attr: name (v/c)
+ edges (vertex names):
[1] A->B B->A B->C B->D C->B C->D D->B D->E E->D

然后我使用 all_simple_paths 函数获取 i 和 j 之间的所有简单路径。我的问题从这里开始。

1) 我可以将 j（参数 to 有 to=V(graph)）指定为所有可能的端点。但是我不能指定 from 参数来计算寻找所有顶点的路径都有可能的起点。我必须一次指定我的每个变量。有什么解决办法吗？

2) all_simple_path 函数运行良好并为我提供了 i 和 j 之间的所有简单路径，例如对于从 A 开始并以任何可能的 j:

结束的简单路径

>Simple_path_list<-all_simple_paths(graph, from ="A", to=V(graph), mode = c("out"))
>Simple_path_list
[[1]]
+ 2/5 vertices, named:
[1] A B

[[2]]
+ 3/5 vertices, named:
[1] A B C

[[3]]
+ 4/5 vertices, named:
[1] A B C D

[[4]]
+ 5/5 vertices, named:
[1] A B C D E

[[5]]
+ 3/5 vertices, named:
[1] A B D

[[6]]
+ 4/5 vertices, named:
[1] A B D E

我的问题是，我需要收集所有这些路径并放在一个列表中，例如：

Paths
A B
A B C
A B C D
A B C D E 
A B D
A B D E

我尝试创建一个列表并使用正常的 list<-Simple_path_list[1] 左右调用路径名，但我总是与路径一起检索有关所涉及顶点数量的信息（例如，+ 4/5 vertices, named).关于如何只检索路径名称而不检索其他信息的任何想法？

Answer 1

all_simple_paths 上的 lapply 函数生成一个列表列表（即每个顶点的路径列表的列表）。使用 unlist(..., recursive = F) 将列表列表简化为列表，然后使用 names 或 igraph 的 as_ids 单独提取顶点 ID。

library(igraph)
M2<-matrix(c(1,1,0,0,0,1,1,1,1,0,0,1,1,1,0,0,1,0,1,1,0,0,0,1,1), 5, byrow=T)
colnames(M2)<-c("A", "B", "C", "D", "E")
row.names(M2)=colnames(M2)
M2
graph<-graph_from_adjacency_matrix(M2, mode=c("directed"), weighted=NULL, diag=F, add.colnames=NULL, add.rownames=NA)
l <- unlist(lapply(V(graph) , function(x) all_simple_paths(graph, from=x)), recursive = F)
paths <- lapply(1:length(l), function(x) as_ids(l[[x]]))

这会产生：

> paths
[[1]]
[1] "A" "B"

[[2]]
[1] "A" "B" "C"

[[3]]
[1] "A" "B" "C" "D"

[[4]]
[1] "A" "B" "C" "D" "E"

[[5]]
[1] "A" "B" "D"

[[6]]
[1] "A" "B" "D" "E"

[[7]]
[1] "B" "A"

[[8]]
[1] "B" "C"

[[9]]
[1] "B" "C" "D"

[[10]]
[1] "B" "C" "D" "E"

[[11]]
[1] "B" "D"

[[12]]
[1] "B" "D" "E"

[[13]]
[1] "C" "B"

[[14]]
[1] "C" "B" "A"

[[15]]
[1] "C" "B" "D"

[[16]]
[1] "C" "B" "D" "E"

[[17]]
[1] "C" "D"

[[18]]
[1] "C" "D" "B"

[[19]]
[1] "C" "D" "B" "A"

[[20]]
[1] "C" "D" "E"

[[21]]
[1] "D" "B"

[[22]]
[1] "D" "B" "A"

[[23]]
[1] "D" "B" "C"

[[24]]
[1] "D" "E"

[[25]]
[1] "E" "D"

[[26]]
[1] "E" "D" "B"

[[27]]
[1] "E" "D" "B" "A"

[[28]]
[1] "E" "D" "B" "C"

加法

对于all_shortest_paths，您必须对每个节点的路径列表进行子集化，以排除测地线信息。

l <- lapply(V(graph), function(x) all_shortest_paths(graph, from = x))
l <- lapply(l, function(x) x[[-2]])
l <- unlist(l, recursive = F)
paths <- lapply(1:length(l), function(x) as_ids(l[[x]]))

从 igraph all_simple_paths 中检索路径名列表

Retrieve list of path name from igraph all_simple_paths

r

list

igraph

加法