igraph R中从根到叶的有向树图中的所有路径

本文介绍了igraph R中从根到叶的有向树图中的所有路径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给出的是一棵树:

library(igraph) # setup graph g= graph.formula(A -+ B, A -+ C, B -+ C, B -+ D, B -+ E ) plot(g, layout = layout.reingold.tilford(g, root="A"))

顶点"A"是树的根，而顶点"C", "D", "E"被视为终叶.

Vertex "A" is the root of the tree, while vertices "C", "D", "E" are considered as terminal leaves.

问题:

任务是查找根与叶之间的所有路径.使用以下代码失败，因为它仅提供最短的路径:

The task is to find all paths between root and leaves. I fail with following code, as it only provides the shortest paths:

# find root and leaves leaves= which(degree(g, v = V(g), mode = "out")==0, useNames = T) root= which(degree(g, v = V(g), mode = "in")==0, useNames = T) # find all paths paths= lapply(root, function(x) get.all.shortest.paths(g, from = x, to = leaves, mode = "out")$res) named_paths= lapply(unlist(paths, recursive=FALSE), function(x) V(g)[x]) named_paths

输出:

$A1 Vertex sequence: [1] "A" "C" $A2 Vertex sequence: [1] "A" "B" "D" $A3 Vertex sequence: [1] "A" "B" "E"

问题:

如何找到包括顶点序列在内的所有路径:"A" "B" "C"?

How can I find all paths including the vertex sequence: "A" "B" "C"?

我的理解是，get.all.shortest.paths()没有提供缺失的序列"A" "B" "C"作为通过顶点序列从"A"到"C"的路径:"A" "C"(可在列表元素$A1中找到) )较短.因此igraph可以正常工作. 尽管如此，我仍在寻找一种代码解决方案，以R list的形式获取从根到所有叶子的所有路径.

My understanding is, that the missing sequence "A" "B" "C" is not provided by get.all.shortest.paths() as the path from "A" to "C" via the vertex sequence: "A" "C" (which is found in list element $A1) is shorter. So igraph works properly. Nevertheless I am looking for a code solution to get all paths from the root to all leaves in form of a R list.

评论:

我知道对于大树，覆盖所有组合的算法可能会变得昂贵，但是我的实际应用相对较小.

I am aware that for large trees the algorithm covering all combinations might become expensive, but my real application is relatively small.

推荐答案

基于Gabor的评论:

Based on Gabor's comment:

all_simple_paths(g, from = root, to = leaves)

产量:

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