File: search.R

package info (click to toggle)
r-cran-tidygraph 1.3.1-2
  • links: PTS, VCS
  • area: main
  • in suites: forky, sid, trixie
  • size: 880 kB
  • sloc: cpp: 41; sh: 13; makefile: 2
file content (141 lines) | stat: -rw-r--r-- 5,494 bytes parent folder | download
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')]
}