r - 通过节点/顶点查找图中的所有路径

Question

我有一个定向igraph：

library( igraph )
links <- data.frame( from = c(1,1, 2,2,3, 3,3,4,6,7,7, 8),
                     to =   c(2,10,3,4,12,4,8,5,7,3,11,9) )
nodes <- data.frame( name = 1:12 )
net <- graph_from_data_frame( d = links, vertices = nodes, directed = TRUE ) 
plot(net)

我想要的是：

1. 获取图的子集，包含节点 3 一步内的所有节点（进出）
2. 获取子集中通过节点 3 的所有路径的列表

对于第 1 步，我可以这样做：

ego.list <- make_ego_graph( net, order = 1, nodes = 3, mode = "all")
desired_subset <- NULL
for (i in seq_along(ego.list) ){
  x <- ego.list[[i]]
  desired_subset <- graph.union( desired_subset, x )
}
plot(desired_subset)

但是现在我被卡住了。我想要的是找到整个（有向）子集中的所有路径，这些路径通过节点 3，所以：

• 2->3->12
• 2->3->4
• 2->3->8
• 7->3->12
• 7->3->4
• 7->3->8

到目前为止，我发现的只是获取从一个节点到另一个节点的路径列表。但我想获得通过某个节点的所有路径的列表。
有任何想法吗？

标签： r

Answer 1

找到了解决办法！

使用igraph R 中从根到叶子的有向树图中的所有路径，我得到以下代码：

#for shorter code
g <- desired_subset
# find entrynodes (nothing goes in) and exit_nodes (nothing goes out)
exit_nodes  <- which( degree(g, v = V(g), mode = "out" ) == 0 )
entry_nodes <- which( degree(g, v = V(g), mode = "in" ) == 0)
# find all paths from entry to exit nodes
paths= lapply( entry_nodes, function(x) all_simple_paths(g, from = x, to = exit_nodes))
named_paths= lapply(unlist(paths, recursive=FALSE), function(x) V(g)[x])
#filter out all paths that do not contain node 3
answer <- named_paths[ unlist( lapply( named_paths, function(x) 3 %in% names(x) ) ) ]
#put in a data.table
as.data.table(data.table::transpose( lapply(answer, names) ) )

#    V1 V2 V3
# 1:  2  3  4
# 2:  2  3  8
# 3:  2  3 12
# 4:  7  3  4
# 5:  7  3  8
# 6:  7  3 12