1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141
|
#' 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.
#'
#' @param root The node to start the search from
#'
#' @param 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.
#'
#' @param 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).
#'
#' @return An integer vector, the nature of which is determined by the function.
#'
#' @name search_graph
#' @rdname search_graph
#'
#' @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)
#'
NULL
# Breath First Search -----------------------------------------------------
#' @describeIn search_graph Get the succession in which the nodes are visited in a breath first search
#' @importFrom igraph bfs
#' @export
bfs_rank <- function(root, mode = 'out', unreachable = FALSE) {
expect_nodes()
graph <- .G()
root <- as_node_ind(root, graph)
ind <- bfs(graph = graph, root = root, mode = mode, unreachable = unreachable,
order = TRUE, rank = TRUE)$rank
as.integer(ind)[focus_ind(graph, 'nodes')]
}
#' @describeIn search_graph Get the nodes from which each node is visited in a breath first search
#' @importFrom igraph bfs
#' @export
bfs_parent <- function(root, mode = 'out', unreachable = FALSE) {
expect_nodes()
graph <- .G()
root <- as_node_ind(root, graph)
ind <- bfs(graph = graph, root = root, mode = mode, unreachable = unreachable,
order = TRUE, father = TRUE)$father
as.integer(ind)[focus_ind(graph, 'nodes')]
}
#' @describeIn search_graph Get the node that was visited before each node in a breath first search
#' @importFrom igraph bfs
#' @export
bfs_before <- function(root, mode = 'out', unreachable = FALSE) {
expect_nodes()
graph <- .G()
root <- as_node_ind(root, graph)
ind <- bfs(graph = graph, root = root, mode = mode, unreachable = unreachable,
order = TRUE, pred = TRUE)$pred
as.integer(ind)[focus_ind(graph, 'nodes')]
}
#' @describeIn search_graph Get the node that was visited after each node in a breath first search
#' @importFrom igraph bfs
#' @export
bfs_after <- function(root, mode = 'out', unreachable = FALSE) {
expect_nodes()
graph <- .G()
root <- as_node_ind(root, graph)
ind <- bfs(graph = graph, root = root, mode = mode, unreachable = unreachable,
order = TRUE, succ = TRUE)$succ
as.integer(ind)[focus_ind(graph, 'nodes')]
}
#' @describeIn search_graph Get the number of nodes between the root and each node in a breath first search
#' @importFrom igraph bfs
#' @export
bfs_dist <- function(root, mode = 'out', unreachable = FALSE) {
expect_nodes()
graph <- .G()
root <- as_node_ind(root, graph)
ind <- bfs(graph = graph, root = root, mode = mode, unreachable = unreachable,
order = TRUE, dist = TRUE)$dist
as.integer(ind)[focus_ind(graph, 'nodes')]
}
# Depth First Search ------------------------------------------------------
#' @describeIn search_graph Get the succession in which the nodes are visited in a depth first search
#' @importFrom igraph dfs
#' @export
dfs_rank <- function(root, mode = 'out', unreachable = FALSE) {
expect_nodes()
graph <- .G()
root <- as_node_ind(root, graph)
ind <- dfs(graph = graph, root = root, mode = mode, unreachable = unreachable,
order = TRUE)$order
match(seq_along(ind), as.integer(ind))[focus_ind(graph, 'nodes')]
}
#' @describeIn search_graph Get the succession in which each nodes subtree is completed in a depth first search
#' @importFrom igraph dfs
#' @export
dfs_rank_out <- function(root, mode = 'out', unreachable = FALSE) {
expect_nodes()
graph <- .G()
root <- as_node_ind(root, graph)
ind <- dfs(graph = graph, root = root, mode = mode, unreachable = unreachable,
order = TRUE, order.out = TRUE)$order.out
match(seq_along(ind), as.integer(ind))[focus_ind(graph, 'nodes')]
}
#' @describeIn search_graph Get the nodes from which each node is visited in a depth first search
#' @importFrom igraph dfs
#' @export
dfs_parent <- function(root, mode = 'out', unreachable = FALSE) {
expect_nodes()
graph <- .G()
root <- as_node_ind(root, graph)
ind <- dfs(graph = graph, root = root, mode = mode, unreachable = unreachable,
order = TRUE, father = TRUE)$father
as.integer(ind)[focus_ind(graph, 'nodes')]
}
#' @describeIn search_graph Get the number of nodes between the root and each node in a depth first search
#' @importFrom igraph dfs
#' @export
dfs_dist <- function(root, mode = 'out', unreachable = FALSE) {
expect_nodes()
graph <- .G()
root <- as_node_ind(root, graph)
ind <- dfs(graph = graph, root = root, mode = mode, unreachable = unreachable,
order = TRUE, dist = TRUE)$dist
as.integer(ind)[focus_ind(graph, 'nodes')]
}
|