These functions wraps the igraph::bfs()
and igraph::dfs()
functions to
provide a consistent return value that can be used in dplyr::mutate()
calls. Each function returns an integer vector with values matching the order
of the nodes in the graph.
bfs_rank(root, mode = "out", unreachable = FALSE) bfs_parent(root, mode = "out", unreachable = FALSE) bfs_before(root, mode = "out", unreachable = FALSE) bfs_after(root, mode = "out", unreachable = FALSE) bfs_dist(root, mode = "out", unreachable = FALSE) dfs_rank(root, mode = "out", unreachable = FALSE) dfs_rank_out(root, mode = "out", unreachable = FALSE) dfs_parent(root, mode = "out", unreachable = FALSE) dfs_dist(root, mode = "out", unreachable = FALSE)
root  The node to start the search from 

mode  How edges are followed in the search if the graph is directed.

unreachable  Should the search jump to a new component if the search is
terminated without all nodes being visited? Default to 
An integer vector, the nature of which is determined by the function.
bfs_rank
: Get the succession in which the nodes are visited in a breath first search
bfs_parent
: Get the nodes from which each node is visited in a breath first search
bfs_before
: Get the node that was visited before each node in a breath first search
bfs_after
: Get the node that was visited after each node in a breath first search
bfs_dist
: Get the number of nodes between the root and each node in a breath first search
dfs_rank
: Get the succession in which the nodes are visited in a depth first search
dfs_rank_out
: Get the succession in which each nodes subtree is completed in a depth first search
dfs_parent
: Get the nodes from which each node is visited in a depth first search
dfs_dist
: Get the number of nodes between the root and each node in a depth first search
# Get the depth of each node in a tree create_tree(10, 2) %>% activate(nodes) %>% mutate(depth = bfs_dist(root = 1))#> # A tbl_graph: 10 nodes and 9 edges #> # #> # A rooted tree #> # #> # Node Data: 10 x 1 (active) #> depth #> <int> #> 1 0 #> 2 1 #> 3 1 #> 4 2 #> 5 2 #> 6 2 #> # … with 4 more rows #> # #> # Edge Data: 9 x 2 #> from to #> <int> <int> #> 1 1 2 #> 2 1 3 #> 3 2 4 #> # … with 6 more rows# Reorder nodes based on a depth first search from node 3 create_notable('franklin') %>% activate(nodes) %>% mutate(order = dfs_rank(root = 3)) %>% arrange(order)#> # A tbl_graph: 12 nodes and 18 edges #> # #> # An undirected simple graph with 1 component #> # #> # Node Data: 12 x 1 (active) #> order #> <int> #> 1 1 #> 2 2 #> 3 3 #> 4 4 #> 5 5 #> 6 6 #> # … with 6 more rows #> # #> # Edge Data: 18 x 2 #> from to #> <int> <int> #> 1 2 3 #> 2 1 2 #> 3 2 7 #> # … with 15 more rows