nauty_Traces_sys/
lib.rs

1#![doc(html_root_url = "https://docs.rs/nauty-Traces-sys/0.10.0")]
2#![allow(non_camel_case_types)]
3#![allow(non_snake_case)]
4mod bindings;
5
6use ::std::os::raw::c_int;
7pub use bindings::*;
8
9// bindgen doesn't get the types right for the following constants
10pub const FALSE: boolean = bindings::FALSE as boolean;
11pub const TRUE: boolean = bindings::TRUE as boolean;
12pub const CONSOLWIDTH: c_int = bindings::CONSOLWIDTH as c_int;
13
14pub const MTOOBIG: c_int = bindings::MTOOBIG as c_int;
15pub const NTOOBIG: c_int = bindings::NTOOBIG as c_int;
16pub const CANONGNIL: c_int = bindings::CANONGNIL as c_int;
17pub const NAUABORTED: c_int = bindings::NAUABORTED as c_int;
18pub const NAUKILLED: c_int = bindings::NAUKILLED as c_int;
19
20// bindgen gets this wrong somehow? linker won't find it.
21#[allow(non_upper_case_globals)]
22pub const bit: [set; set::BITS as usize] = {
23    let mut arr = [0; set::BITS as usize];
24    let mut val = 1;
25    let mut num = 0;
26    while num < arr.len() {
27        let idx = arr.len() - num - 1;
28        arr[idx] = val;
29        val <<= 1;
30        num += 1;
31    }
32    arr
33};
34
35pub fn SETWORDSNEEDED(n: usize) -> usize {
36    n.div_ceil(WORDSIZE as _)
37}
38
39impl std::default::Default for optionblk {
40    /// Default options for undirected graphs, equivalent to nauty's DEFAULTOPTIONS_GRAPH.
41    fn default() -> Self {
42        optionblk {
43            getcanon: 0,
44            digraph: FALSE,
45            writeautoms: FALSE,
46            writemarkers: FALSE,
47            defaultptn: TRUE,
48            cartesian: FALSE,
49            linelength: CONSOLWIDTH,
50            outfile: std::ptr::null_mut(),
51            userrefproc: None,
52            userautomproc: None,
53            userlevelproc: None,
54            usernodeproc: None,
55            usercanonproc: None,
56            invarproc: None,
57            tc_level: 100,
58            mininvarlevel: 0,
59            maxinvarlevel: 1,
60            invararg: 0,
61            dispatch: &raw mut dispatch_graph,
62            schreier: FALSE,
63            extra_options: std::ptr::null_mut(),
64        }
65    }
66}
67
68impl optionblk {
69    /// Default options for directed graphs, equivalent to nauty's DEFAULTOPTIONS_DIGRAPH.
70    pub fn default_digraph() -> Self {
71        optionblk {
72            digraph: TRUE,
73            invarproc: Some(adjacencies),
74            maxinvarlevel: 999,
75            ..Self::default()
76        }
77    }
78
79    /// Default options for undirected sparse graphs, equivalent to nauty's DEFAULTOPTIONS_SPARSEGRAPH.
80    pub fn default_sparse() -> Self {
81        optionblk {
82            dispatch: &raw mut dispatch_sparse,
83            ..Self::default()
84        }
85    }
86
87    /// Default options for directed sparse graphs, equivalent to nauty's DEFAULTOPTIONS_SPARSEDIGRAPH.
88    pub fn default_sparse_digraph() -> Self {
89        optionblk {
90            invarproc: Some(adjacencies_sg),
91            dispatch: &raw mut dispatch_sparse,
92            ..Self::default_digraph()
93        }
94    }
95}
96
97impl std::default::Default for TracesOptions {
98    /// Default options for undirected graphs, equivalent to Traces' DEFAULTOPTIONS_TRACES.
99    fn default() -> Self {
100        TracesOptions {
101            getcanon: FALSE,
102            writeautoms: FALSE,
103            cartesian: FALSE,
104            digraph: FALSE,
105            defaultptn: TRUE,
106            linelength: 0,
107            outfile: std::ptr::null_mut(),
108            strategy: 0,
109            verbosity: 0,
110            generators: std::ptr::null_mut(),
111            userautomproc: None,
112            reserved: std::ptr::null_mut(),
113            weighted: FALSE,
114        }
115    }
116}
117
118#[allow(clippy::derivable_impls)]
119impl std::default::Default for statsblk {
120    fn default() -> Self {
121        statsblk {
122            canupdates: Default::default(),
123            errstatus: Default::default(),
124            grpsize1: Default::default(),
125            grpsize2: Default::default(),
126            invapplics: Default::default(),
127            invarsuclevel: Default::default(),
128            invsuccesses: Default::default(),
129            maxlevel: Default::default(),
130            numbadleaves: Default::default(),
131            numgenerators: Default::default(),
132            numnodes: Default::default(),
133            numorbits: Default::default(),
134            tctotal: Default::default(),
135        }
136    }
137}
138
139#[allow(clippy::derivable_impls)]
140impl std::default::Default for TracesStats {
141    fn default() -> Self {
142        TracesStats {
143            grpsize1: Default::default(),
144            grpsize2: Default::default(),
145            numgenerators: Default::default(),
146            numorbits: Default::default(),
147            treedepth: Default::default(),
148            canupdates: Default::default(),
149            errstatus: Default::default(),
150            numnodes: Default::default(),
151            interrupted: Default::default(),
152            peaknodes: Default::default(),
153        }
154    }
155}
156
157/// Create an empty graph with `n` vertices.
158/// `m` should be set to `SETWORDSNEEDED(n)`.
159pub fn empty_graph(m: usize, n: usize) -> Vec<graph> {
160    vec![0; m * n]
161}
162
163/// Create an uninitialised graph with `n` vertices.
164/// `m` should be set to `SETWORDSNEEDED(n)`.
165pub fn uninit_graph(m: usize, n: usize) -> Vec<graph> {
166    Vec::with_capacity(m * n)
167}
168
169pub fn ADDONEEDGE(g: &mut [graph], v: usize, w: usize, m: usize) {
170    ADDONEARC(g, v, w, m);
171    ADDONEARC(g, w, v, m);
172}
173
174pub fn ADDONEARC(g: &mut [graph], v: usize, w: usize, m: usize) {
175    ADDELEMENT(GRAPHROW(g as &mut [set], v, m), w);
176}
177
178pub fn GRAPHROW(g: &mut [set], v: usize, m: usize) -> &mut [set] {
179    &mut g[m * v..]
180}
181
182pub fn ADDELEMENT(setadd: &mut [set], pos: usize) {
183    setadd[SETWD(pos)] |= bit[SETBT(pos)]
184}
185
186pub fn SETWD(pos: usize) -> usize {
187    pos / (WORDSIZE as usize)
188}
189
190pub fn SETBT(pos: usize) -> usize {
191    pos & (WORDSIZE as usize - 1)
192}
193
194#[cfg(feature = "libc")]
195pub fn DYNFREE<T>(ptr: &mut *mut T, len: &mut usize) {
196    unsafe {
197        libc::free(*ptr as *mut libc::c_void);
198    }
199    *ptr = std::ptr::null_mut();
200    *len = 0;
201}
202
203#[cfg(feature = "libc")]
204pub fn SG_FREE(sg: &mut sparsegraph) {
205    DYNFREE(&mut sg.v, &mut sg.vlen);
206    DYNFREE(&mut sg.d, &mut sg.dlen);
207    DYNFREE(&mut sg.e, &mut sg.elen);
208}
209
210impl std::default::Default for sparsegraph {
211    fn default() -> Self {
212        sparsegraph {
213            nde: Default::default(),
214            v: std::ptr::null_mut(),
215            nv: Default::default(),
216            d: std::ptr::null_mut(),
217            e: std::ptr::null_mut(),
218            w: std::ptr::null_mut(),
219            vlen: Default::default(),
220            dlen: Default::default(),
221            elen: Default::default(),
222            wlen: Default::default(),
223        }
224    }
225}
226
227/// Sparse graph with allocated memory
228#[derive(Debug, Default, Clone)]
229pub struct SparseGraph {
230    pub v: Vec<usize>,
231    pub d: Vec<c_int>,
232    pub e: Vec<c_int>,
233}
234
235impl SparseGraph {
236    /// Create a sparse graph with the given number of vertices and edges
237    pub fn new(vertices: usize, edges: usize) -> Self {
238        SparseGraph {
239            v: vec![0; vertices],
240            d: vec![0; vertices],
241            e: vec![0; edges],
242        }
243    }
244}
245
246impl<'a> std::convert::From<&'a mut SparseGraph> for sparsegraph {
247    fn from(g: &'a mut SparseGraph) -> Self {
248        sparsegraph {
249            nv: g.v.len() as c_int,
250            nde: g.e.len(),
251            v: g.v.as_mut_ptr(),
252            d: g.d.as_mut_ptr(),
253            e: g.e.as_mut_ptr(),
254            w: std::ptr::null_mut(),
255            vlen: g.v.len(),
256            dlen: g.d.len(),
257            elen: g.e.len(),
258            wlen: 0,
259        }
260    }
261}
262
263#[cfg(test)]
264mod tests {
265
266    use super::*;
267    use ::std::os::raw::c_int;
268
269    // test nauty examples nautyex2.c to nautyex10.c
270
271    #[test]
272    fn nautyex2() {
273        let orders = [1., 2., 6., 8., 10., 12., 14., 16., 18., 20.];
274
275        let mut options = optionblk::default();
276        // options.writeautoms = TRUE;
277        let mut stats = statsblk::default();
278
279        for (n, order) in orders.iter().enumerate() {
280            let n = n + 1;
281            let m = SETWORDSNEEDED(n);
282
283            unsafe {
284                nauty_check(
285                    WORDSIZE as c_int,
286                    m as c_int,
287                    n as c_int,
288                    NAUTYVERSIONID as c_int,
289                );
290            }
291
292            let mut lab = vec![0; n];
293            let mut ptn = vec![0; n];
294            let mut orbits = vec![0; n];
295            let mut g = empty_graph(m, n);
296            for v in 0..n {
297                ADDONEEDGE(&mut g, v, (v + 1) % n, m);
298            }
299            unsafe {
300                densenauty(
301                    g.as_mut_ptr(),
302                    lab.as_mut_ptr(),
303                    ptn.as_mut_ptr(),
304                    orbits.as_mut_ptr(),
305                    &mut options,
306                    &mut stats,
307                    m as c_int,
308                    n as c_int,
309                    std::ptr::null_mut(),
310                );
311            }
312            assert_eq!(stats.grpsize1, *order);
313            assert_eq!(stats.grpsize2, 0);
314        }
315    }
316
317    extern "C" fn writeautom(p: *mut i32, n: i32) {
318        for i in 0..n {
319            print!(" {:2}", unsafe { *p.offset(i as isize) })
320        }
321        println!()
322    }
323
324    #[test]
325    fn nautyex3() {
326        // nautyex3.c nauty example
327
328        let mut options = optionblk::default();
329        let mut stats = statsblk::default();
330
331        /* The following cause nauty to call two procedures which
332        store the group information as nauty runs. */
333
334        options.userautomproc = Some(groupautomproc);
335        options.userlevelproc = Some(grouplevelproc);
336
337        for n in 1..20 {
338            let m = SETWORDSNEEDED(n);
339            unsafe {
340                nauty_check(
341                    WORDSIZE as c_int,
342                    m as c_int,
343                    n as c_int,
344                    NAUTYVERSIONID as c_int,
345                );
346            }
347
348            let mut g = empty_graph(n, m);
349            let mut lab = vec![0; n];
350            let mut ptn = vec![0; n];
351            let mut orbits = vec![0; n];
352
353            for v in 0..n {
354                ADDONEEDGE(&mut g, v, (v + 1) % n, m)
355            }
356
357            println!("Automorphisms of C[{}]:", n);
358
359            unsafe {
360                densenauty(
361                    g.as_mut_ptr(),
362                    lab.as_mut_ptr(),
363                    ptn.as_mut_ptr(),
364                    orbits.as_mut_ptr(),
365                    &mut options,
366                    &mut stats,
367                    m as c_int,
368                    n as c_int,
369                    std::ptr::null_mut(),
370                );
371
372                /* Get a pointer to the structure in which the group information
373                has been stored.  If you use TRUE as an argument, the
374                structure will be "cut loose" so that it won't be used
375                again the next time nauty() is called.  Otherwise, as
376                here, the same structure is used repeatedly. */
377
378                let group = groupptr(FALSE);
379
380                /* Expand the group structure to include a full set of coset
381                representatives at every level.  This step is necessary
382                if allgroup() is to be called. */
383
384                makecosetreps(group);
385
386                /* Call the procedure writeautom() for every element of the group.
387                The first call is always for the identity. */
388
389                allgroup(group, Some(writeautom));
390            }
391        }
392    }
393
394    #[test]
395    fn nautyex4() {
396        let n_range = 1..20;
397
398        use ::std::os::raw::c_int;
399        let mut options = optionblk::default_sparse();
400        let mut stats = statsblk::default();
401        // options.writeautoms = TRUE;
402
403        for n in n_range {
404            let m = SETWORDSNEEDED(n);
405
406            unsafe {
407                nauty_check(
408                    WORDSIZE as c_int,
409                    m as c_int,
410                    n as c_int,
411                    NAUTYVERSIONID as c_int,
412                );
413            }
414
415            let mut lab = vec![0; n];
416            let mut ptn = vec![0; n];
417            let mut orbits = vec![0; n];
418
419            /* SG_ALLOC makes sure that the v,d,e fields of a sparse graph
420            structure point to arrays that are large enough.  This only
421            works if the structure has been initialised. */
422
423            let mut sg = SparseGraph::new(
424                n,     /* Number of vertices */
425                2 * n, /* Number of directed edges */
426            );
427
428            for i in 0..n {
429                sg.v[i] = 2 * i as usize;
430                sg.d[i] = 2;
431                sg.e[2 * i] = ((i + n - 1) % n) as c_int; /* edge i->i-1 */
432                sg.e[2 * i + 1] = ((i + n + 1) % n) as c_int; /* edge i->i+1 */
433            }
434
435            println!("Generators for Aut(C[{}]):", n);
436            unsafe {
437                sparsenauty(
438                    &mut (&mut sg).into(),
439                    lab.as_mut_ptr(),
440                    ptn.as_mut_ptr(),
441                    orbits.as_mut_ptr(),
442                    &mut options,
443                    &mut stats,
444                    std::ptr::null_mut(),
445                );
446            }
447
448            println!("Automorphism group size = {}", stats.grpsize1);
449            if n < 3 {
450                assert_eq!(stats.grpsize1, n as f64)
451            } else {
452                assert_eq!(stats.grpsize1, 2. * n as f64)
453            }
454            println!();
455        }
456    }
457
458    #[test]
459    fn nautyex5() {
460        let n_range = (2..20).step_by(2);
461
462        let mut options = optionblk::default_sparse();
463        let mut stats = statsblk::default();
464
465        let mut cg1 = sparsegraph::default();
466        let mut cg2 = sparsegraph::default();
467
468        /* Select option for canonical labelling */
469        options.getcanon = TRUE;
470
471        for n in n_range {
472            let m = SETWORDSNEEDED(n);
473            unsafe {
474                nauty_check(
475                    WORDSIZE as c_int,
476                    m as c_int,
477                    n as c_int,
478                    NAUTYVERSIONID as c_int,
479                );
480            }
481            let mut lab1 = vec![0; n];
482            let mut lab2 = vec![0; n];
483            let mut ptn = vec![0; n];
484            let mut orbits = vec![0; n];
485            let mut map = vec![0; n];
486
487            /* Now make the first graph */
488
489            let mut sg1 = SparseGraph::new(
490                n,     /* Number of vertices */
491                3 * n, /* Number of directed edges */
492            );
493
494            for i in 0..n {
495                sg1.v[i] = (3 * i) as usize; /* Position of vertex i in v array */
496                sg1.d[i] = 3; /* Degree of vertex i */
497            }
498
499            for i in (0..n).step_by(2) {
500                sg1.e[sg1.v[i] as usize] = (i + 1) as c_int;
501                sg1.e[sg1.v[i + 1] as usize] = i as c_int;
502            }
503
504            for i in 0..n - 2 {
505                /* Clockwise edges */
506                sg1.e[(sg1.v[i] + 1) as usize] = (i + 2) as c_int;
507            }
508            sg1.e[(sg1.v[n - 2] + 1) as usize] = 1;
509            sg1.e[(sg1.v[n - 1] + 1) as usize] = 0;
510
511            for i in 2..n {
512                /* Anticlockwise edges */
513                sg1.e[(sg1.v[i] + 2) as usize] = (i - 2) as c_int;
514            }
515            sg1.e[(sg1.v[1] + 2) as usize] = (n - 2) as c_int;
516            sg1.e[(sg1.v[0] + 2) as usize] = (n - 1) as c_int;
517
518            /* Now make the second graph */
519
520            let mut sg2 = SparseGraph::new(
521                n,     /* Number of vertices */
522                3 * n, /* Number of directed edges */
523            );
524
525            // // this is redundant already in nautyex5.c
526            // for i in 0..n {
527            //     sg2.v[i] = (3*i) as usize;
528            //     sg2.d[i] = 3;
529            // }
530
531            for i in 0..n {
532                sg2.v[i] = (3 * i) as usize;
533                sg2.d[i] = 3;
534                sg2.e[sg2.v[i] as usize] = ((i + 1) % n) as c_int; /* Clockwise */
535                sg2.e[(sg2.v[i] + 1) as usize] = ((i + n - 1) % n) as c_int; /* Anti-clockwise */
536                sg2.e[(sg2.v[i] + 2) as usize] = ((i + n / 2) % n) as c_int; /* Diagonals */
537            }
538
539            /* Label sg1, result in cg1 and labelling in lab1; similarly sg2.
540            It is not necessary to pre-allocate space in cg1 and cg2, but
541            they have to be initialised as we did above.  */
542            unsafe {
543                sparsenauty(
544                    &mut (&mut sg1).into(),
545                    lab1.as_mut_ptr(),
546                    ptn.as_mut_ptr(),
547                    orbits.as_mut_ptr(),
548                    &mut options,
549                    &mut stats,
550                    &mut cg1,
551                );
552                sparsenauty(
553                    &mut (&mut sg2).into(),
554                    lab2.as_mut_ptr(),
555                    ptn.as_mut_ptr(),
556                    orbits.as_mut_ptr(),
557                    &mut options,
558                    &mut stats,
559                    &mut cg2,
560                );
561            }
562
563            /* Compare canonically labelled graphs */
564            let are_same = unsafe { aresame_sg(&mut cg1, &mut cg2) } == TRUE;
565            assert!(are_same);
566            if are_same {
567                println!("Isomorphic");
568                if n <= 1000 {
569                    /* Write the isomorphism.  For each i, vertex lab1[i]
570                    of sg1 maps onto vertex lab2[i] of sg2.  We compute
571                    the map in order of labelling because it looks better. */
572
573                    for i in 0..n {
574                        map[lab1[i] as usize] = lab2[i];
575                    }
576                    for i in 0..n {
577                        print!(" {}-{}", i, map[i])
578                    }
579                    println!()
580                }
581            } else {
582                println!("Not isomorphic.");
583            }
584        }
585    }
586
587    #[test]
588    fn nautyex6() {
589        let n_range = (2..20).step_by(2);
590
591        let mut options = optionblk::default();
592        let mut stats = statsblk::default();
593
594        /* Select option for canonical labelling */
595
596        options.getcanon = TRUE;
597
598        for n in n_range {
599            let m = SETWORDSNEEDED(n);
600            unsafe {
601                nauty_check(
602                    WORDSIZE as c_int,
603                    m as c_int,
604                    n as c_int,
605                    NAUTYVERSIONID as c_int,
606                );
607            }
608
609            let mut lab1 = vec![0; n];
610            let mut lab2 = vec![0; n];
611            let mut ptn = vec![0; n];
612            let mut orbits = vec![0; n];
613            let mut map = vec![0; n];
614            let mut cg1 = empty_graph(n, m);
615            let mut cg2 = empty_graph(n, m);
616
617            /* Now make the first graph */
618            /* ADDEDGE() is defined above */
619            let mut g1 = empty_graph(m, n);
620
621            for i in 0..n - 2 {
622                ADDONEEDGE(&mut g1, i, i + 2, m)
623            }
624            ADDONEEDGE(&mut g1, n - 2, 1, m);
625            ADDONEEDGE(&mut g1, n - 1, 0, m);
626            for i in (0..n).step_by(2) {
627                ADDONEEDGE(&mut g1, i, i + 1, m)
628            }
629
630            /* Now make the second graph */
631
632            let mut g2 = empty_graph(m, n);
633            for i in 0..n - 1 {
634                ADDONEEDGE(&mut g2, i, i + 1, m)
635            }
636            ADDONEEDGE(&mut g2, n - 1, 0, m);
637            for i in 0..n / 2 {
638                ADDONEEDGE(&mut g2, i, i + n / 2, m);
639            }
640
641            /* Label g1, result in cg1 and labelling in lab1; similarly g2.
642            It is not necessary to pre-allocate space in cg1 and cg2, but
643            they have to be initialised as we did above.  */
644
645            unsafe {
646                densenauty(
647                    g1.as_mut_ptr(),
648                    lab1.as_mut_ptr(),
649                    ptn.as_mut_ptr(),
650                    orbits.as_mut_ptr(),
651                    &mut options,
652                    &mut stats,
653                    m as c_int,
654                    n as c_int,
655                    cg1.as_mut_ptr(),
656                );
657
658                densenauty(
659                    g2.as_mut_ptr(),
660                    lab2.as_mut_ptr(),
661                    ptn.as_mut_ptr(),
662                    orbits.as_mut_ptr(),
663                    &mut options,
664                    &mut stats,
665                    m as c_int,
666                    n as c_int,
667                    cg2.as_mut_ptr(),
668                );
669            }
670
671            /* Compare canonically labelled graphs */
672            assert_eq!(cg1, cg2);
673            if cg1 == cg2 {
674                println!("Isomorphic.");
675                if n <= 1000 {
676                    /* Write the isomorphism.  For each i, vertex lab1[i]
677                    of sg1 maps onto vertex lab2[i] of sg2.  We compute
678                    the map in order of labelling because it looks better. */
679
680                    for i in 0..n {
681                        map[lab1[i] as usize] = lab2[i];
682                    }
683                    for i in 0..n {
684                        print!(" {}-{}", i, map[i]);
685                    }
686                    println!()
687                }
688            }
689        }
690    }
691
692    #[test]
693    fn nautyex7() {
694        let n_range = (2..20).step_by(2);
695
696        let mut options = TracesOptions::default();
697        let mut stats = TracesStats::default();
698
699        /* Declare and initialize sparse graph structures */
700        let mut cg1 = sparsegraph::default();
701        let mut cg2 = sparsegraph::default();
702
703        /* Select option for canonical labelling */
704
705        options.getcanon = TRUE;
706
707        for n in n_range {
708            let m = SETWORDSNEEDED(n);
709            unsafe {
710                nauty_check(
711                    WORDSIZE as c_int,
712                    m as c_int,
713                    n as c_int,
714                    NAUTYVERSIONID as c_int,
715                );
716            }
717
718            let mut lab1 = vec![0; n];
719            let mut lab2 = vec![0; n];
720            let mut ptn = vec![0; n];
721            let mut orbits = vec![0; n];
722            let mut map = vec![0; n];
723
724            /* Now make the first graph */
725            let mut sg1 = SparseGraph::new(
726                n,     /* Number of vertices */
727                3 * n, /* Number of directed edges */
728            );
729
730            for i in 0..n {
731                sg1.v[i] = (3 * i) as usize; /* Position of vertex i in v array */
732                sg1.d[i] = 3; /* Degree of vertex i */
733            }
734
735            for i in (0..n).step_by(2) {
736                /* Spokes */
737                sg1.e[sg1.v[i] as usize] = (i + 1) as c_int;
738                sg1.e[sg1.v[i + 1] as usize] = i as c_int;
739            }
740
741            for i in 0..n - 2 {
742                /* Clockwise edges */
743                sg1.e[(sg1.v[i] + 1) as usize] = (i + 2) as c_int;
744            }
745            sg1.e[(sg1.v[n - 2] + 1) as usize] = 1;
746            sg1.e[(sg1.v[n - 1] + 1) as usize] = 0;
747
748            for i in 2..n {
749                /* Anticlockwise edges */
750                sg1.e[(sg1.v[i] + 2) as usize] = (i - 2) as c_int;
751            }
752            sg1.e[(sg1.v[1] + 2) as usize] = (n - 2) as c_int;
753            sg1.e[(sg1.v[0] + 2) as usize] = (n - 1) as c_int;
754
755            /* Now make the second graph */
756            let mut sg2 = SparseGraph::new(
757                n,     /* Number of vertices */
758                3 * n, /* Number of directed edges */
759            );
760
761            for i in 0..n {
762                sg2.v[i] = (3 * i) as usize;
763                sg2.d[i] = 3;
764                sg2.e[(sg2.v[i]) as usize] = ((i + 1) % n) as c_int; /* Clockwise */
765                sg2.e[(sg2.v[i] + 1) as usize] = ((i + n - 1) % n) as c_int; /* Anti-clockwise */
766                sg2.e[(sg2.v[i] + 2) as usize] = ((i + n / 2) % n) as c_int; /* Diagonals */
767            }
768
769            /* Label sg1, result in cg1 and labelling in lab1; similarly sg2.
770            It is not necessary to pre-allocate space in cg1 and cg2, but
771            they have to be initialised as we did above.  */
772
773            unsafe {
774                Traces(
775                    &mut (&mut sg1).into(),
776                    lab1.as_mut_ptr(),
777                    ptn.as_mut_ptr(),
778                    orbits.as_mut_ptr(),
779                    &mut options,
780                    &mut stats,
781                    &mut cg1,
782                );
783                Traces(
784                    &mut (&mut sg2).into(),
785                    lab2.as_mut_ptr(),
786                    ptn.as_mut_ptr(),
787                    orbits.as_mut_ptr(),
788                    &mut options,
789                    &mut stats,
790                    &mut cg2,
791                );
792            }
793
794            /* Compare canonically labelled graphs */
795            let are_same = unsafe { aresame_sg(&mut cg1, &mut cg2) } == TRUE;
796            assert!(are_same);
797            if are_same {
798                println!("Isomorphic.");
799                if n <= 1000 {
800                    /* Write the isomorphism.  For each i, vertex lab1[i]
801                    of sg1 maps onto vertex lab2[i] of sg2.  We compute
802                    the map in order of labelling because it looks better. */
803
804                    for i in 0..n {
805                        map[lab1[i] as usize] = lab2[i]
806                    }
807                    for i in 0..n {
808                        print!(" {}-{}", i, map[i]);
809                    }
810                    println!();
811                }
812            } else {
813                println!("Not isomorphic.");
814            }
815        }
816    }
817
818    #[test]
819    fn nautyex8() {
820        let n_range = (2..20).step_by(2);
821
822        // nautyex8.c nauty example
823
824        let mut options = optionblk::default();
825        let mut stats = statsblk::default();
826
827        options.getcanon = TRUE;
828
829        for n in n_range {
830            let m = SETWORDSNEEDED(n);
831
832            unsafe {
833                nauty_check(
834                    WORDSIZE as c_int,
835                    m as c_int,
836                    n as c_int,
837                    NAUTYVERSIONID as c_int,
838                );
839            }
840
841            let mut lab1 = vec![0; n];
842            let mut lab2 = vec![0; n];
843            let mut ptn = vec![0; n];
844            let mut orbits = vec![0; n];
845            let mut map = vec![0; n];
846
847            /* Now make the first graph */
848
849            let mut g1 = empty_graph(m, n);
850
851            for i in (0..n).step_by(2) {
852                /* Spokes */
853                ADDONEEDGE(&mut g1, i, i + 1, m);
854            }
855
856            for i in 0..n - 2 {
857                /* Cycle */
858                ADDONEEDGE(&mut g1, i, i + 2, m);
859            }
860            ADDONEEDGE(&mut g1, 1, n - 2, m);
861            ADDONEEDGE(&mut g1, 0, n - 1, m);
862
863            /* Now make the second graph */
864
865            let mut g2 = empty_graph(m, n);
866
867            for i in 0..n {
868                ADDONEEDGE(&mut g2, i, (i + 1) % n, m); /* Rim */
869                ADDONEEDGE(&mut g2, i, (i + n / 2) % n, m); /* Diagonals */
870            }
871
872            /* Create canonical graphs */
873
874            let mut cg1 = empty_graph(m, n);
875            let mut cg2 = empty_graph(m, n);
876
877            unsafe {
878                densenauty(
879                    g1.as_mut_ptr(),
880                    lab1.as_mut_ptr(),
881                    ptn.as_mut_ptr(),
882                    orbits.as_mut_ptr(),
883                    &mut options,
884                    &mut stats,
885                    m as c_int,
886                    n as c_int,
887                    cg1.as_mut_ptr(),
888                );
889
890                densenauty(
891                    g2.as_mut_ptr(),
892                    lab2.as_mut_ptr(),
893                    ptn.as_mut_ptr(),
894                    orbits.as_mut_ptr(),
895                    &mut options,
896                    &mut stats,
897                    m as c_int,
898                    n as c_int,
899                    cg2.as_mut_ptr(),
900                );
901            }
902
903            assert_eq!(cg1, cg2);
904            if cg1 == cg2 {
905                println!("Isomorphic.");
906
907                /* Write the isomorphism. For each i, vertex lab1[i]
908                of sg1 maps onto vertex lab2[i] of sg2. We compute
909                the map in order of labelling because it looks better. */
910                for i in 0..n {
911                    map[lab1[i] as usize] = lab2[i];
912                }
913                for (i, m) in map.iter().enumerate() {
914                    print!(" {}-{}", i, m)
915                }
916                println!()
917            } else {
918                println!("Not isomorphic.")
919            }
920        }
921    }
922
923    #[test]
924    fn nautyex9() {
925        let mut auto_group_size = std::collections::HashMap::new();
926        for i in &[3, 4, 6, 7, 8, 9, 11, 12, 14, 15, 16, 18, 19] {
927            auto_group_size.insert(*i, None);
928        }
929        auto_group_size.insert(5, Some(10.));
930        auto_group_size.insert(10, Some(320.));
931        auto_group_size.insert(13, Some(78.));
932        auto_group_size.insert(17, Some(136.));
933
934        let n_range = 3..20;
935        let mut options = TracesOptions::default();
936        let mut stats = TracesStats::default();
937
938        let mut gens = std::ptr::null_mut();
939
940        /* Select option for passing generators to Traces */
941
942        options.generators = &mut gens;
943
944        for n in n_range {
945            let m = SETWORDSNEEDED(n);
946            unsafe {
947                nauty_check(
948                    WORDSIZE as c_int,
949                    m as c_int,
950                    n as c_int,
951                    NAUTYVERSIONID as c_int,
952                );
953            }
954
955            let mut lab = vec![0; n];
956            let mut ptn = vec![0; n];
957            let mut orbits = vec![0; n];
958            let mut p = vec![0; n];
959            let mut issquare = vec![FALSE; n];
960
961            /* Initialise list of automorphisms */
962
963            gens = std::ptr::null_mut();
964
965            /* Find the squares and the degree */
966
967            for i in 0..n {
968                issquare[(i * i) % n] = TRUE;
969            }
970            if issquare.last() != Some(&TRUE) {
971                assert_eq!(auto_group_size[&n], None);
972                println!("-1 must be a square mod n; try again");
973                continue;
974            }
975
976            let mut deg = 0;
977            for i in 1..n {
978                if issquare[i] == TRUE {
979                    deg += 1
980                }
981            }
982
983            /* Now make the graph */
984            let mut sg = SparseGraph::new(
985                n,       /* Number of vertices */
986                n * deg, /* Number of directed edges */
987            );
988
989            for i in 0..n {
990                sg.v[i] = (i * deg) as usize; /* Position of vertex i in v array */
991                sg.d[i] = deg as c_int; /* Degree of vertex i */
992            }
993
994            for i in 0..n {
995                let mut k = sg.v[i] as usize;
996                for j in 1..n {
997                    if issquare[j] == TRUE {
998                        sg.e[k] = ((i + j) % n) as c_int;
999                        k += 1;
1000                    }
1001                }
1002            }
1003
1004            /* Add known automorphisms */
1005
1006            /* We wouldn't need freeschreier() if we were only
1007            processing one graph, but it doesn't hurt.  This
1008            is how to properly dispose of previous generators. */
1009
1010            unsafe {
1011                freeschreier(std::ptr::null_mut(), &mut gens);
1012            }
1013
1014            /* Cyclic rotation */
1015            for i in 0..n {
1016                p[i] = ((i + 1) % n) as c_int;
1017            }
1018            unsafe {
1019                addpermutation(&mut gens, p.as_mut_ptr(), n as c_int);
1020            }
1021
1022            /* Reflection about 0 */
1023            for i in 0..n {
1024                p[i] = ((n - i) % n) as c_int;
1025            }
1026            unsafe {
1027                addpermutation(&mut gens, p.as_mut_ptr(), n as c_int);
1028            }
1029
1030            /* Call Traces */
1031            unsafe {
1032                Traces(
1033                    &mut (&mut sg).into(),
1034                    lab.as_mut_ptr(),
1035                    ptn.as_mut_ptr(),
1036                    orbits.as_mut_ptr(),
1037                    &mut options,
1038                    &mut stats,
1039                    std::ptr::null_mut(),
1040                );
1041            }
1042
1043            assert_eq!(auto_group_size[&n], Some(stats.grpsize1));
1044            print!("Automorphism group size = ");
1045            unsafe {
1046                writegroupsize(stdout, stats.grpsize1, stats.grpsize2);
1047            }
1048            println!();
1049
1050            /* Traces left the automorphims we gave it, augmented by
1051            any extra automorphims it found, in a circular list
1052            pointed to by gens.  See schreier.txt for documentation. */
1053        }
1054    }
1055
1056    #[test]
1057    fn nautyex10() {
1058        let n_range = (2..20).step_by(2);
1059
1060        let mut options = TracesOptions::default();
1061        let mut stats = TracesStats::default();
1062
1063        /* Declare and initialize sparse graph structures */
1064        let mut cg1 = sparsegraph::default();
1065        let mut cg2 = sparsegraph::default();
1066
1067        for n in n_range {
1068            let m = SETWORDSNEEDED(n);
1069            unsafe {
1070                nauty_check(
1071                    WORDSIZE as c_int,
1072                    m as c_int,
1073                    n as c_int,
1074                    NAUTYVERSIONID as c_int,
1075                );
1076            }
1077            let mut lab1 = vec![0; n];
1078            let mut lab2 = vec![0; n];
1079            let mut ptn = vec![0; n];
1080            let mut orbits = vec![0; n];
1081            let mut map = vec![0; n];
1082
1083            /* Now make the first graph */
1084
1085            let mut sg1 = SparseGraph::new(
1086                n,     /* Number of vertices */
1087                3 * n, /* Number of directed edges */
1088            );
1089
1090            for i in 0..n {
1091                sg1.v[i] = (3 * i) as usize; /* Position of vertex i in v array */
1092                sg1.d[i] = 3; /* Degree of vertex i */
1093            }
1094
1095            for i in (0..n).step_by(2) {
1096                sg1.e[sg1.v[i] as usize] = (i + 1) as c_int;
1097                sg1.e[sg1.v[i + 1] as usize] = i as c_int;
1098            }
1099
1100            for i in 0..n - 2 {
1101                /* Clockwise edges */
1102                sg1.e[(sg1.v[i] + 1) as usize] = (i + 2) as c_int;
1103            }
1104            sg1.e[(sg1.v[n - 2] + 1) as usize] = 1;
1105            sg1.e[(sg1.v[n - 1] + 1) as usize] = 0;
1106
1107            for i in 2..n {
1108                /* Anticlockwise edges */
1109                sg1.e[(sg1.v[i] + 2) as usize] = (i - 2) as c_int;
1110            }
1111            sg1.e[(sg1.v[1] + 2) as usize] = (n - 2) as c_int;
1112            sg1.e[(sg1.v[0] + 2) as usize] = (n - 1) as c_int;
1113
1114            /* Now make the second graph */
1115
1116            let mut sg2 = SparseGraph::new(
1117                n,     /* Number of vertices */
1118                3 * n, /* Number of directed edges */
1119            );
1120
1121            for i in 0..n {
1122                sg2.v[i] = (3 * i) as usize;
1123                sg2.d[i] = 3;
1124                sg2.e[sg2.v[i] as usize] = ((i + 1) % n) as c_int; /* Clockwise */
1125                sg2.e[(sg2.v[i] + 1) as usize] = ((i + n - 1) % n) as c_int; /* Anti-clockwise */
1126                sg2.e[(sg2.v[i] + 2) as usize] = ((i + n / 2) % n) as c_int; /* Diagonals */
1127            }
1128
1129            /* Now we make the canonically labelled graphs by a two-step
1130            process.  The first call to Traces computes the
1131            automorphism group.  The second call computes the
1132            canonical labelling, using the automorphism group from
1133            the first call.
1134
1135            We have declared a variable "generators" that will be
1136            used to hold the group generators between the two calls.
1137            It has to be initialised to NULL and its address has to
1138            be given to Traces using options.generators.  After the
1139            second call, we need to discard the generators with a
1140            call to freeschreier(), which also initializes it again. */
1141
1142            let mut generators = std::ptr::null_mut();
1143            options.generators = &mut generators;
1144
1145            options.getcanon = FALSE;
1146            unsafe {
1147                Traces(
1148                    &mut (&mut sg1).into(),
1149                    lab1.as_mut_ptr(),
1150                    ptn.as_mut_ptr(),
1151                    orbits.as_mut_ptr(),
1152                    &mut options,
1153                    &mut stats,
1154                    std::ptr::null_mut(),
1155                );
1156            }
1157            options.getcanon = TRUE;
1158            unsafe {
1159                Traces(
1160                    &mut (&mut sg1).into(),
1161                    lab1.as_mut_ptr(),
1162                    ptn.as_mut_ptr(),
1163                    orbits.as_mut_ptr(),
1164                    &mut options,
1165                    &mut stats,
1166                    &mut cg1,
1167                );
1168                freeschreier(std::ptr::null_mut(), &mut generators);
1169            }
1170
1171            options.getcanon = FALSE;
1172            unsafe {
1173                Traces(
1174                    &mut (&mut sg2).into(),
1175                    lab2.as_mut_ptr(),
1176                    ptn.as_mut_ptr(),
1177                    orbits.as_mut_ptr(),
1178                    &mut options,
1179                    &mut stats,
1180                    std::ptr::null_mut(),
1181                );
1182            }
1183            options.getcanon = TRUE;
1184            unsafe {
1185                Traces(
1186                    &mut (&mut sg2).into(),
1187                    lab2.as_mut_ptr(),
1188                    ptn.as_mut_ptr(),
1189                    orbits.as_mut_ptr(),
1190                    &mut options,
1191                    &mut stats,
1192                    &mut cg2,
1193                );
1194                freeschreier(std::ptr::null_mut(), &mut generators);
1195            }
1196
1197            /* Compare canonically labelled graphs */
1198            let are_same = unsafe { aresame_sg(&mut cg1, &mut cg2) } == TRUE;
1199            assert!(are_same);
1200            if are_same {
1201                println!("Isomorphic");
1202                if n <= 1000 {
1203                    /* Write the isomorphism.  For each i, vertex lab1[i]
1204                    of sg1 maps onto vertex lab2[i] of sg2.  We compute
1205                    the map in order of labelling because it looks better. */
1206
1207                    for i in 0..n {
1208                        map[lab1[i] as usize] = lab2[i];
1209                    }
1210                    for i in 0..n {
1211                        print!(" {}-{}", i, map[i])
1212                    }
1213                    println!()
1214                }
1215            } else {
1216                println!("Not isomorphic.");
1217            }
1218        }
1219    }
1220
1221    // test a number of sparsegraph functions
1222    #[cfg(feature = "libc")]
1223    #[test]
1224    fn sg_fun() {
1225        let n = 10;
1226
1227        let mut sg = SparseGraph::new(
1228            n,     /* Number of vertices */
1229            2 * n, /* Number of directed edges */
1230        );
1231
1232        for i in 0..n {
1233            sg.v[i] = 2 * i as usize;
1234            sg.d[i] = 2;
1235            sg.e[2 * i] = ((i + n - 1) % n) as c_int; /* edge i->i-1 */
1236            sg.e[2 * i + 1] = ((i + n + 1) % n) as c_int; /* edge i->i+1 */
1237        }
1238
1239        unsafe { test_copy_sg(&mut (&mut sg).into()) }
1240
1241        let m = SETWORDSNEEDED(n);
1242        let mut g = empty_graph(m, n);
1243        for v in 0..n {
1244            ADDONEEDGE(&mut g, v, (v + 1) % n, m)
1245        }
1246        unsafe { test_nauty_to_sg(&mut g, &mut (&mut sg).into(), n, m) }
1247        unsafe { test_sg_to_nauty(&mut (&mut sg).into(), &mut g, n) }
1248
1249        test_sortlists_sg(&mut sg);
1250
1251        // TODO: test `put_sg`
1252    }
1253
1254    #[cfg(feature = "libc")]
1255    unsafe fn test_copy_sg(sg: &mut sparsegraph) {
1256        let sg_cp = copy_sg(sg, std::ptr::null_mut());
1257        assert!(aresame_sg(sg, sg_cp) != 0);
1258        SG_FREE(&mut *sg_cp);
1259    }
1260
1261    #[cfg(feature = "libc")]
1262    unsafe fn test_nauty_to_sg(
1263        g: &mut [graph],
1264        sg: &mut sparsegraph,
1265        n: usize,
1266        m: usize,
1267    ) {
1268        let sg_from_g = nauty_to_sg(
1269            g.as_mut_ptr(),
1270            std::ptr::null_mut(),
1271            m as c_int,
1272            n as c_int,
1273        );
1274        assert!(aresame_sg(sg, sg_from_g) != 0);
1275        SG_FREE(&mut *sg_from_g);
1276    }
1277
1278    #[cfg(feature = "libc")]
1279    unsafe fn test_sg_to_nauty(
1280        sg: &mut sparsegraph,
1281        g: &mut [graph],
1282        n: usize,
1283    ) {
1284        let mut m = 0;
1285        let mut g_from_sg = sg_to_nauty(sg, std::ptr::null_mut(), 0, &mut m);
1286        {
1287            let g2 = std::slice::from_raw_parts(
1288                g_from_sg as *const graph,
1289                n * m as usize,
1290            );
1291            assert_eq!(&*g, g2);
1292        }
1293        let mut dummy = 0;
1294        DYNFREE(&mut g_from_sg, &mut dummy);
1295    }
1296
1297    #[cfg(feature = "libc")]
1298    fn test_sortlists_sg(sg: &mut SparseGraph) {
1299        let orig_sg = sg.clone();
1300
1301        unsafe { sortlists_sg(&mut sg.into()) }
1302        assert_eq!(orig_sg.v, sg.v);
1303        assert_eq!(orig_sg.d, sg.d);
1304        assert!(orig_sg.e != sg.e);
1305    }
1306}
nauty_Traces_sys/lib.rs

nauty_Traces_sys/
lib.rs
