sample_spanning_tree: Samples from the spanning trees of a graph randomly and...

In igraph: Network Analysis and Visualization

Samples from the spanning trees of a graph randomly and uniformly

Description

sample_spanning_tree() picks a spanning tree of an undirected graph randomly and uniformly, using loop-erased random walks.

Usage

sample_spanning_tree(graph, vid = 0)

Arguments

graph	The input graph to sample from. Edge directions are ignored if the graph is directed.
vid	When the graph is disconnected, this argument specifies how to handle the situation. When the argument is zero (the default), the sampling will be performed component-wise, and the result will be a spanning forest. When the argument contains a vertex ID, only the component containing the given vertex will be processed, and the result will be a spanning tree of the component of the graph.

Value

An edge sequence containing the edges of the spanning tree. Use subgraph_from_edges() to extract the corresponding subgraph.

Related documentation in the C library

igraph_random_spanning_tree().

See Also

subgraph_from_edges() to extract the tree itself

Other trees: is_forest(), is_tree(), make_from_prufer(), to_prufer()

Examples

g <- make_full_graph(10) %du% make_full_graph(5)
edges <- sample_spanning_tree(g)
forest <- subgraph_from_edges(g, edges)

igraph documentation built on Oct. 20, 2024, 1:06 a.m.