rust_igraph/algorithms/motifs/isoclass/
mod.rs

1//! Isomorphism class functions (ALGO-MO-004).
2//!
3//! Counterpart of `igraph_isoclass`, `igraph_isoclass_subgraph`, and
4//! `igraph_isoclass_create` in `references/igraph/src/isomorphism/isoclasses.c`.
5//!
6//! Classifies small graphs into isomorphism classes via precomputed lookup
7//! tables. Two graphs have the same isoclass iff they are isomorphic.
8//!
9//! Supported sizes:
10//! - Directed: 3 and 4 vertices (16 and 218 isoclasses respectively)
11//! - Undirected: 3, 4, and 5 vertices (4, 11, and 34 isoclasses)
12
13use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
14
15pub(in crate::algorithms::motifs) mod tables;
16
17/// Determines the isomorphism class of a graph.
18///
19/// The graph must have exactly 3 or 4 vertices (directed), or 3, 4, or 5
20/// vertices (undirected). Multi-edges and self-loops are ignored.
21///
22/// Class 0 is always the empty graph; the highest class is the complete graph.
23///
24/// # Examples
25///
26/// ```
27/// use rust_igraph::{Graph, isoclass};
28///
29/// // Empty directed graph on 3 vertices → class 0
30/// let g = Graph::new(3, true).unwrap();
31/// assert_eq!(isoclass(&g).unwrap(), 0);
32///
33/// // Complete undirected graph on 3 vertices (triangle) → class 3
34/// let mut g = Graph::with_vertices(3);
35/// g.add_edge(0, 1).unwrap();
36/// g.add_edge(1, 2).unwrap();
37/// g.add_edge(0, 2).unwrap();
38/// assert_eq!(isoclass(&g).unwrap(), 3);
39/// ```
40pub fn isoclass(graph: &Graph) -> IgraphResult<u32> {
41    let n = graph.vcount();
42    let directed = graph.is_directed();
43
44    let (arr_idx, arr_code, mul) = get_tables(n, directed)?;
45
46    let mut code: u32 = 0;
47    let ecount = graph.ecount();
48    for eid in 0..ecount {
49        #[allow(clippy::cast_possible_truncation)]
50        let (src, tgt) = graph.edge(eid as u32)?;
51        if src == tgt {
52            continue;
53        }
54        let idx = mul * src + tgt;
55        code |= arr_idx[idx as usize];
56    }
57
58    Ok(arr_code[code as usize].into())
59}
60
61/// Determines the isomorphism class of a subgraph induced by the given vertices.
62///
63/// `vids` must contain 3 or 4 distinct vertex IDs (directed), or 3, 4, or 5
64/// distinct vertex IDs (undirected). Each vertex must exist in the graph.
65///
66/// # Examples
67///
68/// ```
69/// use rust_igraph::{Graph, isoclass_subgraph};
70///
71/// // Build a 5-vertex graph with a triangle on vertices 0,1,2
72/// let mut g = Graph::with_vertices(5);
73/// g.add_edge(0, 1).unwrap();
74/// g.add_edge(1, 2).unwrap();
75/// g.add_edge(0, 2).unwrap();
76/// g.add_edge(3, 4).unwrap();
77///
78/// // Subgraph {0,1,2} is a triangle → class 3 for undirected 3-vertex
79/// assert_eq!(isoclass_subgraph(&g, &[0, 1, 2]).unwrap(), 3);
80/// // Subgraph {0,3,4} has one edge (3-4) → class 1
81/// assert_eq!(isoclass_subgraph(&g, &[0, 3, 4]).unwrap(), 1);
82/// ```
83pub fn isoclass_subgraph(graph: &Graph, vids: &[VertexId]) -> IgraphResult<u32> {
84    let subgraph_size = u32::try_from(vids.len())
85        .map_err(|_| IgraphError::InvalidArgument("isoclass_subgraph: too many vertices".into()))?;
86    let directed = graph.is_directed();
87
88    let (arr_idx, arr_code, mul) = get_tables(subgraph_size, directed)?;
89
90    let n = graph.vcount();
91    for &v in vids {
92        if v >= n {
93            return Err(IgraphError::InvalidArgument(format!(
94                "isoclass_subgraph: vertex {v} out of range (graph has {n} vertices)"
95            )));
96        }
97    }
98
99    let mut code: u32 = 0;
100
101    for (i, &from) in vids.iter().enumerate() {
102        let ecount = graph.ecount();
103        for eid in 0..ecount {
104            #[allow(clippy::cast_possible_truncation)]
105            let (src, tgt) = graph.edge(eid as u32)?;
106            if src != from || src == tgt {
107                continue;
108            }
109            if let Some(to_pos) = vids.iter().position(|&v| v == tgt) {
110                let idx = (mul as usize) * i + to_pos;
111                code |= arr_idx[idx];
112            }
113        }
114    }
115
116    Ok(arr_code[code as usize].into())
117}
118
119/// Creates the canonical representative graph of the given isomorphism class.
120///
121/// The isomorphism class number must be in `[0, graph_count(size, directed) - 1]`.
122///
123/// Supports directed 3-4 and undirected 3-5 vertex graphs.
124///
125/// # Examples
126///
127/// ```
128/// use rust_igraph::{isoclass, isoclass_create};
129///
130/// // Create directed 3-vertex graph of class 5
131/// let g = isoclass_create(3, 5, true).unwrap();
132/// assert_eq!(g.vcount(), 3);
133/// assert!(g.is_directed());
134/// assert_eq!(isoclass(&g).unwrap(), 5);
135///
136/// // Create undirected 4-vertex graph of class 0 (empty graph)
137/// let g = isoclass_create(4, 0, false).unwrap();
138/// assert_eq!(g.ecount(), 0);
139/// ```
140pub fn isoclass_create(size: u32, number: u32, directed: bool) -> IgraphResult<Graph> {
141    let (isographs, classedges, power) = get_create_tables(size, directed)?;
142
143    let graph_count = isographs.len();
144    if number as usize >= graph_count {
145        return Err(IgraphError::InvalidArgument(format!(
146            "isoclass_create: class {number} out of range (only {graph_count} \
147             {} graphs on {size} vertices)",
148            if directed { "directed" } else { "undirected" }
149        )));
150    }
151
152    let mut code = isographs[number as usize];
153    let mut edges: Vec<(VertexId, VertexId)> = Vec::new();
154    let mut current_power = power;
155    let mut pos: usize = 0;
156
157    while code > 0 {
158        if code >= current_power {
159            let src = VertexId::from(classedges[2 * pos]);
160            let tgt = VertexId::from(classedges[2 * pos + 1]);
161            edges.push((src, tgt));
162            code -= current_power;
163        }
164        current_power /= 2;
165        pos += 1;
166    }
167
168    let mut graph = Graph::new(size, directed)?;
169    for (src, tgt) in edges {
170        graph.add_edge(src, tgt)?;
171    }
172
173    Ok(graph)
174}
175
176fn get_tables(n: u32, directed: bool) -> IgraphResult<(&'static [u32], &'static [u8], u32)> {
177    if directed {
178        match n {
179            3 => Ok((&tables::ISOCLASS_3_IDX, &tables::ISOCLASS2_3, 3)),
180            4 => Ok((&tables::ISOCLASS_4_IDX, &tables::ISOCLASS2_4, 4)),
181            _ => Err(IgraphError::InvalidArgument(format!(
182                "isoclass: directed graphs require 3 or 4 vertices (got {n})"
183            ))),
184        }
185    } else {
186        match n {
187            3 => Ok((&tables::ISOCLASS_3U_IDX, &tables::ISOCLASS2_3U, 3)),
188            4 => Ok((&tables::ISOCLASS_4U_IDX, &tables::ISOCLASS2_4U, 4)),
189            5 => Ok((&tables::ISOCLASS_5U_IDX, &tables::ISOCLASS2_5U, 5)),
190            _ => Err(IgraphError::InvalidArgument(format!(
191                "isoclass: undirected graphs require 3, 4, or 5 vertices (got {n})"
192            ))),
193        }
194    }
195}
196
197fn get_create_tables(
198    size: u32,
199    directed: bool,
200) -> IgraphResult<(&'static [u32], &'static [u8], u32)> {
201    if directed {
202        match size {
203            3 => Ok((&tables::ISOGRAPHS_3, &tables::CLASSEDGES_3, 32)),
204            4 => Ok((&tables::ISOGRAPHS_4, &tables::CLASSEDGES_4, 2048)),
205            _ => Err(IgraphError::InvalidArgument(format!(
206                "isoclass_create: directed graphs require size 3 or 4 (got {size})"
207            ))),
208        }
209    } else {
210        match size {
211            3 => Ok((&tables::ISOGRAPHS_3U, &tables::CLASSEDGES_3U, 4)),
212            4 => Ok((&tables::ISOGRAPHS_4U, &tables::CLASSEDGES_4U, 32)),
213            5 => Ok((&tables::ISOGRAPHS_5U, &tables::CLASSEDGES_5U, 512)),
214            _ => Err(IgraphError::InvalidArgument(format!(
215                "isoclass_create: undirected graphs require size 3, 4, or 5 (got {size})"
216            ))),
217        }
218    }
219}
220
221#[cfg(test)]
222mod tests {
223    use super::*;
224
225    #[test]
226    fn isoclass_directed_3_empty() {
227        let g = Graph::new(3, true).unwrap();
228        assert_eq!(isoclass(&g).unwrap(), 0);
229    }
230
231    #[test]
232    fn isoclass_directed_3_complete() {
233        let mut g = Graph::new(3, true).unwrap();
234        for i in 0..3u32 {
235            for j in 0..3u32 {
236                if i != j {
237                    g.add_edge(i, j).unwrap();
238                }
239            }
240        }
241        assert_eq!(isoclass(&g).unwrap(), 15);
242    }
243
244    #[test]
245    fn isoclass_undirected_3_triangle() {
246        let mut g = Graph::with_vertices(3);
247        g.add_edge(0, 1).unwrap();
248        g.add_edge(1, 2).unwrap();
249        g.add_edge(0, 2).unwrap();
250        assert_eq!(isoclass(&g).unwrap(), 3);
251    }
252
253    #[test]
254    fn isoclass_undirected_3_single_edge() {
255        let mut g = Graph::with_vertices(3);
256        g.add_edge(0, 1).unwrap();
257        assert_eq!(isoclass(&g).unwrap(), 1);
258    }
259
260    #[test]
261    fn isoclass_undirected_4_empty() {
262        let g = Graph::with_vertices(4);
263        assert_eq!(isoclass(&g).unwrap(), 0);
264    }
265
266    #[test]
267    fn isoclass_undirected_4_complete() {
268        let mut g = Graph::with_vertices(4);
269        for i in 0..4u32 {
270            for j in (i + 1)..4 {
271                g.add_edge(i, j).unwrap();
272            }
273        }
274        assert_eq!(isoclass(&g).unwrap(), 10);
275    }
276
277    #[test]
278    fn isoclass_undirected_5_empty() {
279        let g = Graph::with_vertices(5);
280        assert_eq!(isoclass(&g).unwrap(), 0);
281    }
282
283    #[test]
284    fn isoclass_undirected_5_complete() {
285        let mut g = Graph::with_vertices(5);
286        for i in 0..5u32 {
287            for j in (i + 1)..5 {
288                g.add_edge(i, j).unwrap();
289            }
290        }
291        assert_eq!(isoclass(&g).unwrap(), 33);
292    }
293
294    #[test]
295    fn isoclass_create_roundtrip_directed_3() {
296        for cls in 0..16u32 {
297            let g = isoclass_create(3, cls, true).unwrap();
298            assert_eq!(isoclass(&g).unwrap(), cls, "class {cls} roundtrip failed");
299        }
300    }
301
302    #[test]
303    fn isoclass_create_roundtrip_directed_4() {
304        for cls in 0..218u32 {
305            let g = isoclass_create(4, cls, true).unwrap();
306            assert_eq!(isoclass(&g).unwrap(), cls, "class {cls} roundtrip failed");
307        }
308    }
309
310    #[test]
311    fn isoclass_create_roundtrip_undirected_3() {
312        for cls in 0..4u32 {
313            let g = isoclass_create(3, cls, false).unwrap();
314            assert_eq!(isoclass(&g).unwrap(), cls, "class {cls} roundtrip failed");
315        }
316    }
317
318    #[test]
319    fn isoclass_create_roundtrip_undirected_4() {
320        for cls in 0..11u32 {
321            let g = isoclass_create(4, cls, false).unwrap();
322            assert_eq!(isoclass(&g).unwrap(), cls, "class {cls} roundtrip failed");
323        }
324    }
325
326    #[test]
327    fn isoclass_create_roundtrip_undirected_5() {
328        for cls in 0..34u32 {
329            let g = isoclass_create(5, cls, false).unwrap();
330            assert_eq!(isoclass(&g).unwrap(), cls, "class {cls} roundtrip failed");
331        }
332    }
333
334    #[test]
335    fn isoclass_create_out_of_range() {
336        assert!(isoclass_create(3, 16, true).is_err());
337        assert!(isoclass_create(4, 218, true).is_err());
338        assert!(isoclass_create(3, 4, false).is_err());
339        assert!(isoclass_create(4, 11, false).is_err());
340        assert!(isoclass_create(5, 34, false).is_err());
341    }
342
343    #[test]
344    fn isoclass_invalid_size() {
345        let g = Graph::new(2, true).unwrap();
346        assert!(isoclass(&g).is_err());
347        let g = Graph::new(5, true).unwrap();
348        assert!(isoclass(&g).is_err());
349        let g = Graph::with_vertices(2);
350        assert!(isoclass(&g).is_err());
351        let g = Graph::with_vertices(6);
352        assert!(isoclass(&g).is_err());
353    }
354
355    #[test]
356    fn isoclass_self_loops_ignored() {
357        let mut g = Graph::new(3, true).unwrap();
358        g.add_edge(0, 0).unwrap();
359        g.add_edge(0, 1).unwrap();
360        let mut g2 = Graph::new(3, true).unwrap();
361        g2.add_edge(0, 1).unwrap();
362        assert_eq!(isoclass(&g).unwrap(), isoclass(&g2).unwrap());
363    }
364
365    #[test]
366    fn isoclass_subgraph_basic() {
367        let mut g = Graph::with_vertices(5);
368        g.add_edge(0, 1).unwrap();
369        g.add_edge(1, 2).unwrap();
370        g.add_edge(0, 2).unwrap();
371        g.add_edge(3, 4).unwrap();
372
373        // Triangle subgraph
374        assert_eq!(isoclass_subgraph(&g, &[0, 1, 2]).unwrap(), 3);
375        // Single edge subgraph
376        assert_eq!(isoclass_subgraph(&g, &[0, 3, 4]).unwrap(), 1);
377        // Empty subgraph
378        assert_eq!(isoclass_subgraph(&g, &[0, 3, 2]).unwrap(), 1);
379    }
380
381    #[test]
382    fn isoclass_subgraph_invalid_vertex() {
383        let g = Graph::with_vertices(3);
384        assert!(isoclass_subgraph(&g, &[0, 1, 5]).is_err());
385    }
386}
rust_igraph/algorithms/motifs/isoclass/mod.rs

rust_igraph/algorithms/motifs/isoclass/
mod.rs
