18 releases (11 breaking)
0.12.1  Apr 11, 2024 

0.12.0  Jul 21, 2023 
0.11.1  Jun 26, 2023 
0.8.0  Sep 26, 2022 
0.1.1  Feb 11, 2022 
#522 in Math
1,058 downloads per month
Used in 2 crates
68KB
2K
SLoC
nautypet
Canonical graph labelling.
Leverages nauty and Traces to find canonical labellings and graph automorphisms for petgraph graphs.
Example
use petgraph::graph::UnGraph;
use nauty_pet::prelude::*;
// Two different vertex labellings for the tree graph with two edges
let g1 = UnGraph::<(), ()>::from_edges([(0, 1), (1, 2)]);
let g2 = UnGraph::<(), ()>::from_edges([(0, 1), (0, 2)]);
// The canonical forms are identical
let c1 = g1.clone().into_canon();
let c2 = g2.clone().into_canon();
assert!(c1.is_identical(&c2));
// Alternatively, we can use a dedicated `struct` for canonically
// labelled graphs
let c1 = CanonGraph::from(g1.clone());
let c2 = CanonGraph::from(g2);
assert_eq!(c1, c2);
// `g1` is invariant under the permutation 0 > 2, 1 > 1, 2 > 0.
// we encode it as the vector `[2, 1, 0]`
let automorphisms = g1.try_into_autom_group().unwrap();
assert!(automorphisms.contains(&vec![2, 1, 0]));
Features

serde1
: Enables serialisation of CanonGraph objects using serde. 
stable
: Ensures deterministic behaviour when node or edge weights are distinguishable, but compare equal.
To enable features feature1
, feature2
add the following to
your Cargo.toml:
[dependencies]
nautypet = { version = "0.8", features = ["feature1", "feature2"] }
License: Apache2.0
Dependencies
~4.5–7.5MB
~133K SLoC