bfs.Rd

% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/structural.properties.R
\name{bfs}
\alias{bfs}
\title{Breadth-first search}
\usage{
bfs(
  graph,
  root,
  mode = c("out", "in", "all", "total"),
  unreachable = TRUE,
  restricted = NULL,
  order = TRUE,
  rank = FALSE,
  parent = FALSE,
  pred = FALSE,
  succ = FALSE,
  dist = FALSE,
  callback = NULL,
  extra = NULL,
  rho = parent.frame(),
  neimode = deprecated(),
  father = deprecated()
)
}
\arguments{
\item{graph}{The input graph.}

\item{root}{Numeric vector, usually of length one. The root vertex, or root
vertices to start the search from.}

\item{mode}{For directed graphs specifies the type of edges to follow.
\sQuote{out} follows outgoing, \sQuote{in} incoming edges. \sQuote{all}
ignores edge directions completely. \sQuote{total} is a synonym for
\sQuote{all}. This argument is ignored for undirected graphs.}

\item{unreachable}{Logical scalar, whether the search should visit the
vertices that are unreachable from the given root vertex (or vertices). If
\code{TRUE}, then additional searches are performed until all vertices are
visited.}

\item{restricted}{\code{NULL} (=no restriction), or a vector of vertices
(ids or symbolic names). In the latter case, the search is restricted to the
given vertices.}

\item{order}{Logical scalar, whether to return the ordering of the vertices.}

\item{rank}{Logical scalar, whether to return the rank of the vertices.}

\item{parent}{Logical scalar, whether to return the parent of the vertices.}

\item{pred}{Logical scalar, whether to return the predecessors of the
vertices.}

\item{succ}{Logical scalar, whether to return the successors of the
vertices.}

\item{dist}{Logical scalar, whether to return the distance from the root of
the search tree.}

\item{callback}{If not \code{NULL}, then it must be callback function. This
is called whenever a vertex is visited. See details below.}

\item{extra}{Additional argument to supply to the callback function.}

\item{rho}{The environment in which the callback function is evaluated.}

\item{neimode}{\ifelse{html}{\href{https://lifecycle.r-lib.org/articles/stages.html#deprecated}{\figure{lifecycle-deprecated.svg}{options: alt='[Deprecated]'}}}{\strong{[Deprecated]}} This argument is deprecated
from igraph 1.3.0; use \code{mode} instead.}

\item{father}{\ifelse{html}{\href{https://lifecycle.r-lib.org/articles/stages.html#deprecated}{\figure{lifecycle-deprecated.svg}{options: alt='[Deprecated]'}}}{\strong{[Deprecated]}} Use \code{parent} instead.}
}
\value{
A named list with the following entries:
\item{root}{Numeric scalar.
The root vertex that was used as the starting point of the search.}
\item{neimode}{Character scalar. The \code{mode} argument of the function
call. Note that for undirected graphs this is always \sQuote{all},
irrespectively of the supplied value.}
\item{order}{Numeric vector. The
vertex ids, in the order in which they were visited by the search.}
\item{rank}{Numeric vector. The rank for each vertex, zero for unreachable vertices.}
\item{parent}{Numeric
vector. The parent of each vertex, i.e. the vertex it was discovered from.}
\item{father}{Like parent, kept for compatibility for now.}
\item{pred}{Numeric vector. The previously visited vertex for each vertex,
or 0 if there was no such vertex.}
\item{succ}{Numeric vector. The next
vertex that was visited after the current one, or 0 if there was no such
vertex.}
\item{dist}{Numeric vector, for each vertex its distance from the
root of the search tree. Unreachable vertices have a negative distance
as of igraph 1.6.0, this used to be \code{NaN}.}

Note that \code{order}, \code{rank}, \code{parent}, \code{pred}, \code{succ}
and \code{dist} might be \code{NULL} if their corresponding argument is
\code{FALSE}, i.e. if their calculation is not requested.
}
\description{
Breadth-first search is an algorithm to traverse a graph. We start from a
root vertex and spread along every edge \dQuote{simultaneously}.
}
\details{
The callback function must have the following arguments:
\describe{
\item{graph}{The input graph is passed to the callback function here.}
\item{data}{A named numeric vector, with the following entries:
\sQuote{vid}, the vertex that was just visited, \sQuote{pred}, its
predecessor (zero if this is the first vertex), \sQuote{succ}, its successor
(zero if this is the last vertex), \sQuote{rank}, the rank of the
current vertex, \sQuote{dist}, its distance from the root of the search
tree.}
\item{extra}{The extra argument.}
}

The callback must return \code{FALSE}
to continue the search or \code{TRUE} to terminate it. See examples below on how to
use the callback function.
}
\examples{

## Two rings
bfs(make_ring(10) \%du\% make_ring(10),
  root = 1, "out",
  order = TRUE, rank = TRUE, parent = 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)

}
\seealso{
\code{\link[=dfs]{dfs()}} for depth-first search.

Other structural.properties: 
\code{\link{component_distribution}()},
\code{\link{connect}()},
\code{\link{constraint}()},
\code{\link{coreness}()},
\code{\link{degree}()},
\code{\link{dfs}()},
\code{\link{distance_table}()},
\code{\link{edge_density}()},
\code{\link{feedback_arc_set}()},
\code{\link{girth}()},
\code{\link{is_acyclic}()},
\code{\link{is_dag}()},
\code{\link{is_matching}()},
\code{\link{k_shortest_paths}()},
\code{\link{knn}()},
\code{\link{reciprocity}()},
\code{\link{subcomponent}()},
\code{\link{subgraph}()},
\code{\link{topo_sort}()},
\code{\link{transitivity}()},
\code{\link{unfold_tree}()},
\code{\link{which_multiple}()},
\code{\link{which_mutual}()}
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\concept{structural.properties}
\keyword{graphs}