rust_igraph/algorithms/isomorphism/canonical/
count_automorphisms.rs

1//! `count_automorphisms` (`ALGO-ISO-004`).
2
3use super::canonicalize;
4use crate::core::{Graph, IgraphResult};
5
6/// Count the automorphisms of `graph` — the order `|Aut(G)|` of its
7/// automorphism group.
8///
9/// An automorphism is a vertex permutation that maps `graph` onto itself
10/// (preserving adjacency and, when supplied, vertex colours). The count can
11/// grow factorially, so it is returned as an `f64`, exactly as igraph's
12/// `igraph_count_automorphisms` returns an `igraph_real_t`. The value is
13/// exact up to `2^53`; beyond that the `f64` loses precision (igraph has the
14/// same limit and offers a string-returning variant for larger groups, which
15/// is out of scope here).
16///
17/// `colors` is an optional per-vertex colour slice (length must equal the
18/// vertex count); only colour-preserving permutations are counted. Pass
19/// `None` for an uncoloured graph.
20///
21/// The count is computed by the shared individualization-refinement engine
22/// (see [`canonical_permutation`](super::canonical_permutation::canonical_permutation)):
23/// `|Aut(G)|` equals the number of leaves of the I-R search tree whose
24/// relabeled-adjacency certificate equals the canonical (lexicographically
25/// maximal) one.
26///
27/// # Scope
28///
29/// Simple graphs (directed or undirected), self-loops allowed, optional
30/// vertex colours. Multi-edges are rejected.
31///
32/// # Errors
33///
34/// Returns an error if `colors` has the wrong length or the graph has
35/// multiple edges between the same pair of vertices.
36///
37/// # Examples
38///
39/// ```
40/// use rust_igraph::{Graph, count_automorphisms};
41///
42/// // The 4-cycle C_4 has the dihedral group of order 2*4 = 8.
43/// let mut c4 = Graph::new(4, false).unwrap();
44/// for (u, v) in [(0, 1), (1, 2), (2, 3), (3, 0)] {
45///     c4.add_edge(u, v).unwrap();
46/// }
47/// assert_eq!(count_automorphisms(&c4, None).unwrap(), 8.0);
48/// ```
49pub fn count_automorphisms(graph: &Graph, colors: Option<&[u32]>) -> IgraphResult<f64> {
50    Ok(canonicalize(graph, colors)?.group_order)
51}
52
53#[cfg(test)]
54#[allow(clippy::cast_precision_loss)] // small factorial counts, exact below 2^52
55mod tests {
56    use super::*;
57
58    fn cycle(n: u32, directed: bool) -> Graph {
59        let mut g = Graph::new(n, directed).expect("graph");
60        for i in 0..n {
61            g.add_edge(i, (i + 1) % n).expect("edge");
62        }
63        g
64    }
65
66    fn complete(n: u32) -> Graph {
67        let mut g = Graph::new(n, false).expect("graph");
68        for u in 0..n {
69            for v in (u + 1)..n {
70                g.add_edge(u, v).expect("edge");
71            }
72        }
73        g
74    }
75
76    fn path(n: u32) -> Graph {
77        let mut g = Graph::new(n, false).expect("graph");
78        for i in 0..n.saturating_sub(1) {
79            g.add_edge(i, i + 1).expect("edge");
80        }
81        g
82    }
83
84    fn petersen() -> Graph {
85        let mut g = Graph::new(10, false).expect("graph");
86        for i in 0..5 {
87            g.add_edge(i, (i + 1) % 5).expect("edge"); // outer cycle
88            g.add_edge(i + 5, ((i + 2) % 5) + 5).expect("edge"); // inner pentagram
89            g.add_edge(i, i + 5).expect("edge"); // spokes
90        }
91        g
92    }
93
94    #[test]
95    fn complete_graph_is_factorial() {
96        let fact = [1u64, 1, 2, 6, 24, 120, 720];
97        for n in 1u32..=6 {
98            let got = count_automorphisms(&complete(n), None).expect("count");
99            assert!((got - fact[n as usize] as f64).abs() < 0.5, "K_{n}");
100        }
101    }
102
103    #[test]
104    fn cycle_is_dihedral() {
105        for n in 3u32..=8 {
106            let got = count_automorphisms(&cycle(n, false), None).expect("count");
107            assert!((got - f64::from(2 * n)).abs() < 0.5, "C_{n}");
108        }
109    }
110
111    #[test]
112    fn path_is_two() {
113        for n in 2u32..=8 {
114            let got = count_automorphisms(&path(n), None).expect("count");
115            assert!((got - 2.0).abs() < 0.5, "path_{n}");
116        }
117    }
118
119    #[test]
120    fn petersen_is_120() {
121        let got = count_automorphisms(&petersen(), None).expect("count");
122        assert!((got - 120.0).abs() < 0.5);
123    }
124
125    #[test]
126    fn directed_cycle_is_n() {
127        // A directed cycle has only its n rotations as automorphisms.
128        for n in 3u32..=8 {
129            let got = count_automorphisms(&cycle(n, true), None).expect("count");
130            assert!((got - f64::from(n)).abs() < 0.5, "directed C_{n}");
131        }
132    }
133
134    #[test]
135    fn empty_graph_is_factorial() {
136        // No edges: every permutation is an automorphism, so |Aut| = n!.
137        let g = Graph::new(4, false).expect("graph");
138        let got = count_automorphisms(&g, None).expect("count");
139        assert!((got - 24.0).abs() < 0.5);
140    }
141
142    #[test]
143    fn null_graph_is_one() {
144        let g = Graph::new(0, false).expect("graph");
145        let got = count_automorphisms(&g, None).expect("count");
146        assert!((got - 1.0).abs() < 0.5);
147    }
148
149    #[test]
150    fn colors_restrict_the_group() {
151        // K_4 has |Aut| = 24; colouring one vertex distinctly fixes it,
152        // leaving S_3 on the other three -> |Aut| = 6.
153        let g = complete(4);
154        let colors = [1u32, 0, 0, 0];
155        let got = count_automorphisms(&g, Some(&colors)).expect("count");
156        assert!((got - 6.0).abs() < 0.5);
157    }
158
159    #[test]
160    fn rejects_multigraph() {
161        let mut g = Graph::new(2, false).expect("graph");
162        g.add_edge(0, 1).expect("edge");
163        g.add_edge(0, 1).expect("edge");
164        assert!(count_automorphisms(&g, None).is_err());
165    }
166
167    #[test]
168    fn rejects_wrong_color_length() {
169        let g = cycle(3, false);
170        let colors = [0u32, 1];
171        assert!(count_automorphisms(&g, Some(&colors)).is_err());
172    }
173}
rust_igraph/algorithms/isomorphism/canonical/count_automorphisms.rs

rust_igraph/algorithms/isomorphism/canonical/
count_automorphisms.rs
