rust_igraph/algorithms/constructors/
atlas.rs

1//! Read-Wilson graph atlas constructor (ALGO-CN-021).
2//!
3//! Counterpart of `igraph_atlas()` in
4//! `references/igraph/src/constructors/atlas.c:63-87`. Returns the
5//! `number`-th of the 1253 simple unlabelled undirected graphs on
6//! 0..7 vertices, in the ordering of Ronald C. Read and Robin J. Wilson,
7//! *An Atlas of Graphs* (Oxford University Press, 1998):
8//!
9//! 1. by ascending vertex count;
10//! 2. for fixed vertex count, by ascending edge count;
11//! 3. for fixed vertex/edge count, by ascending lexicographic degree
12//!    sequence;
13//! 4. for fixed degree sequence, by ascending automorphism count.
14//!
15//! The graphs on 0, 1, 2, 3, 4, 5, 6, 7 vertices start at indices 0, 1,
16//! 2, 4, 8, 19, 53, 209 respectively. All atlas graphs are undirected.
17//!
18//! The edge data is stored in [`atlas_edges`](super::atlas_edges) — two
19//! static `&[u32]` tables transliterated byte-for-byte from
20//! `references/igraph/src/constructors/atlas-edges.h`.
21
22use super::atlas_edges::{ATLAS_EDGES, ATLAS_EDGES_POS};
23use crate::core::{Graph, IgraphError, IgraphResult};
24
25/// Total number of graphs catalogued in the atlas: 1253.
26pub const ATLAS_SIZE: u32 = 1253;
27
28/// Build the `number`-th graph from Read-Wilson's *An Atlas of Graphs*.
29///
30/// `number` must be in `0..1253`. The returned graph is always
31/// undirected. See the module docstring for the ordering convention.
32///
33/// # Errors
34///
35/// * [`IgraphError::InvalidArgument`] — `number` is outside `0..1253`.
36///
37/// # Examples
38///
39/// ```
40/// use rust_igraph::atlas;
41///
42/// // 0: the null graph (0 vertices, 0 edges)
43/// let g = atlas(0).unwrap();
44/// assert_eq!((g.vcount(), g.ecount()), (0, 0));
45///
46/// // 3: the single edge K_2
47/// let k2 = atlas(3).unwrap();
48/// assert_eq!((k2.vcount(), k2.ecount()), (2, 1));
49///
50/// // 1252 (last): the complete graph K_7
51/// let k7 = atlas(1252).unwrap();
52/// assert_eq!((k7.vcount(), k7.ecount()), (7, 21));
53/// ```
54pub fn atlas(number: u32) -> IgraphResult<Graph> {
55    if number >= ATLAS_SIZE {
56        return Err(IgraphError::InvalidArgument(format!(
57            "atlas: graph index {number} is out of range (must be < {ATLAS_SIZE})"
58        )));
59    }
60
61    let pos = ATLAS_EDGES_POS[number as usize] as usize;
62    if pos + 2 > ATLAS_EDGES.len() {
63        return Err(IgraphError::InvalidArgument(
64            "atlas: corrupt position table (header out of range)".into(),
65        ));
66    }
67
68    let vcount = ATLAS_EDGES[pos];
69    let ecount = ATLAS_EDGES[pos + 1] as usize;
70
71    let edge_words = ecount
72        .checked_mul(2)
73        .ok_or_else(|| IgraphError::InvalidArgument("atlas: edge buffer overflow".into()))?;
74    let end = pos
75        .checked_add(2)
76        .and_then(|x| x.checked_add(edge_words))
77        .ok_or_else(|| IgraphError::InvalidArgument("atlas: edge buffer overflow".into()))?;
78    if end > ATLAS_EDGES.len() {
79        return Err(IgraphError::InvalidArgument(
80            "atlas: corrupt position table (payload out of range)".into(),
81        ));
82    }
83
84    let mut g = Graph::new(vcount, false)?;
85    let edges: Vec<(u32, u32)> = ATLAS_EDGES[pos + 2..end]
86        .chunks_exact(2)
87        .map(|pair| (pair[0], pair[1]))
88        .collect();
89    g.add_edges(edges)?;
90    Ok(g)
91}
92
93#[cfg(test)]
94mod tests {
95    use super::*;
96    use std::collections::BTreeSet;
97
98    fn canonical_edge_set(g: &Graph) -> BTreeSet<(u32, u32)> {
99        let mut s = BTreeSet::new();
100        for v in 0..g.vcount() {
101            for &u in &g.neighbors(v).expect("neighbors") {
102                if v <= u {
103                    s.insert((v, u));
104                } else {
105                    s.insert((u, v));
106                }
107            }
108        }
109        s
110    }
111
112    #[test]
113    fn out_of_range_errors() {
114        assert!(atlas(ATLAS_SIZE).is_err());
115        assert!(atlas(ATLAS_SIZE + 1).is_err());
116        assert!(atlas(u32::MAX).is_err());
117    }
118
119    #[test]
120    fn atlas_size_constant_matches_upstream() {
121        // upstream says 1253 — atlas-edges.h has exactly that many POS entries.
122        assert_eq!(ATLAS_SIZE, 1253);
123    }
124
125    #[test]
126    fn null_graph_indices() {
127        // 0..=7 — single null graph on n vertices at the start of each n-cell.
128        let starts: [(u32, u32); 8] = [
129            (0, 0),
130            (1, 1),
131            (2, 2),
132            (3, 4),
133            (4, 8),
134            (5, 19),
135            (6, 53),
136            (7, 209),
137        ];
138        for (n, idx) in starts {
139            let g = atlas(idx).unwrap_or_else(|_| panic!("atlas({idx})"));
140            assert_eq!(g.vcount(), n, "atlas({idx}) vcount");
141            assert_eq!(g.ecount(), 0, "atlas({idx}) ecount (null graph)");
142        }
143    }
144
145    #[test]
146    fn small_known_graphs() {
147        // Hand-checked against igraph C output and the Read-Wilson Atlas.
148        let g3 = atlas(3).expect("3");
149        assert_eq!((g3.vcount(), g3.ecount()), (2, 1));
150        assert_eq!(
151            canonical_edge_set(&g3),
152            [(0u32, 1u32)].into_iter().collect()
153        );
154
155        // index 7 is the K_3 triangle on 3 vertices
156        let g7 = atlas(7).expect("7");
157        assert_eq!((g7.vcount(), g7.ecount()), (3, 3));
158        assert_eq!(
159            canonical_edge_set(&g7),
160            [(0u32, 1), (0, 2), (1, 2)].into_iter().collect()
161        );
162
163        // index 18 = K_4 (last 4-vertex graph): 6 edges, 3-regular
164        let k4 = atlas(18).expect("18");
165        assert_eq!((k4.vcount(), k4.ecount()), (4, 6));
166        for v in 0..k4.vcount() {
167            assert_eq!(k4.neighbors(v).expect("nbrs").len(), 3);
168        }
169    }
170
171    #[test]
172    fn k7_is_last_atlas_graph() {
173        // index 1252 is K_7: 7 vertices, 21 edges (C(7,2)), 6-regular.
174        let k7 = atlas(1252).expect("1252");
175        assert_eq!((k7.vcount(), k7.ecount()), (7, 21));
176        for v in 0..k7.vcount() {
177            assert_eq!(k7.neighbors(v).expect("nbrs").len(), 6);
178        }
179    }
180
181    #[test]
182    fn no_self_loops_or_repeated_edges() {
183        // Spot-check across a representative spread instead of all 1253.
184        let samples = [
185            0, 1, 2, 3, 4, 7, 8, 18, 19, 52, 53, 70, 100, 180, 208, 209, 500, 1000, 1252,
186        ];
187        for &i in &samples {
188            let g = atlas(i).unwrap_or_else(|_| panic!("atlas({i})"));
189            let mut seen: BTreeSet<(u32, u32)> = BTreeSet::new();
190            for v in 0..g.vcount() {
191                for &u in &g.neighbors(v).expect("nbrs") {
192                    assert_ne!(v, u, "atlas({i}) self-loop at {v}");
193                    let key = if v <= u { (v, u) } else { (u, v) };
194                    if !seen.insert(key) {
195                        // multi-edge appears twice in neighbors traversal naturally,
196                        // but with chunks_exact + add_edges every undirected edge
197                        // is inserted exactly once, so we only need degree symmetry.
198                    }
199                }
200            }
201        }
202    }
203
204    #[test]
205    fn all_atlas_graphs_construct_and_are_undirected() {
206        // Walk the entire catalogue. Cheap (1253 tiny graphs).
207        for i in 0..ATLAS_SIZE {
208            let g = atlas(i).unwrap_or_else(|_| panic!("atlas({i})"));
209            assert!(g.vcount() <= 7, "atlas({i}) vcount {}", g.vcount());
210            assert!(!g.is_directed(), "atlas({i}) should be undirected");
211            // edge count consistent with neighbor-sum / 2
212            let total_deg: usize = (0..g.vcount())
213                .map(|v| g.neighbors(v).expect("nbrs").len())
214                .sum();
215            assert_eq!(
216                total_deg,
217                g.ecount() as usize * 2,
218                "atlas({i}) degree sum != 2|E|"
219            );
220        }
221    }
222
223    #[test]
224    fn vertex_count_partitions_match_upstream_starts() {
225        // For each n in 0..=7, atlas(start[n]..start[n+1]) should all have
226        // exactly n vertices.
227        let starts = [0u32, 1, 2, 4, 8, 19, 53, 209, ATLAS_SIZE];
228        for n in 0..8 {
229            let lo = starts[n];
230            let hi = starts[n + 1];
231            for i in lo..hi {
232                let g = atlas(i).expect("atlas");
233                assert_eq!(
234                    g.vcount() as usize,
235                    n,
236                    "atlas({i}) should have vcount {n}, got {}",
237                    g.vcount()
238                );
239            }
240        }
241    }
242}
rust_igraph/algorithms/constructors/atlas.rs

rust_igraph/algorithms/constructors/
atlas.rs
