How to find 'first' and 'last' vertex connected to vertex

Question

Suppose I have an adjacency matrix as follows:

library(igraph)
df <- data.frame(id = 1:8, parent = c(NA, NA, 1, 1, 3, 4, NA, 7))
g <- graph_from_data_frame(na.omit(df))

For each vertex, how do I show the first and final vertices in the directed path? For example, vertex '4' starts at 6 and ends with 1. (Alternatively, obtaining a list of all vertices in that path would work).

So you just want the in and out neighbors? What would be the result for vertex 1 or vertex 8? What if a vertex is connected to more than 2 other vertices? Maybe checkout the `neighbors()` function. — MrFlick, Apr 27 '16 at 20:04
I want the root/terminal leaves of each tree. The data (should) be such that all trees in the forest only have a single root. — Soul Donut, Apr 27 '16 at 20:25

score 5 · Answer 1 · edited Sep 20 '17 at 19:27

5

Consider a topological sort. Topological sorting a directed graph will give you the first and last vertex.

For R you may use the topological sort method in the igraph package. http://igraph.org/r/doc/topo_sort.html

edited Sep 20 '17 at 19:27

jsta

3,216
25
35

answered Apr 27 '16 at 20:32

Felipe Sulser

1,185
8
19

score 0 · Answer 2 · edited May 23 '17 at 12:08

Following this answer, I ended up doing a graph decomposition on the forest, then finding which vertices had an out-degree equal to 0, thus determining the root node for each tree (doing the same for in-degree yields which vertices are terminal, although I realized I didn't need this information -- as a result I'm not marking this as the answer).

library(igraph)
library(dplyr)

df <- data.frame(id = 1:8, parent = c(NA, NA, 1, 1, 3, 4, NA, 7))
edgelist_df <- na.omit(df)
g <- graph_from_data_frame(edgelist_df)

tree_to_df <- function(graph, forest_edgelist){
  # for a directed tree, find its root and assign that root to every
  # node in the tree's edgelist

  # `dplyr::filter` fails on the subset below, so we use base R
  tree_dat <- forest_edgelist[forest_edgelist$id %in% V(graph)$name,]

  root <- which(degree(graph, v = V(graph), mode = 'out') == 0, useNames = T)
  tree_dat$root <- names(root)
  return(tree_dat)
}

root_dat <-
   decompose.graph %>% # find connected subgraphs
   lapply(tree_to_df, forest_edgelist = edgelist_df) %>%
   bind_rows

How to find 'first' and 'last' vertex connected to vertex

2 Answers2