Function canonical_permutation 

pub fn canonical_permutation(
    graph: &Graph,
    colors: Option<&[u32]>,
) -> IgraphResult<Vec<u32>>

Compute a canonical vertex permutation of graph.

The returned vector labeling has one entry per vertex: labeling[v] is the canonical position assigned to vertex v (a vertex → position map). Two graphs are isomorphic if and only if relabeling each by its canonical permutation produces the same graph, so canonical permutations give an isomorphism test by comparison of canonical forms.

colors is an optional per-vertex colour slice (length must equal the vertex count); vertices of different colours are never identified. Pass None for an uncoloured graph.

This mirrors igraph’s igraph_canonical_permutation (BLISS-backed upstream). The specific labeling is implementation-defined — only the resulting canonical form is meaningful — so the labeling here need not match igraph’s byte-for-byte, but the induced canonical form is a valid isomorphism invariant.

Scope

Simple graphs (directed or undirected), self-loops allowed, optional vertex colours. Multi-edges are rejected.

Errors

Returns an error if colors has the wrong length or the graph has multiple edges between the same pair of vertices.

Examples

use rust_igraph::{Graph, canonical_permutation, permute_vertices};

// Two differently-labeled copies of the path 0-1-2.
let mut a = Graph::new(3, false).unwrap();
a.add_edge(0, 1).unwrap();
a.add_edge(1, 2).unwrap();

let mut b = Graph::new(3, false).unwrap();
b.add_edge(2, 1).unwrap();
b.add_edge(1, 0).unwrap();

let pa = canonical_permutation(&a, None).unwrap();
let pb = canonical_permutation(&b, None).unwrap();
assert_eq!(pa.len(), 3);

// Relabeling each graph to canonical form yields identical edge sets.
// `permute_vertices` wants a position -> vertex map, the inverse of `labeling`.
let inv = |p: &[u32]| -> Vec<u32> {
    let mut q = vec![0u32; p.len()];
    for (v, &pos) in p.iter().enumerate() {
        q[pos as usize] = v as u32;
    }
    q
};
let ca = permute_vertices(&a, &inv(&pa)).unwrap();
let cb = permute_vertices(&b, &inv(&pb)).unwrap();
let mut ea: Vec<_> = (0..ca.ecount()).map(|e| ca.edge(e as u32).unwrap()).collect();
let mut eb: Vec<_> = (0..cb.ecount()).map(|e| cb.edge(e as u32).unwrap()).collect();
ea.sort_unstable();
eb.sort_unstable();
assert_eq!(ea, eb);