graph.bfs

0th

Percentile

Breadth-first search

Breadth-first search is an algorithm to traverse a graph. We start from a root vertex and spread along every edge simultaneously.

Keywords
graphs
Usage
graph.bfs (graph, root, neimode = 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())
Arguments
graph
The input graph.
root
Numeric vector, usually of length one. The root vertex, or root vertices to start the search from.
neimode
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<
unreachable
Logical scalar, whether the search should visit the vertices that are unreachable from the given root vertex (or vertices). If TRUE, then additional searches are performed until all vertices are visited.
restricted
NULL (=no restriction), or a vector of vertices (ids or symbolic names). In the latter case, the search is restricted to the given vertices.
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 NULL, then it must be callback function. This is called whenever a vertex is visited. See details below.
extra
Additional argument to supply to the callback function.
rho
The environment in which the callback function is evaluated.
Details

The callback function must have the following arguments: [object Object],[object Object],[object Object] See examples below on how to use the callback function.

Value

  • A named list with the following entries:
  • rootNumeric scalar. The root vertex that was used as the starting point of the search.
  • neimodeCharacter scalar. The neimode argument of the function call. Note that for undirected graphs this is always all, irrespectively of the supplied value.
  • orderNumeric vector. The vertex ids, in the order in which they were visited by the search.
  • rankNumeric vector. The rank for each vertex.
  • fatherNumeric vector. The father of each vertex, i.e. the vertex it was discovered from.
  • predNumeric vector. The previously visited vertex for each vertex, or 0 if there was no such vertex.
  • succNumeric vector. The next vertex that was visited after the current one, or 0 if there was no such vertex.
  • distNumeric 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.

See Also

graph.dfs for depth-first search.

Aliases
  • graph.bfs
Examples
## Two rings
graph.bfs(graph.ring(10) %du% graph.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 <- graph.bfs(graph.ring(10) %du% graph.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
}
graph.bfs(graph.ring(10) %du% graph.ring(10), root=1, callback=f)
Documentation reproduced from package igraph, version 0.6.5-2, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.