Depth-first search in igraph

dfs-igraph.R

library(igraph)
library(tidygraph)

# Create an igraph
# c - d
#   - e
#   - f - b
ig <- graph_from_literal(f-+b, c-+e:f, c-+d)
ig

# Calculate the depth-first search from node "c"
ig_dfs <- graph.dfs(
  ig,
  root = "c",
  neimode = "out",
  father = TRUE,
  order = TRUE,
  unreachable = FALSE,
  dist = TRUE
)

# `$father` is a named vector.  Each item is a node, in the same order as V(ig).
# The values are the indices of each node's parent.  Look the indices up among
# the names to get the name of the parent.  The order of nodes in these vectors
# is arbitrary, the order of the internal storage.

node_ids <- as.numeric(V(ig)) # id of each node, in order of node id
node_names <- names(V(ig)) # name of each node, in order of node id
parent_ids <- as.integer(ig_dfs$father) # id of each node's parent, in order of node id
parent_names <- node_names[ig_dfs$father] # name of each node's parent, in order of node id
node_ids_dfs <- as.numeric(ig_dfs$order) # id of each node, in dfs order
node_names_dfs <- names(ig_dfs$order) # name of each node, in dfs order
parent_ids_dfs <- parent_ids[ig_dfs$order] # id of each node's parent, in dfs order
parent_names_dfs <- parent_names[ig_dfs$order] # name of each node's parent, in dfs order
node_depth <- as.numeric(ig_dfs$dist) # depth of each node
node_depth_dfs <- as.numeric(ig_dfs$dist[node_names_dfs]) # depth of each node, in dfs order

node_names[2] # node name, given node id
parent_ids[2] # parent id, given node id
parent_names[2] # parent name, given node id
node_depth[2] # node depth, given node id
node_ids_dfs[3] # node id, given node's place in the dfs order
node_names_dfs[3] # node name, given node's place in the dfs order
parent_ids_dfs[3] # parent id, given node's place in the dfs order
parent_names_dfs[3] # parent name, given node's place in the dfs order
node_ids[which(parent_ids == 1)] # children ids, given node id
node_names[which(parent_ids == 1)] # children names, given node id
node_ids_dfs[which(node_ids_dfs == node_ids_dfs[3])] # children ids, given node's place in the dfs order
node_names_dfs[which(node_ids_dfs == node_ids_dfs[3])] # children names, given node's place in the dfs order

# Tidygraph resolves it back to node IDs, not to names.
ig |>
  as_tbl_graph() |>
  activate(nodes) |>
  mutate(parent = dfs_parent(root = which(names(V(ig)) == "c")))