Function minimum_spanning_tree 

pub fn minimum_spanning_tree(
    graph: &Graph,
    weights: Option<&[f64]>,
    method: MstAlgorithm,
) -> IgraphResult<Vec<u32>>

Computes a minimum spanning tree (or forest, if disconnected) of graph and returns the IDs of the edges that constitute the tree.

Counterpart of igraph_minimum_spanning_tree from references/igraph/src/misc/spanning_trees.c:461.

Arguments

• graph - Input graph. Edge directions are ignored.
• weights - Optional edge weights, indexed by edge ID. When provided, weights.len() must equal graph.ecount(). NaN entries are rejected. When None, edge weights are treated as uniform and the spanning forest is an arbitrary BFS tree.
• method - Which underlying algorithm to use; see MstAlgorithm.

Returns

The edge IDs (in the order the algorithm picked them) that form the spanning tree / forest. For a graph with c connected components, the result has exactly vcount − c edges. The order reflects the algorithm: BFS layer-by-layer for Unweighted, pop-order for Prim, ascending-weight for Kruskal.

Errors

Returns IgraphError::InvalidArgument when

• weights.len() does not match graph.ecount(),
• any weight is NaN, or
• method is a weighted variant (Prim / Kruskal) but weights is None.

Examples

use rust_igraph::{Graph, MstAlgorithm, minimum_spanning_tree};

// Square 0-1-2-3-0 with diagonals 0-2 and 1-3, weights chosen so
// the unique MST is the four outer edges (weight 1) and skips both
// diagonals (weight 10).
let mut g = Graph::with_vertices(4);
g.add_edge(0, 1).unwrap(); // eid 0, w=1
g.add_edge(1, 2).unwrap(); // eid 1, w=1
g.add_edge(2, 3).unwrap(); // eid 2, w=1
g.add_edge(3, 0).unwrap(); // eid 3, w=1
g.add_edge(0, 2).unwrap(); // eid 4, w=10
g.add_edge(1, 3).unwrap(); // eid 5, w=10

let w = [1.0, 1.0, 1.0, 1.0, 10.0, 10.0];
let mut tree = minimum_spanning_tree(&g, Some(&w), MstAlgorithm::Kruskal).unwrap();
tree.sort_unstable();
// A 4-vertex graph needs vcount-1 = 3 tree edges (one square edge
// closes the cycle).
assert_eq!(tree.len(), 3);
assert!(tree.iter().all(|&e| e < 4));

References

• R. C. Prim, Shortest connection networks and some generalizations, Bell System Technical Journal 36 (1957), 1389-1401.
• J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc. 7 (1956), 48-50.