Function maximum_cardinality_search 

pub fn maximum_cardinality_search(graph: &Graph) -> IgraphResult<McsResult>

Computes a maximum cardinality search ordering.

Assigns a rank to each vertex such that visiting vertices in decreasing rank order corresponds to always choosing the vertex with the most already-visited neighbors next. Edge directions are ignored. Self-loops and multi-edges are stripped internally.

Returns

An McsResult with alpha (vertex-to-rank) and alpham1 (rank-to-vertex, the inverse).

Complexity

O(|V| + |E|) using bucket-list data structures.

References

R. E. Tarjan, M. Yannakakis: “Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs.” SIAM J. Comput. 13, 566–579, 1984.

Examples

use rust_igraph::{maximum_cardinality_search, create};

let g = create(&[(0, 1), (1, 2), (2, 0)], 3, false).unwrap();
let mcs = maximum_cardinality_search(&g).unwrap();
assert_eq!(mcs.alpha.len(), 3);
assert_eq!(mcs.alpham1.len(), 3);
// alpham1 is the inverse of alpha
for (v, &rank) in mcs.alpha.iter().enumerate() {
    assert_eq!(mcs.alpham1[rank as usize], v as u32);
}