根据DAG中的顶点名称获取“顶级”边缘

Question

relations <- data.frame(from=c("Bob", "Tom", "Cecil", "Alice", "Esmeralda"),
                        to=c("Alice", "Cecil", "Esmeralda", "Esmeralda", "David"))
g <- graph_from_data_frame(relations, directed=TRUE)
plot(g)

我可以找到这样一个顶点的父节点：

head_of(g, E(g)[V(g)[name=="Bob"]])

我的问题是：如何找到顶点的顶级父级？在这种情况下遵循路径

鲍勃 - >爱丽丝 - >埃斯梅拉达 - >大卫

我将顶点名称Bob作为输入，并希望找到顶级父级（David）。

Answer 1

如果您从“Bob”（仅使用出境链接）获取可以到达的点子图，那么您寻找的顶级父级将是距离“Bob”最远的点。

SUB = induced_subgraph(g, subcomponent(g, "Bob", mode="out"))
TopLevel = farthest.nodes(SUB)$vertices[2]
TopLevel
+ 1/4 vertex, named:
[1] David

Answer 2

这可能不是最好的方式，你可以随时走出去的邻居，直到没有更多。例如

top_node <- function(v) {
  vx <- V(g)[v]
  vresut <- vx
  visited <- c()
  while(length(vx)>0 && !(vx %in% visited)) {
    if (length(vx)>1) stop("multiple outgoing nodes found")
    vresult <- vx
    visited <- c(visited, vx)
    vx <- V(g)[outnei(vx)]  
  }
  vresult
}

top_node("Bob")

这假设每个节点都有一个传出节点，并且没有环路/电路。