如何获取图中叶节点之间的所有可能路径?
How to get all possible paths between leaf nodes in a graph?
我想获得图表中的“连接组”列表。
这是一个例子:
library(igraph)
G <- graph(c(1,2,2,3,2,5,4,5,5,6,4,7,4,8,7,8,8,9), directed=F)
plot(G)
我想获取两个叶节点之间所有可能的路径:
[1] 1 2 3
[2] 1 2 5 6
[3] 1 2 5 4 8 9
[4] 1 2 5 4 7 8 9
[5] 3 2 5 6
[6] 3 2 5 4 8 9
[7] 3 2 5 4 7 8 9
[8] 6 5 4 7 8 9
[9] 6 5 4 8 9
我正在使用 R。感谢您的帮助。
我不太确定这里的确切逻辑是什么,但您似乎想要获取从每个叶节点到所有其他叶节点的路径。我们可以写一个辅助函数来做到这一点。
get_leaf_paths <- function(G) {
leafs <- V(G)[degree(G)==1]
do.call("c", lapply(1:(length(leafs)-1), function(i) {
all_simple_paths(G,leafs[[i]], leafs[[-(1:i)]])
}))
}
基本上,我们通过查找仅连接到一个其他节点的那些节点来找到叶节点,然后我们为这些节点中的每一个调用 all_simple_paths 以获得与所有其他叶节点的连接。我们只寻找与列表更靠后的其他人的联系,以避免重复。最后,我们将所有最短路径调用的结果合并到一个对象中,该对象将收集所有路径。输出看起来像这样
get_leaf_paths(G)
# [[1]]
# + 3/9 vertices, from 6d0bb8d:
# [1] 1 2 3
# [[2]]
# + 7/9 vertices, from 6d0bb8d:
# [1] 1 2 5 4 7 8 9
# [[3]]
# + 6/9 vertices, from 6d0bb8d:
# [1] 1 2 5 4 8 9
# [[4]]
# + 4/9 vertices, from 6d0bb8d:
# [1] 1 2 5 6
# [[5]]
+ 7/9 vertices, from 6d0bb8d:
# [1] 3 2 5 4 7 8 9
# [[6]]
# + 6/9 vertices, from 6d0bb8d:
# [1] 3 2 5 4 8 9
# [[7]]
# + 4/9 vertices, from 6d0bb8d:
# [1] 3 2 5 6
# [[8]]
# + 6/9 vertices, from 6d0bb8d:
# [1] 6 5 4 7 8 9
# [[9]]
# + 5/9 vertices, from 6d0bb8d:
# [1] 6 5 4 8 9
或许我们可以按照以下步骤操作:
- 根据
degree
过滤所有叶子
- 使用
combn
枚举叶子的所有组合
- 为每对叶子
生成一个all_simple-paths
列表
你可以试试这个
unlist(
combn(
V(G)[degree(G) == 1],
2,
function(x) all_simple_paths(G, x[1], x[2]),
simplify = FALSE
),
recursive = FALSE
)
这给出了
[[1]]
+ 3/9 vertices, from 27e9df3:
[1] 1 2 3
[[2]]
+ 4/9 vertices, from 27e9df3:
[1] 1 2 5 6
[[3]]
+ 7/9 vertices, from 27e9df3:
[1] 1 2 5 4 7 8 9
[[4]]
+ 6/9 vertices, from 27e9df3:
[1] 1 2 5 4 8 9
[[5]]
+ 4/9 vertices, from 27e9df3:
[1] 3 2 5 6
[[6]]
+ 7/9 vertices, from 27e9df3:
[1] 3 2 5 4 7 8 9
[[7]]
+ 6/9 vertices, from 27e9df3:
[1] 3 2 5 4 8 9
[[8]]
+ 6/9 vertices, from 27e9df3:
[1] 6 5 4 7 8 9
[[9]]
+ 5/9 vertices, from 27e9df3:
[1] 6 5 4 8 9
我想获得图表中的“连接组”列表。 这是一个例子:
library(igraph)
G <- graph(c(1,2,2,3,2,5,4,5,5,6,4,7,4,8,7,8,8,9), directed=F)
plot(G)
我想获取两个叶节点之间所有可能的路径:
[1] 1 2 3
[2] 1 2 5 6
[3] 1 2 5 4 8 9
[4] 1 2 5 4 7 8 9
[5] 3 2 5 6
[6] 3 2 5 4 8 9
[7] 3 2 5 4 7 8 9
[8] 6 5 4 7 8 9
[9] 6 5 4 8 9
我正在使用 R。感谢您的帮助。
我不太确定这里的确切逻辑是什么,但您似乎想要获取从每个叶节点到所有其他叶节点的路径。我们可以写一个辅助函数来做到这一点。
get_leaf_paths <- function(G) {
leafs <- V(G)[degree(G)==1]
do.call("c", lapply(1:(length(leafs)-1), function(i) {
all_simple_paths(G,leafs[[i]], leafs[[-(1:i)]])
}))
}
基本上,我们通过查找仅连接到一个其他节点的那些节点来找到叶节点,然后我们为这些节点中的每一个调用 all_simple_paths 以获得与所有其他叶节点的连接。我们只寻找与列表更靠后的其他人的联系,以避免重复。最后,我们将所有最短路径调用的结果合并到一个对象中,该对象将收集所有路径。输出看起来像这样
get_leaf_paths(G)
# [[1]]
# + 3/9 vertices, from 6d0bb8d:
# [1] 1 2 3
# [[2]]
# + 7/9 vertices, from 6d0bb8d:
# [1] 1 2 5 4 7 8 9
# [[3]]
# + 6/9 vertices, from 6d0bb8d:
# [1] 1 2 5 4 8 9
# [[4]]
# + 4/9 vertices, from 6d0bb8d:
# [1] 1 2 5 6
# [[5]]
+ 7/9 vertices, from 6d0bb8d:
# [1] 3 2 5 4 7 8 9
# [[6]]
# + 6/9 vertices, from 6d0bb8d:
# [1] 3 2 5 4 8 9
# [[7]]
# + 4/9 vertices, from 6d0bb8d:
# [1] 3 2 5 6
# [[8]]
# + 6/9 vertices, from 6d0bb8d:
# [1] 6 5 4 7 8 9
# [[9]]
# + 5/9 vertices, from 6d0bb8d:
# [1] 6 5 4 8 9
或许我们可以按照以下步骤操作:
- 根据
degree
过滤所有叶子
- 使用
combn
枚举叶子的所有组合
- 为每对叶子 生成一个
all_simple-paths
列表
你可以试试这个
unlist(
combn(
V(G)[degree(G) == 1],
2,
function(x) all_simple_paths(G, x[1], x[2]),
simplify = FALSE
),
recursive = FALSE
)
这给出了
[[1]]
+ 3/9 vertices, from 27e9df3:
[1] 1 2 3
[[2]]
+ 4/9 vertices, from 27e9df3:
[1] 1 2 5 6
[[3]]
+ 7/9 vertices, from 27e9df3:
[1] 1 2 5 4 7 8 9
[[4]]
+ 6/9 vertices, from 27e9df3:
[1] 1 2 5 4 8 9
[[5]]
+ 4/9 vertices, from 27e9df3:
[1] 3 2 5 6
[[6]]
+ 7/9 vertices, from 27e9df3:
[1] 3 2 5 4 7 8 9
[[7]]
+ 6/9 vertices, from 27e9df3:
[1] 3 2 5 4 8 9
[[8]]
+ 6/9 vertices, from 27e9df3:
[1] 6 5 4 7 8 9
[[9]]
+ 5/9 vertices, from 27e9df3:
[1] 6 5 4 8 9