CODEWITHSUNDEEP
rigraphdirected-acyclic-graphs
user3575737
user3575737

Reputation: 79

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

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)

I can find the parent of a vertex like this:

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

My question is: how can I find the top level parent of a vertex? In this case following the path

Bob -> Alice -> Esmeralda -> David

I have the vertex name Bob as input and want to find the top level parent (David).

Upvotes: 1

Views: 63

Answers (2)

G5W
G5W

Reputation: 37641

If you take the subgraph of points that you can reach from "Bob" (using only out-bound links), then the top level parent that you seek will be the most distant point from "Bob". 

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

Upvotes: 3

MrFlick
MrFlick

Reputation: 206197

This might not be the best way, by you could always walk the outgoing neighbors till there are no more. For example

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

This assumes that each node has one outgoing node and that there are no loops/circuits.

Upvotes: 0

Related Questions