#r #igraph #directed-acyclic-graphs
#r #igraph #направленные ациклические графы
Вопрос:
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).
Ответ №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
Комментарии:
1. Отлично! Есть идеи, как я могу получить только имя вершины в виде строки / символа?
2. Если вам нужна только строка, а не весь узел, вы можете использовать
TopLevel$name
Ответ №2:
Возможно, это не лучший способ, поскольку вы всегда можете обойти исходящих соседей, пока их больше не останется. Например
top_node <- function(v) {
vx <- V(g)[v]
vresut <- vx
visited <- c()
while(length(vx)>0 amp;amp; !(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")
Это предполагает, что у каждого узла есть один исходящий узел и что нет циклов / контуров.