rust_igraph/algorithms/motifs/
graph_count.rs

1//! Graph count (ALGO-MO-003) — number of non-isomorphic graphs.
2//!
3//! Counterpart of `igraph_graph_count` in
4//! `references/igraph/src/isomorphism/isoclasses.c:2920`.
5//!
6//! Returns the number of unlabelled simple graphs on n vertices.
7//! Used with isoclass and motif-finder functions.
8//!
9//! OEIS A000088 (undirected), A000273 (directed).
10
11use crate::core::{IgraphError, IgraphResult};
12
13/// Undirected graph counts: number of non-isomorphic simple graphs on n vertices.
14/// Index 0..=14 (OEIS A000088).
15const UNDIRECTED_GRAPH_COUNTS: &[u64] = &[
16    1,
17    1,
18    2,
19    4,
20    11,
21    34,
22    156,
23    1_044,
24    12_346,
25    274_668,
26    12_005_168,
27    1_018_997_864,
28    165_091_172_592,
29    50_502_031_367_952,
30    29_054_155_657_235_488,
31];
32
33/// Directed graph counts: number of non-isomorphic directed simple graphs on n vertices.
34/// Index 0..=9 (OEIS A000273).
35const DIRECTED_GRAPH_COUNTS: &[u64] = &[
36    1,
37    1,
38    3,
39    16,
40    218,
41    9_608,
42    1_540_944,
43    882_033_440,
44    1_793_359_192_848,
45    13_027_956_824_399_552,
46];
47
48/// Return the number of non-isomorphic simple graphs on `n` vertices.
49///
50/// For undirected graphs, supports `n` up to 14.
51/// For directed graphs, supports `n` up to 9.
52///
53/// # Arguments
54///
55/// * `n` — number of vertices.
56/// * `directed` — whether to count directed graphs.
57///
58/// # Errors
59///
60/// Returns an error if `n` is too large for the lookup table.
61///
62/// # Examples
63///
64/// ```
65/// use rust_igraph::graph_count;
66///
67/// // 2 non-isomorphic undirected graphs on 2 vertices: empty and K2
68/// assert_eq!(graph_count(2, false).unwrap(), 2);
69/// // 3 non-isomorphic directed graphs on 2 vertices
70/// assert_eq!(graph_count(2, true).unwrap(), 3);
71/// // 4 undirected graphs on 3 vertices
72/// assert_eq!(graph_count(3, false).unwrap(), 4);
73/// ```
74pub fn graph_count(n: u32, directed: bool) -> IgraphResult<u64> {
75    let idx = n as usize;
76    if directed {
77        if idx >= DIRECTED_GRAPH_COUNTS.len() {
78            return Err(IgraphError::InvalidArgument(format!(
79                "graph_count: n={n} too large for directed graphs (max {})",
80                DIRECTED_GRAPH_COUNTS.len() - 1
81            )));
82        }
83        Ok(DIRECTED_GRAPH_COUNTS[idx])
84    } else {
85        if idx >= UNDIRECTED_GRAPH_COUNTS.len() {
86            return Err(IgraphError::InvalidArgument(format!(
87                "graph_count: n={n} too large for undirected graphs (max {})",
88                UNDIRECTED_GRAPH_COUNTS.len() - 1
89            )));
90        }
91        Ok(UNDIRECTED_GRAPH_COUNTS[idx])
92    }
93}
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98
99    #[test]
100    fn graph_count_undirected_basic() {
101        assert_eq!(graph_count(0, false).unwrap(), 1);
102        assert_eq!(graph_count(1, false).unwrap(), 1);
103        assert_eq!(graph_count(2, false).unwrap(), 2);
104        assert_eq!(graph_count(3, false).unwrap(), 4);
105        assert_eq!(graph_count(4, false).unwrap(), 11);
106        assert_eq!(graph_count(5, false).unwrap(), 34);
107    }
108
109    #[test]
110    fn graph_count_directed_basic() {
111        assert_eq!(graph_count(0, true).unwrap(), 1);
112        assert_eq!(graph_count(1, true).unwrap(), 1);
113        assert_eq!(graph_count(2, true).unwrap(), 3);
114        assert_eq!(graph_count(3, true).unwrap(), 16);
115        assert_eq!(graph_count(4, true).unwrap(), 218);
116    }
117
118    #[test]
119    fn graph_count_undirected_max() {
120        assert!(graph_count(14, false).is_ok());
121        assert!(graph_count(15, false).is_err());
122    }
123
124    #[test]
125    fn graph_count_directed_max() {
126        assert!(graph_count(9, true).is_ok());
127        assert!(graph_count(10, true).is_err());
128    }
129}
rust_igraph/algorithms/motifs/graph_count.rs

rust_igraph/algorithms/motifs/
graph_count.rs
