rust_igraph/algorithms/isomorphism/canonical/
automorphism_group.rs

1//! `automorphism_group` (`ALGO-ISO-005`).
2
3use super::canonicalize;
4use crate::core::{Graph, IgraphResult};
5
6/// Compute a generating set of the automorphism group `Aut(G)`.
7///
8/// Returns a small list of permutations that *generate* the whole group:
9/// every automorphism of `graph` is a product of these generators (and
10/// their inverses). Each generator `g` is a vertex permutation given as a
11/// `Vec<u32>` where `g[v]` is the image of vertex `v`; it preserves
12/// adjacency and, when supplied, vertex colours. This mirrors igraph's
13/// `igraph_automorphism_group`, which likewise returns generators rather
14/// than the full (potentially factorial) group.
15///
16/// The generating set is **not unique** — different correct implementations
17/// (and igraph's bliss backend) may return different generators. What is
18/// invariant is the group they generate: its order equals
19/// [`count_automorphisms`](super::count_automorphisms::count_automorphisms).
20/// The trivial group (only the identity) is represented by an empty list.
21///
22/// `colors` is an optional per-vertex colour slice (length must equal the
23/// vertex count); only colour-preserving permutations are included. Pass
24/// `None` for an uncoloured graph.
25///
26/// Generators come from the shared individualization-refinement engine (see
27/// [`canonical_permutation`](super::canonical_permutation::canonical_permutation)):
28/// every leaf of the I-R search tree whose certificate equals the canonical
29/// one yields one automorphism, and a greedy subset that generates all of
30/// them is returned.
31///
32/// # Scope
33///
34/// Simple graphs (directed or undirected), self-loops allowed, optional
35/// vertex colours. Multi-edges are rejected.
36///
37/// # Errors
38///
39/// Returns an error if `colors` has the wrong length or the graph has
40/// multiple edges between the same pair of vertices.
41///
42/// # Examples
43///
44/// ```
45/// use rust_igraph::{Graph, automorphism_group};
46///
47/// // The path P_3 (0-1-2) has one non-trivial automorphism: the end swap
48/// // (0 2). So a single generator suffices.
49/// let mut p3 = Graph::new(3, false).unwrap();
50/// p3.add_edge(0, 1).unwrap();
51/// p3.add_edge(1, 2).unwrap();
52/// let gens = automorphism_group(&p3, None).unwrap();
53/// assert_eq!(gens, vec![vec![2, 1, 0]]);
54/// ```
55pub fn automorphism_group(graph: &Graph, colors: Option<&[u32]>) -> IgraphResult<Vec<Vec<u32>>> {
56    Ok(canonicalize(graph, colors)?.generators)
57}
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62    use std::collections::HashSet;
63
64    fn cycle(n: u32, directed: bool) -> Graph {
65        let mut g = Graph::new(n, directed).expect("graph");
66        for i in 0..n {
67            g.add_edge(i, (i + 1) % n).expect("edge");
68        }
69        g
70    }
71
72    fn complete(n: u32) -> Graph {
73        let mut g = Graph::new(n, false).expect("graph");
74        for u in 0..n {
75            for v in (u + 1)..n {
76                g.add_edge(u, v).expect("edge");
77            }
78        }
79        g
80    }
81
82    fn petersen() -> Graph {
83        let mut g = Graph::new(10, false).expect("graph");
84        for i in 0..5 {
85            g.add_edge(i, (i + 1) % 5).expect("edge");
86            g.add_edge(i + 5, (i + 2) % 5 + 5).expect("edge");
87            g.add_edge(i, i + 5).expect("edge");
88        }
89        g
90    }
91
92    /// Build a dense adjacency matrix for verifying that a permutation
93    /// preserves adjacency.
94    #[allow(clippy::many_single_char_names)]
95    fn matrix(g: &Graph) -> Vec<Vec<bool>> {
96        let n = g.vcount() as usize;
97        let mut m = vec![vec![false; n]; n];
98        for eid in 0..g.ecount() {
99            let (u, v) = g.edge(u32::try_from(eid).expect("eid")).expect("edge");
100            m[u as usize][v as usize] = true;
101            if !g.is_directed() {
102                m[v as usize][u as usize] = true;
103            }
104        }
105        m
106    }
107
108    fn is_automorphism(g: &Graph, perm: &[u32]) -> bool {
109        let n = g.vcount() as usize;
110        if perm.len() != n {
111            return false;
112        }
113        // Must be a permutation.
114        let mut seen = vec![false; n];
115        for &p in perm {
116            if seen[p as usize] {
117                return false;
118            }
119            seen[p as usize] = true;
120        }
121        let m = matrix(g);
122        for u in 0..n {
123            for v in 0..n {
124                if m[u][v] != m[perm[u] as usize][perm[v] as usize] {
125                    return false;
126                }
127            }
128        }
129        true
130    }
131
132    fn compose(a: &[u32], b: &[u32]) -> Vec<u32> {
133        b.iter().map(|&bv| a[bv as usize]).collect()
134    }
135
136    /// Closure size of the group generated by `gens` over `n` points.
137    fn closure_order(gens: &[Vec<u32>], n: usize) -> usize {
138        let id: Vec<u32> = (0..n as u32).collect();
139        let mut set: HashSet<Vec<u32>> = HashSet::new();
140        set.insert(id.clone());
141        let mut frontier = vec![id];
142        while let Some(p) = frontier.pop() {
143            for g in gens {
144                let q = compose(g, &p);
145                if set.insert(q.clone()) {
146                    frontier.push(q);
147                }
148            }
149        }
150        set.len()
151    }
152
153    #[test]
154    fn every_generator_is_an_automorphism() {
155        for g in [complete(5), cycle(6, false), cycle(5, true), petersen()] {
156            let gens = automorphism_group(&g, None).expect("gens");
157            for aut in &gens {
158                assert!(is_automorphism(&g, aut), "generator is not an automorphism");
159            }
160        }
161    }
162
163    #[test]
164    fn generators_generate_full_group() {
165        // Closure order must equal |Aut(G)|.
166        let n = 5u32;
167        assert_eq!(
168            closure_order(
169                &automorphism_group(&complete(n), None).expect("g"),
170                n as usize
171            ),
172            120 // 5!
173        );
174        assert_eq!(
175            closure_order(&automorphism_group(&cycle(6, false), None).expect("g"), 6),
176            12 // dihedral
177        );
178        assert_eq!(
179            closure_order(&automorphism_group(&cycle(5, true), None).expect("g"), 5),
180            5 // rotations only
181        );
182        assert_eq!(
183            closure_order(&automorphism_group(&petersen(), None).expect("g"), 10),
184            120
185        );
186    }
187
188    #[test]
189    fn trivial_group_has_no_generators() {
190        // The path P_4's only automorphism beyond identity is the end-swap,
191        // so it needs exactly one generator. An asymmetric graph needs none.
192        // A single vertex: trivial group, empty generator list.
193        let g = Graph::new(1, false).expect("graph");
194        assert!(automorphism_group(&g, None).expect("g").is_empty());
195    }
196
197    #[test]
198    fn colors_restrict_the_group() {
199        // K_4 coloured into two pairs: closure order 2*2 = 4.
200        let g = complete(4);
201        let colors = [0u32, 0, 1, 1];
202        let gens = automorphism_group(&g, Some(&colors)).expect("g");
203        for aut in &gens {
204            // Every generator preserves adjacency and colours.
205            assert!(is_automorphism(&g, aut));
206            for (v, &img) in aut.iter().enumerate() {
207                assert_eq!(colors[v], colors[img as usize], "colour not preserved");
208            }
209        }
210        assert_eq!(closure_order(&gens, 4), 4);
211    }
212
213    #[test]
214    fn rejects_multigraph() {
215        let mut g = Graph::new(2, false).expect("graph");
216        g.add_edge(0, 1).expect("edge");
217        g.add_edge(0, 1).expect("edge");
218        assert!(automorphism_group(&g, None).is_err());
219    }
220
221    #[test]
222    fn rejects_wrong_color_length() {
223        let g = cycle(3, false);
224        let colors = [0u32, 1];
225        assert!(automorphism_group(&g, Some(&colors)).is_err());
226    }
227}
rust_igraph/algorithms/isomorphism/canonical/automorphism_group.rs

rust_igraph/algorithms/isomorphism/canonical/
automorphism_group.rs
