rust-igraph 0.0.1-alpha.4

//! `automorphism_group` (`ALGO-ISO-005`).

use super::canonicalize;
use crate::core::{Graph, IgraphResult};

/// Compute a generating set of the automorphism group `Aut(G)`.
///
/// Returns a small list of permutations that *generate* the whole group:
/// every automorphism of `graph` is a product of these generators (and
/// their inverses). Each generator `g` is a vertex permutation given as a
/// `Vec<u32>` where `g[v]` is the image of vertex `v`; it preserves
/// adjacency and, when supplied, vertex colours. This mirrors igraph's
/// `igraph_automorphism_group`, which likewise returns generators rather
/// than the full (potentially factorial) group.
///
/// The generating set is **not unique** — different correct implementations
/// (and igraph's bliss backend) may return different generators. What is
/// invariant is the group they generate: its order equals
/// [`count_automorphisms`](super::count_automorphisms::count_automorphisms).
/// The trivial group (only the identity) is represented by an empty list.
///
/// `colors` is an optional per-vertex colour slice (length must equal the
/// vertex count); only colour-preserving permutations are included. Pass
/// `None` for an uncoloured graph.
///
/// Generators come from the shared individualization-refinement engine (see
/// [`canonical_permutation`](super::canonical_permutation::canonical_permutation)):
/// every leaf of the I-R search tree whose certificate equals the canonical
/// one yields one automorphism, and a greedy subset that generates all of
/// them is returned.
///
/// # 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, automorphism_group};
///
/// // The path P_3 (0-1-2) has one non-trivial automorphism: the end swap
/// // (0 2). So a single generator suffices.
/// let mut p3 = Graph::new(3, false).unwrap();
/// p3.add_edge(0, 1).unwrap();
/// p3.add_edge(1, 2).unwrap();
/// let gens = automorphism_group(&p3, None).unwrap();
/// assert_eq!(gens, vec![vec![2, 1, 0]]);
/// ```
pub fn automorphism_group(graph: &Graph, colors: Option<&[u32]>) -> IgraphResult<Vec<Vec<u32>>> {
    Ok(canonicalize(graph, colors)?.generators)
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::collections::HashSet;

    fn cycle(n: u32, directed: bool) -> Graph {
        let mut g = Graph::new(n, directed).expect("graph");
        for i in 0..n {
            g.add_edge(i, (i + 1) % n).expect("edge");
        }
        g
    }

    fn complete(n: u32) -> Graph {
        let mut g = Graph::new(n, false).expect("graph");
        for u in 0..n {
            for v in (u + 1)..n {
                g.add_edge(u, v).expect("edge");
            }
        }
        g
    }

    fn petersen() -> Graph {
        let mut g = Graph::new(10, false).expect("graph");
        for i in 0..5 {
            g.add_edge(i, (i + 1) % 5).expect("edge");
            g.add_edge(i + 5, (i + 2) % 5 + 5).expect("edge");
            g.add_edge(i, i + 5).expect("edge");
        }
        g
    }

    /// Build a dense adjacency matrix for verifying that a permutation
    /// preserves adjacency.
    #[allow(clippy::many_single_char_names)]
    fn matrix(g: &Graph) -> Vec<Vec<bool>> {
        let n = g.vcount() as usize;
        let mut m = vec![vec![false; n]; n];
        for eid in 0..g.ecount() {
            let (u, v) = g.edge(u32::try_from(eid).expect("eid")).expect("edge");
            m[u as usize][v as usize] = true;
            if !g.is_directed() {
                m[v as usize][u as usize] = true;
            }
        }
        m
    }

    fn is_automorphism(g: &Graph, perm: &[u32]) -> bool {
        let n = g.vcount() as usize;
        if perm.len() != n {
            return false;
        }
        // Must be a permutation.
        let mut seen = vec![false; n];
        for &p in perm {
            if seen[p as usize] {
                return false;
            }
            seen[p as usize] = true;
        }
        let m = matrix(g);
        for u in 0..n {
            for v in 0..n {
                if m[u][v] != m[perm[u] as usize][perm[v] as usize] {
                    return false;
                }
            }
        }
        true
    }

    fn compose(a: &[u32], b: &[u32]) -> Vec<u32> {
        b.iter().map(|&bv| a[bv as usize]).collect()
    }

    /// Closure size of the group generated by `gens` over `n` points.
    fn closure_order(gens: &[Vec<u32>], n: usize) -> usize {
        let id: Vec<u32> = (0..n as u32).collect();
        let mut set: HashSet<Vec<u32>> = HashSet::new();
        set.insert(id.clone());
        let mut frontier = vec![id];
        while let Some(p) = frontier.pop() {
            for g in gens {
                let q = compose(g, &p);
                if set.insert(q.clone()) {
                    frontier.push(q);
                }
            }
        }
        set.len()
    }

    #[test]
    fn every_generator_is_an_automorphism() {
        for g in [complete(5), cycle(6, false), cycle(5, true), petersen()] {
            let gens = automorphism_group(&g, None).expect("gens");
            for aut in &gens {
                assert!(is_automorphism(&g, aut), "generator is not an automorphism");
            }
        }
    }

    #[test]
    fn generators_generate_full_group() {
        // Closure order must equal |Aut(G)|.
        let n = 5u32;
        assert_eq!(
            closure_order(
                &automorphism_group(&complete(n), None).expect("g"),
                n as usize
            ),
            120 // 5!
        );
        assert_eq!(
            closure_order(&automorphism_group(&cycle(6, false), None).expect("g"), 6),
            12 // dihedral
        );
        assert_eq!(
            closure_order(&automorphism_group(&cycle(5, true), None).expect("g"), 5),
            5 // rotations only
        );
        assert_eq!(
            closure_order(&automorphism_group(&petersen(), None).expect("g"), 10),
            120
        );
    }

    #[test]
    fn trivial_group_has_no_generators() {
        // The path P_4's only automorphism beyond identity is the end-swap,
        // so it needs exactly one generator. An asymmetric graph needs none.
        // A single vertex: trivial group, empty generator list.
        let g = Graph::new(1, false).expect("graph");
        assert!(automorphism_group(&g, None).expect("g").is_empty());
    }

    #[test]
    fn colors_restrict_the_group() {
        // K_4 coloured into two pairs: closure order 2*2 = 4.
        let g = complete(4);
        let colors = [0u32, 0, 1, 1];
        let gens = automorphism_group(&g, Some(&colors)).expect("g");
        for aut in &gens {
            // Every generator preserves adjacency and colours.
            assert!(is_automorphism(&g, aut));
            for (v, &img) in aut.iter().enumerate() {
                assert_eq!(colors[v], colors[img as usize], "colour not preserved");
            }
        }
        assert_eq!(closure_order(&gens, 4), 4);
    }

    #[test]
    fn rejects_multigraph() {
        let mut g = Graph::new(2, false).expect("graph");
        g.add_edge(0, 1).expect("edge");
        g.add_edge(0, 1).expect("edge");
        assert!(automorphism_group(&g, None).is_err());
    }

    #[test]
    fn rejects_wrong_color_length() {
        let g = cycle(3, false);
        let colors = [0u32, 1];
        assert!(automorphism_group(&g, Some(&colors)).is_err());
    }
}