igraph (version 1.3.5)

unfold_tree: Convert a general graph into a forest

Description

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.

Usage

unfold_tree(graph, mode = c("all", "out", "in", "total"), roots)

Value

A list with two components:

tree

The result, an igraph object, a tree or a forest.

vertex_index

A numeric vector, it gives a mapping from the vertices of the new graph to the vertices of the old graph.

Arguments

graph

The input graph, it can be either directed or undirected.

mode

Character string, defined the types of the paths used for the breadth-first search. “out” follows the outgoing, “in” the incoming edges, “all” and “total” both of them. This argument is ignored for undirected graphs.

roots

A vector giving the vertices from which the breadth-first search is performed. Typically it contains one vertex per component.

Author

Gabor Csardi

Details

A forest is a graph, whose components are trees.

The roots vector can be calculated by simply doing a topological sort in all components of the graph, see the examples below.

Examples

g <- make_tree(10) %du% make_tree(10)
V(g)$id <- seq_len(vcount(g))-1
roots <- sapply(decompose(g), function(x) {
            V(x)$id[ topo_sort(x)[1]+1 ] })
tree <- unfold_tree(g, roots=roots)