tidygraph: search_graph – R documentation

Become an expert in R — Interactive courses, Cheat Sheets, certificates and more!

search_graph

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

A Tidy API for Graph Manipulation

v1.2.0

MIT + file LICENSE

Authors

Thomas Lin Pedersen [cre, aut] (<https://orcid.org/0000-0002-5147-4711>)

Initial release