根据 DAG 中的顶点名称获取 "top level" 条边

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

这可能不是最好的方法，因为您总是可以步行离开即将离去的邻居，直到再也没有人了。例如

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")

这假设每个节点都有一个输出节点并且没有loops/circuits。

Answer 2

如果您采用可以从 "Bob" 到达的点的子图（仅使用出站链接），那么您寻找的顶级父级将是距 [=13= 最远的点].

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

根据 DAG 中的顶点名称获取 "top level" 条边

Get "top level" edge based on vertex name in DAG

r

igraph

directed-acyclic-graphs