Search a graph with depth first and breath first

Source: R/search.R

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)

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))
#> # A tbl_graph: 10 nodes and 9 edges
#> #
#> # A rooted tree
#> #
#> # Node Data: 10 × 1 (active)
#>    depth
#>    <int>
#>  1     0
#>  2     1
#>  3     1
#>  4     2
#>  5     2
#>  6     2
#>  7     2
#>  8     3
#>  9     3
#> 10     3
#> #
#> # Edge Data: 9 × 2
#>    from    to
#>   <int> <int>
#> 1     1     2
#> 2     1     3
#> 3     2     4
#> # ℹ 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 × 1 (active)
#>    order
#>    <int>
#>  1     1
#>  2     2
#>  3     3
#>  4     4
#>  5     5
#>  6     6
#>  7     7
#>  8     8
#>  9     9
#> 10    10
#> 11    11
#> 12    12
#> #
#> # Edge Data: 18 × 2
#>    from    to
#>   <int> <int>
#> 1     2     3
#> 2     1     2
#> 3     2     7
#> # ℹ 15 more rows