map_dfs: Apply a function to nodes in the order of a depth first search

Description

These functions allow you to map over the nodes in a graph, by first performing a depth first search on the graph and then mapping over each node in the order they are visited. The mapping function will have access to the result and search statistics for all the nodes between itself and the root in the search. To map over the nodes in the reverse direction use map_dfs_back().

Usage

map_dfs(root, mode = "out", unreachable = FALSE, .f, ...)
map_dfs_lgl(root, mode = "out", unreachable = FALSE, .f, ...)
map_dfs_chr(root, mode = "out", unreachable = FALSE, .f, ...)
map_dfs_int(root, mode = "out", unreachable = FALSE, .f, ...)
map_dfs_dbl(root, mode = "out", unreachable = FALSE, .f, ...)

Value

map_dfs() returns a list of the same length as the number of nodes in the graph, in the order matching the node order in the graph (that is, not in the order they are called). map_dfs_*() tries to coerce its result into a vector of the classes logical (map_dfs_lgl), character

(map_dfs_chr), integer (map_dfs_int), or double (map_dfs_dbl). These functions will throw an error if they are unsuccesful, so they are type safe.

Arguments

root: The node to start the search from
mode: How should edges be followed? 'out' only follows outbound edges, 'in' only follows inbound edges, and 'all' follows all edges. This parameter is ignored for undirected graphs.
unreachable: Should the search jump to an unvisited node if the search is completed without visiting all nodes.
.f: A function to map over all nodes. See Details
...: Additional parameters to pass to .f

Details

The function provided to .f will be called with the following arguments in addition to those supplied through ...:

graph: The full tbl_graph object
node: The index of the node currently mapped over
rank: The rank of the node in the search
rank_out: The rank of the completion of the nodes subtree
parent: The index of the node that led to the current node
dist: The distance of the current node from the root
path: A table containing node, rank, rank_out, parent, dist, and resultcolumns giving the values for each node leading to the current node. Theresult` column will contain the result of the mapping of each node in a list.

Instead of spelling out all of these in the function it is possible to simply name the ones needed and use ... to catch the rest.

Examples

Run this code

# Add a random integer to the last value along a search
create_tree(40, children = 3, directed = TRUE) %>%
  mutate(child_acc = map_dfs_int(node_is_root(), .f = function(node, path, ...) {
    last_val <- if (nrow(path) == 0) 0L else tail(unlist(path$result), 1)
    last_val + sample(1:10, 1)
  }))