View source: R/structural.properties.R
dfs | R Documentation |
Depth-first search is an algorithm to traverse a graph. It starts from a root vertex and tries to go quickly as far from as possible.
dfs(
graph,
root,
mode = c("out", "in", "all", "total"),
unreachable = TRUE,
order = TRUE,
order.out = FALSE,
father = FALSE,
dist = FALSE,
in.callback = NULL,
out.callback = NULL,
extra = NULL,
rho = parent.frame(),
neimode = deprecated()
)
The callback functions must have the following arguments:
The input graph is passed to the callback function here.
A named numeric vector, with the following entries: ‘vid’, the vertex that was just visited and ‘dist’, its distance from the root of the search tree.
The extra argument.
The callback must return FALSE to continue the search or TRUE to terminate it. See examples below on how to use the callback functions.
A named list with the following entries:
root |
Numeric scalar. The root vertex that was used as the starting point of the search. |
neimode |
Character scalar. The |
order |
Numeric vector. The vertex ids, in the order in which they were visited by the search. |
order.out |
Numeric vector, the vertex ids, in the order of the completion of their subtree. |
father |
Numeric vector. The father of each vertex, i.e. the vertex it was discovered from. |
dist |
Numeric vector, for each vertex its distance from the root of the search tree. |
Note that order
, order.out
, father
, and dist
might be NULL
if their corresponding argument is FALSE
, i.e.
if their calculation is not requested.
Gabor Csardi csardi.gabor@gmail.com
bfs()
for breadth-first search.
Other structural.properties:
bfs()
,
component_distribution()
,
connect()
,
constraint()
,
coreness()
,
degree()
,
distance_table()
,
edge_density()
,
feedback_arc_set()
,
girth()
,
is_acyclic()
,
is_dag()
,
is_matching()
,
k_shortest_paths()
,
knn()
,
reciprocity()
,
subcomponent()
,
subgraph()
,
topo_sort()
,
transitivity()
,
unfold_tree()
,
which_multiple()
,
which_mutual()
## A graph with two separate trees
dfs(make_tree(10) %du% make_tree(10),
root = 1, "out",
TRUE, TRUE, TRUE, TRUE
)
## How to use a callback
f.in <- function(graph, data, extra) {
cat("in:", paste(collapse = ", ", data), "\n")
FALSE
}
f.out <- function(graph, data, extra) {
cat("out:", paste(collapse = ", ", data), "\n")
FALSE
}
tmp <- dfs(make_tree(10),
root = 1, "out",
in.callback = f.in, out.callback = f.out
)
## Terminate after the first component, using a callback
f.out <- function(graph, data, extra) {
data["vid"] == 1
}
tmp <- dfs(make_tree(10) %du% make_tree(10),
root = 1,
out.callback = f.out
)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.