DiagrammeR (version 0.8.4)

do_dfs: Perform a depth-first search

Description

With either a single node serving as the starting point or using the whole graph, perform a depth-first search.

Usage

do_dfs(graph, node = NULL, direction = "all")

Arguments

graph

a graph object of class dgr_graph that is created using create_graph.

node

an optional node ID value to specify a single starting point for the dfs.

direction

using all (the default), the dfs will ignore edge direction while traversing through the graph. With out, traversals between adjacent nodes will respect the edge direction.

Value

a list object containing dfs information.

Examples

library(magrittr)

# Create a graph containing two balanced trees
graph <-
  create_graph() %>%
  add_balanced_tree(2, 2) %>%
  add_balanced_tree(3, 2)

# Perform a depth-first search of the smaller tree,
# beginning at the root node `1`
dfs_info <-
  graph %>% do_dfs(1)

# The do_dfs function creates a list with
# information on the nodes visited (in the order
# visited) and the complete search path
dfs_info
#> $visited
#> [1] "1" "2" "4" "5" "3" "6" "7"
#>
#> $search_path
#>  [1] "1" "2" "4" "2" "5" "2" "1" "3" "6" "3" "7"
#> [12] "3" "1"

# The dfs can be done on the entire graph, where
# random nodes are chosen as starting points until
# the entire graph has been traversed; here, dfs
# started at one tree and finished on the other
graph %>% do_dfs
#> $visited
#>  [1] "3"  "1"  "2"  "4"  "5"  "6"  "7"  "11"
#>  [9] "8"  "9"  "12" "13" "14" "10" "15" "16"
#> [17] "17" "18" "19" "20"
#>
#> $search_path
#>  [1] "3"  "1"  "2"  "4"  "2"  "5"  "2"  "1"
#>  [9] "3"  "6"  "3"  "7"  "3"  "11" "8"  "9"
#> [17] "12" "9"  "13" "9"  "14" "9"  "8"  "10"
#> [25] "15" "10" "16" "10" "17" "10" "8"  "11"
#> [33] "18" "11" "19" "11" "20" "11"

# It's also possible to perform dfs while
# taking into account edge direction; using
# `direction = out` causes the dfs routine to
# visit nodes along outward edges
graph %>%
  do_dfs(3, "out")
#> $visited
#> [1] "3" "6" "7"
#>
#> $search_path
#> [1] "3" "6" "3" "7" "3"

# Reversing the edge directions with the
# `reverse_edge_direction()` function and performing
# dfs at the same node as before results in a
# different set of visited nodes
graph %>%
  reverse_edge_direction %>%
  do_dfs(3, "out")
#> $visited
#> [1] "3" "1"
#>
#> $search_path
#> [1] "3" "1" "3"