View source: R/structural.properties.R
bfs  R Documentation 
Breadthfirst search is an algorithm to traverse a graph. We start from a root vertex and spread along every edge “simultaneously”.
bfs(
graph,
root,
mode = c("out", "in", "all", "total"),
unreachable = TRUE,
restricted = NULL,
order = TRUE,
rank = FALSE,
father = FALSE,
pred = FALSE,
succ = FALSE,
dist = FALSE,
callback = NULL,
extra = NULL,
rho = parent.frame(),
neimode
)
graph 
The input graph. 
root 
Numeric vector, usually of length one. The root vertex, or root vertices to start the search from. 
mode 
For directed graphs specifies the type of edges to follow. ‘out’ follows outgoing, ‘in’ incoming edges. ‘all’ ignores edge directions completely. ‘total’ is a synonym for ‘all’. This argument is ignored for undirected graphs. 
unreachable 
Logical scalar, whether the search should visit the
vertices that are unreachable from the given root vertex (or vertices). If

restricted 

order 
Logical scalar, whether to return the ordering of the vertices. 
rank 
Logical scalar, whether to return the rank of the vertices. 
father 
Logical scalar, whether to return the father of the vertices. 
pred 
Logical scalar, whether to return the predecessors of the vertices. 
succ 
Logical scalar, whether to return the successors of the vertices. 
dist 
Logical scalar, whether to return the distance from the root of the search tree. 
callback 
If not 
extra 
Additional argument to supply to the callback function. 
rho 
The environment in which the callback function is evaluated. 
neimode 
This argument is deprecated from igraph 1.3.0; use

The callback function 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, ‘pred’, its predecessor (zero if this is the first vertex), ‘succ’, its successor (zero if this is the last vertex), ‘rank’, the rank of the current vertex, ‘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 function.
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. 
rank 
Numeric vector. The rank for each vertex. 
father 
Numeric vector. The father of each vertex, i.e. the vertex it was discovered from. 
pred 
Numeric vector. The previously visited vertex for each vertex, or 0 if there was no such vertex. 
succ 
Numeric vector. The next vertex that was visited after the current one, or 0 if there was no such vertex. 
dist 
Numeric vector, for each vertex its distance from the root of the search tree. 
Note that order
, rank
, father
, pred
, succ
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
dfs()
for depthfirst search.
Other structural.properties:
component_distribution()
,
connect()
,
constraint()
,
coreness()
,
degree()
,
dfs()
,
distance_table()
,
edge_density()
,
feedback_arc_set()
,
girth()
,
is_dag()
,
is_matching()
,
knn()
,
laplacian_matrix()
,
reciprocity()
,
subcomponent()
,
subgraph()
,
topo_sort()
,
transitivity()
,
unfold_tree()
,
which_multiple()
,
which_mutual()
## Two rings
bfs(make_ring(10) %du% make_ring(10),
root = 1, "out",
order = TRUE, rank = TRUE, father = TRUE, pred = TRUE,
succ = TRUE, dist = TRUE
)
## How to use a callback
f < function(graph, data, extra) {
print(data)
FALSE
}
tmp < bfs(make_ring(10) %du% make_ring(10),
root = 1, "out",
callback = f
)
## How to use a callback to stop the search
## We stop after visiting all vertices in the initial component
f < function(graph, data, extra) {
data["succ"] == 1
}
bfs(make_ring(10) %du% make_ring(10), root = 1, callback = f)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.