\HeaderA{unfold.tree}{Convert a general graph into a forest}{unfold.tree}
\keyword{graphs}{unfold.tree}
\begin{Description}\relax
Perform a breadth-first search on a graph and convert it into a tree or
forest by replicating vertices that were found more than once.
\end{Description}
\begin{Usage}
\begin{verbatim}
unfold.tree(graph, mode = c("all", "out", "in", "total"), roots) 
\end{verbatim}
\end{Usage}
\begin{Arguments}
\begin{ldescription}
\item[\code{graph}] The input graph, it can be either directed or
undirected.
\item[\code{mode}] Character string, defined the types of the paths used for
the breadth-first search. \dQuote{out} follows the outgoing,
\dQuote{in} the incoming edges, \dQuote{all} and \dQuote{total} both
of them. This argument is ignored for undirected graphs.
\item[\code{roots}] A vector giving the vertices from which the breadth-first
search is performed. Typically it contains one vertex per component.
\end{ldescription}
\end{Arguments}
\begin{Details}\relax
A forest is a graph, whose components are trees.

The \code{roots} vector can be calculated by simply doing a
topological sort in all components of the graph, see the examples
below.
\end{Details}
\begin{Value}
A list with two components:
\begin{ldescription}
\item[\code{tree}] The result, an \code{igraph} object, a tree or a forest.
\item[\code{vertex\_index}] A numeric vector, it gives a mapping from the
vertices of the new graph to the vertices of the old graph.
\end{ldescription}
\end{Value}
\begin{Author}\relax
Gabor Csardi \email{csardi.gabor@gmail.com}
\end{Author}
\begin{Examples}
\begin{ExampleCode}
g <- graph.tree(10) 
V(g)$id <- seq_len(vcount(g))-1
roots <- sapply(decompose.graph(g), function(x) {
            V(x)$id[ topological.sort(x)[1]+1 ] })
tree <- unfold.tree(g, roots=roots)
\end{ExampleCode}
\end{Examples}

