Skip to contents

Convert a general graph into a forest

Source: R/structural-properties.R
unfold_tree.Rd

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)

Arguments

graph

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

...

These dots are for future extensions and must be empty.

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.

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.

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.

unfold_tree(), vcount()

See also

Other structural.properties: bfs(), component_distribution(), connect(), constraint(), coreness(), degree(), dfs(), distance_table(), edge_density(), feedback_arc_set(), feedback_vertex_set(), girth(), is_acyclic(), is_dag(), is_matching(), k_shortest_paths(), knn(), reciprocity(), subcomponent(), subgraph(), topo_sort(), transitivity(), which_multiple(), which_mutual()

Author

Gabor Csardi csardi.gabor@gmail.com

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)