search_graph: Search a graph with depth first and breath first

In tidygraph: A Tidy API for Graph Manipulation

Search a graph with depth first and breath first

Description

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 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

Examples

# 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)

tidygraph documentation built on June 22, 2024, 11:32 a.m.