graph_canon/
autom.rs

1use std::os::raw::{c_int, c_void};
2
3use nauty_Traces_sys::{
4    densenauty, empty_graph, groupautomproc, grouplevelproc, groupptr, grouprec, makecosetreps,
5    optionblk, statsblk, FALSE,
6};
7use petgraph::{EdgeType, Graph};
8
9use crate::{canon::bit_adj_to_graph, dense::Nodes, DenseGraph};
10
11#[repr(C)]
12#[derive(Debug)]
13pub struct AutoGroups {
14    /// The automorphism group of the graph.
15    pub data: Vec<Vec<i32>>,
16
17    /// The number of automorphisms of the graph.
18    pub count: usize,
19
20    /// The number of nodes in the graph.
21    pub n: usize,
22
23    /// The canonical labelling of the graph.
24    pub canon: Vec<u64>,
25
26    /// The `Nodes` of the graph.
27    pub nodes: Nodes,
28}
29impl AutoGroups {
30    pub fn new(n: usize, canon: Vec<u64>, nodes: Nodes) -> Self {
31        Self {
32            data: Vec::with_capacity(n * 100),
33            count: 0,
34            n,
35            canon,
36            nodes,
37        }
38    }
39
40    pub fn from_petgraph<Ty: EdgeType>(graph: &Graph<(), (), Ty>) -> Self {
41        let dense = DenseGraph::from_petgraph(graph);
42        Self::from_dense(dense, graph.is_directed())
43    }
44
45    pub fn from_dense(mut dense: DenseGraph, is_directed: bool) -> Self {
46        let mut stats = statsblk::default();
47        let mut options = autom_opts(is_directed);
48        let mut canon = empty_graph(dense.m, dense.n);
49
50        unsafe {
51            densenauty(
52                dense.g.as_mut_ptr(),
53                dense.nodes.lab.as_mut_ptr(),
54                dense.nodes.ptn.as_mut_ptr(),
55                dense.nodes.orbits.as_mut_ptr(),
56                &mut options,
57                &mut stats,
58                dense.m as c_int,
59                dense.n as c_int,
60                canon.as_mut_ptr(),
61            );
62            let mut autogroups = AutoGroups::new(dense.n, canon, dense.nodes);
63            let group = groupptr(FALSE);
64            makecosetreps(group);
65
66            allgroup3(
67                group,
68                Some(writeautom3),
69                &mut autogroups as *mut AutoGroups as *mut c_void,
70            );
71            autogroups
72        }
73    }
74
75    pub fn orbits(&self) -> &[i32] {
76        &self.nodes.orbits
77    }
78
79    pub fn automorphisms(&self) -> &Vec<Vec<i32>> {
80        &self.data
81    }
82
83    pub fn size(&self) -> usize {
84        self.count
85    }
86
87    pub fn n_nodes(&self) -> usize {
88        self.n
89    }
90
91    pub fn canonical(&self) -> &Vec<u64> {
92        &self.canon
93    }
94}
95
96fn autom_opts(is_directed: bool) -> optionblk {
97    optionblk {
98        writeautoms: 0,
99        getcanon: 1,
100        digraph: is_directed.into(),
101        userautomproc: Some(groupautomproc),
102        userlevelproc: Some(grouplevelproc),
103        ..optionblk::default()
104    }
105}
106
107impl<Ty> From<AutoGroups> for Graph<(), (), Ty>
108where
109    Ty: EdgeType,
110{
111    fn from(ag: AutoGroups) -> Self {
112        bit_adj_to_graph(&ag.canon, ag.n * ag.n, ag.n)
113    }
114}
115
116impl<Ty> From<&AutoGroups> for Graph<(), (), Ty>
117where
118    Ty: EdgeType,
119{
120    fn from(ag: &AutoGroups) -> Self {
121        bit_adj_to_graph(&ag.canon, ag.n * ag.n, ag.n)
122    }
123}
124
125// bindgen gets this wrong somehow? linker won't find it.
126extern "C" {
127    pub fn allgroup3(
128        arg1: *mut grouprec,
129        arg2: ::std::option::Option<
130            unsafe extern "C" fn(
131                arg1: *mut ::std::os::raw::c_int,
132                arg2: ::std::os::raw::c_int,
133                arg3: *mut ::std::os::raw::c_int,
134                arg4: *mut ::std::os::raw::c_void,
135            ),
136        >,
137        arg3: *mut ::std::os::raw::c_void,
138    );
139}
140
141#[no_mangle]
142extern "C" fn writeautom3(p: *mut i32, n: i32, _abort: *mut i32, userptr: *mut c_void) {
143    unsafe {
144        // convert void pointer to an AutoGroups pointer
145        let autogroups_ptr = userptr as *mut AutoGroups;
146
147        // convert the raw pointer to a mutable reference
148        let autogroups = &mut *autogroups_ptr;
149
150        // push the node id to the vector
151        autogroups.data.push(Vec::with_capacity(n as usize));
152        for i in 0..n {
153            autogroups.data[autogroups.count].push(*p.offset(i as isize));
154        }
155        autogroups.count += 1;
156    }
157}
158
159#[cfg(test)]
160mod testing {
161    
162    use petgraph::{Directed, Undirected};
163    use super::*;
164
165
166    #[test]
167    fn autogroups_directed() {
168        let e1 = vec![(0, 1), (1, 2), (2, 0)];
169        let e2 = vec![(0, 1), (1, 2), (2, 0), (1, 0), (2, 1), (0, 2)];
170        let g1 = Graph::<(), (), Directed>::from_edges(&e1);
171        let g2 = Graph::<(), (), Directed>::from_edges(&e2);
172        let a1 = AutoGroups::from_petgraph(&g1);
173        let a2 = AutoGroups::from_petgraph(&g2);
174        let expected_1 = vec![
175                vec![0, 1, 2],
176                vec![1, 2, 0],
177                vec![2, 0, 1],
178        ];
179        let expected_2 = vec![
180                vec![0, 1, 2],
181                vec![1, 0, 2],
182                vec![2, 0, 1],
183                vec![0, 2, 1],
184                vec![1, 2, 0],
185                vec![2, 1, 0],
186        ];
187
188        assert_eq!(a1.size(), 3);
189        assert_eq!(a2.size(), 6);
190        assert_eq!(a1.n_nodes(), 3);
191        assert_eq!(a2.n_nodes(), 3);
192
193        for e in expected_1 {
194            assert!(a1.automorphisms().contains(&e));
195        }
196        for e in expected_2 {
197            assert!(a2.automorphisms().contains(&e));
198        }
199    }
200
201    #[test]
202    fn autogroups_undirected() {
203        let e1 = vec![(0, 1), (1, 2), (2, 0)];
204        let e2 = vec![(0, 1), (1, 2), (2, 0), (1, 0), (2, 1), (0, 2)];
205        let g1 = Graph::<(), (), Undirected>::from_edges(&e1);
206        let g2 = Graph::<(), (), Undirected>::from_edges(&e2);
207        let a1 = AutoGroups::from_petgraph(&g1);
208        let a2 = AutoGroups::from_petgraph(&g2);
209        let expected = vec![
210                vec![0, 1, 2],
211                vec![1, 0, 2],
212                vec![2, 0, 1],
213                vec![0, 2, 1],
214                vec![1, 2, 0],
215                vec![2, 1, 0],
216        ];
217
218        assert_eq!(a1.size(), 6);
219        assert_eq!(a2.size(), 6);
220        assert_eq!(a1.n_nodes(), 3);
221        assert_eq!(a2.n_nodes(), 3);
222
223        for e in expected {
224            assert!(a1.automorphisms().contains(&e));
225            assert!(a2.automorphisms().contains(&e));
226        }
227    }
228}
graph_canon/autom.rs

graph_canon/
autom.rs
