search_graph
Search a graph with depth first and breath first
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.
Usage
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)
Arguments
- root
The node to start the search from
- mode
How edges are followed in the search if the graph is directed.
"out"
only follows outbound edges,"in"
only follows inbound edges, and"all"
or"total"
follows all edges. This is ignored for undirected graphs.- unreachable
Should the search jump to a new component if the search is terminated without all nodes being visited? Default to
FALSE
(only reach connected nodes).
Value
An integer vector, the nature of which is determined by the function.
Functions
bfs_rank
: Get the succession in which the nodes are visited in a breath first searchbfs_parent
: Get the nodes from which each node is visited in a breath first searchbfs_before
: Get the node that was visited before each node in a breath first searchbfs_after
: Get the node that was visited after each node in a breath first searchbfs_dist
: Get the number of nodes between the root and each node in a breath first searchdfs_rank
: Get the succession in which the nodes are visited in a depth first searchdfs_rank_out
: Get the succession in which each nodes subtree is completed in a depth first searchdfs_parent
: Get the nodes from which each node is visited in a depth first searchdfs_dist
: Get the number of nodes between the root and each node in a depth first search
Examples
# NOT RUN {
# Get the depth of each node in a tree
create_tree(10, 2) %>%
activate(nodes) %>%
mutate(depth = bfs_dist(root = 1))
# Reorder nodes based on a depth first search from node 3
create_notable('franklin') %>%
activate(nodes) %>%
mutate(order = dfs_rank(root = 3)) %>%
arrange(order)
# }