nauty_pet/
lib.rs

1//! Canonical graph labelling.
2//!
3//! Leverages [nauty and Traces](http://pallini.di.uniroma1.it/) to
4//! find [canonical
5//! labellings](https://en.wikipedia.org/wiki/Graph_canonization) and
6//! [graph
7//! automorphisms](https://en.wikipedia.org/wiki/Graph_automorphism)
8//! for [petgraph](https://github.com/petgraph/petgraph) graphs.
9//!
10//! # Example
11//!
12//! ```rust
13//! use petgraph::graph::UnGraph;
14//! use nauty_pet::prelude::*;
15//!
16//! // Two different vertex labellings for the tree graph with two edges
17//! let g1 = UnGraph::<(), ()>::from_edges([(0, 1), (1, 2)]);
18//! let g2 = UnGraph::<(), ()>::from_edges([(0, 1), (0, 2)]);
19//!
20//! // The canonical forms are identical
21//! let c1 = g1.clone().into_canon();
22//! let c2 = g2.clone().into_canon();
23//! assert!(c1.is_identical(&c2));
24//!
25//! // Alternatively, we can use a dedicated `struct` for canonically
26//! // labelled graphs
27//! let c1 = CanonGraph::from(g1.clone());
28//! let c2 = CanonGraph::from(g2);
29//! assert_eq!(c1, c2);
30//!
31//! // `g1` is invariant under the permutation 0 -> 2, 1 -> 1, 2 -> 0.
32//! // we encode it as the vector `[2, 1, 0]`
33//! let automorphisms = g1.try_into_autom_group().unwrap();
34//! assert!(automorphisms.contains(&vec![2, 1, 0]));
35//!
36//! ```
37//!
38//! # Features
39//!
40//! * `serde-1`: Enables serialisation of
41//!              [CanonGraph](graph::CanonGraph) objects using
42//!              [serde](https://crates.io/crates/serde).
43//!
44//! * `stable`: Ensures deterministic behaviour when node or edge
45//!             weights are distinguishable, but compare equal.
46//!
47//! To enable features `feature1`, `feature2` add the following to
48//! your Cargo.toml:
49//! ```toml
50//! [dependencies]
51//! nauty-pet = { version = "0.8", features = ["feature1", "feature2"] }
52//! ```
53pub mod autom;
54pub mod canon;
55mod cmp;
56pub mod error;
57pub mod graph;
58mod nauty_graph;
59pub mod prelude;
60
61pub use canon::IntoCanon;
62pub use canon::{IntoCanonNautySparse, TryIntoCanonTraces};
63pub use cmp::IsIdentical;
64
65#[cfg(test)]
66mod tests {
67    use super::prelude::*;
68    use petgraph::{
69        EdgeType,
70        graph::{Graph, IndexType, UnGraph},
71        prelude::EdgeIndex,
72    };
73
74    fn add_edge<N, E, Ty: EdgeType, Ix: IndexType>(
75        g: &mut Graph<N, E, Ty, Ix>,
76        v1: usize,
77        v2: usize,
78        wt: E,
79    ) -> EdgeIndex<Ix> {
80        use petgraph::visit::NodeIndexable;
81        g.add_edge(g.from_index(v1), g.from_index(v2), wt)
82    }
83
84    #[test]
85    fn nautyex8() {
86        let n_range = (2..20).step_by(2);
87
88        for n in n_range {
89            let mut g1 = UnGraph::<(), ()>::with_capacity(n, 3 * n);
90            for _ in 0..n {
91                g1.add_node(());
92            }
93
94            // Spokes
95            for i in (0..n).step_by(2) {
96                add_edge(&mut g1, i, i + 1, ());
97            }
98            // Cycle
99            for i in 0..n - 2 {
100                add_edge(&mut g1, i, i + 2, ());
101            }
102            add_edge(&mut g1, 1, n - 2, ());
103            add_edge(&mut g1, 0, n - 1, ());
104
105            let mut g2 = UnGraph::<(), ()>::with_capacity(n, 3 * n);
106            for _ in 0..n {
107                g2.add_node(());
108            }
109
110            for i in 0..n {
111                add_edge(&mut g2, i, (i + 1) % n, ()); /* Rim */
112            }
113            for i in 0..(n / 2) {
114                add_edge(&mut g2, i, i + n / 2, ()); /* Diagonals */
115            }
116
117            /* Create canonical graphs */
118
119            let cg1 = g1.into_canon();
120            let cg2 = g2.into_canon();
121
122            assert!(cg1.is_identical(&cg2));
123        }
124    }
125}
nauty_pet/lib.rs

nauty_pet/
lib.rs
