Crate graph_canon

Graph Canon

This crate provides a graph canonization algorithm for directed and undirected graphs by calling the C library nauty via nauty-Traces-sys

This crate is built on top of the petgraph crate, but is considerably faster than an existing crate nauty-pet that uses similar techniques because it is very barebones.

Example

Hashable Labels

If you are just looking to create a hashable object to determine isomorphism then it is simples to use the CanonLabeling struct.

This can be created from a Graph object directly.

Directed Graphs

use petgraph::{Directed, Graph};
use graph_canon::CanonLabeling;

let e1 = vec![(0, 1), (0, 2), (1, 2)]; // Isomorphic
let e2 = vec![(1, 0), (1, 2), (0, 2)]; // Isomorphic
let e3 = vec![(1, 0), (1, 2), (2, 1)]; // Non-Isomorphic

let g1 = Graph::<(), (), Directed>::from_edges(&e1);
let g2 = Graph::<(), (), Directed>::from_edges(&e2);
let g3 = Graph::<(), (), Directed>::from_edges(&e3);

let l1 = CanonLabeling::new(&g1);
let l2 = CanonLabeling::new(&g2);
let l3 = CanonLabeling::new(&g3);

assert_eq!(l1, l2);
assert_ne!(l1, l3);

Undirected Graphs

use petgraph::{Undirected, Graph};
use graph_canon::CanonLabeling;

let e1 = vec![(0, 1), (0, 2), (1, 2)]; // Isomorphic
let e2 = vec![(1, 0), (1, 2), (0, 2)]; // Isomorphic
let e3 = vec![(1, 0), (1, 2)];         // Non-Isomorphic

let g1 = Graph::<(), (), Undirected>::from_edges(&e1);
let g2 = Graph::<(), (), Undirected>::from_edges(&e2);
let g3 = Graph::<(), (), Undirected>::from_edges(&e3);

let l1 = CanonLabeling::new(&g1);
let l2 = CanonLabeling::new(&g2);
let l3 = CanonLabeling::new(&g3);

assert_eq!(l1, l2);
assert_ne!(l1, l3);

Recovering the Canonical Graph

If instead you are interested in working with the graph itself, you can use the canonize function to return a new Graph object

Directed Graphs

use petgraph::{Directed, Graph};
use graph_canon::canonize;

let edges = vec![(0, 1), (0, 2), (1, 2)];
let graph = Graph::<(), (), Directed>::from_edges(&edges);
let canon = canonize(&graph);
assert_eq!(canon.edge_count(), 3);

Undirected Graphs

use petgraph::{Undirected, Graph};
use graph_canon::canonize;

let edges = vec![(0, 1), (0, 2), (1, 2)];
let graph = Graph::<(), (), Undirected>::from_edges(&edges);
let canon = canonize(&graph);

// There are currently twice as many edges but may change in the future
assert_eq!(canon.edge_count(), 6);

Recovering the automorphism group of a Graph

If you’re interested in the automorphism group of a graph, you can use the autom module.

Directed Graphs

use petgraph::{Directed, Graph};
use graph_canon::autom::AutoGroups;

let edges = vec![(0, 1), (1, 2), (2, 0)];
let graph = Graph::<(), (), Directed>::from_edges(&edges);
let aut = AutoGroups::from_petgraph(&graph);

assert_eq!(aut.size(), 3);

Re-exports

pub use canon::canonize;

pub use canon::CanonLabeling;

pub use dense::DenseGraph;

Modules

autom

canon

dense