如何遍历iGraph数据对象中的每个叶节点，并获取路径？从根节点开始遍历。

Question

我是R语言的新手，我从数据框(allTog)中创建了一个图形对象，如下所示：

library(igraph)
df.g <- graph.data.frame(d = allTog, directed = TRUE)
plot(df.g, vertex.label = V(df.g)$name)

allTog数据框的定义如下：

allTog <- data.frame(
    source = c("chamber", "chamber", "chamber", "chamber", "chamber", 
    "check", "check", "issue", "issue", "issue"), 
    target = c("check", "issue", "leak", "process", "found", "power", 
    "customer", "customer", "wafer", "replaced") 
    )

这里不关心“row.names”和“values”列。

我该如何从每个根节点（在此示例中为“chamber”）遍历到每个叶节点并获取路径，即所有节点（顶点）名称？我正在寻找一种通用解决方案，因为我的根节点可能会随着代码的每次运行而改变。例如，在下一次运行中，根节点可以是“issue”。

我想要的输出是：

chamber->check->power
chamber->issue->replaced
chamber->process
chamber->issue->customer

So and so forth....

- user1452759

---

你希望输出什么还不是很清楚。你真的需要遍历吗？看起来你并没有沿着节点收集任何信息。此外，你如何定义每个群集中的根节点？是只有入链的节点吗？永远只有一个这样的节点吗？我只是想确保我完全理解你的测试数据。因为你要求从每个叶子到每个根的路径，但现在这些路径都只包含一条边。 - MrFlick

根节点由Rshiny UI中的用户下拉菜单定义。这就是为什么根节点可以更改的原因。始终只会有一个根节点。例如：在另一次运行中，根节点可以是“晶片”。我已经编辑了问题，或许这会更清楚。 - user1452759

Answer 1

如何？

root <- "chamber"
leafnodes <- sapply(V(df.g), function(x) length(neighbors(df.g,x))==0 )
paths <- get.all.shortest.paths(df.g, V(df.g)[root], leafnodes)$res
sapply(paths, function(vs) paste(V(df.g)[vs]$name, collapse="->"))

这列出了您可以访问的所有叶子节点。

# [1] "chamber->leak"            "chamber->process"         "chamber->found"          
# [4] "chamber->check->power"    "chamber->issue->customer" "chamber->check->customer"
# [7] "chamber->issue->wafer"    "chamber->issue->replaced"

- MrFlick

---

好观点@thelatemail，我想我错过了仅从根到叶的部分。我会更新的。 - MrFlick

嘿，谢谢提供这个想法。我看到这个图中有8条路径。但是get.shortest.paths只返回7条路径。“chamber->issue->customer” 这条路径没被包括。有没有办法获取所有8条路径？ - user1452759

我接受这个答案，因为我已经决定使用这个看似部分的输出。感谢大家的帮助！ - user1452759

@user1452759 我已更新答案，以返回从根到叶子节点的所有最短路径，而不仅仅是任意一条路径。因此，如果有多种方法可以在最少的步骤中到达根和叶子节点，则将返回两条路径，因此您将获得“chamber->issue->customer”和“chamber->check->customer”两条路径。 - MrFlick