graph_canon/lib.rs
1//! # Graph Canon
2//!
3//! This crate provides a graph canonization algorithm for directed and undirected graphs
4//! by calling the C library [nauty](https://pallini.di.uniroma1.it/) via [nauty-Traces-sys](https://crates.io/crates/nauty-Traces-sys)
5//!
6//! This crate is built on top of the [petgraph](https://crates.io/crates/petgraph) crate, but is
7//! considerably faster than an existing crate [nauty-pet](https://crates.io/crates/nauty-pet) that
8//! uses similar techniques because it is **very** barebones.
9//!
10//! ## Example
11//!
12//! ### Hashable Labels
13//! If you are just looking to create a hashable object to determine isomorphism
14//! then it is simples to use the `CanonLabeling` struct.
15//!
16//! This can be created from a `Graph` object directly.
17//!
18//! #### Directed Graphs
19//! ```
20//! use petgraph::{Directed, Graph};
21//! use graph_canon::CanonLabeling;
22//!
23//! let e1 = vec![(0, 1), (0, 2), (1, 2)]; // Isomorphic
24//! let e2 = vec![(1, 0), (1, 2), (0, 2)]; // Isomorphic
25//! let e3 = vec![(1, 0), (1, 2), (2, 1)]; // Non-Isomorphic
26//!
27//! let g1 = Graph::<(), (), Directed>::from_edges(&e1);
28//! let g2 = Graph::<(), (), Directed>::from_edges(&e2);
29//! let g3 = Graph::<(), (), Directed>::from_edges(&e3);
30//!
31//! let l1 = CanonLabeling::new(&g1);
32//! let l2 = CanonLabeling::new(&g2);
33//! let l3 = CanonLabeling::new(&g3);
34//!
35//! assert_eq!(l1, l2);
36//! assert_ne!(l1, l3);
37//! ```
38//!
39//! #### Undirected Graphs
40//! ```
41//! use petgraph::{Undirected, Graph};
42//! use graph_canon::CanonLabeling;
43//!
44//! let e1 = vec![(0, 1), (0, 2), (1, 2)]; // Isomorphic
45//! let e2 = vec![(1, 0), (1, 2), (0, 2)]; // Isomorphic
46//! let e3 = vec![(1, 0), (1, 2)]; // Non-Isomorphic
47//!
48//! let g1 = Graph::<(), (), Undirected>::from_edges(&e1);
49//! let g2 = Graph::<(), (), Undirected>::from_edges(&e2);
50//! let g3 = Graph::<(), (), Undirected>::from_edges(&e3);
51//!
52//! let l1 = CanonLabeling::new(&g1);
53//! let l2 = CanonLabeling::new(&g2);
54//! let l3 = CanonLabeling::new(&g3);
55//!
56//! assert_eq!(l1, l2);
57//! assert_ne!(l1, l3);
58//! ```
59//!
60//! ### Recovering the Canonical `Graph`
61//!
62//! If instead you are interested in working with the graph itself,
63//! you can use the `canonize` function to return a new `Graph` object
64//!
65//! #### Directed Graphs
66//! ```
67//! use petgraph::{Directed, Graph};
68//! use graph_canon::canonize;
69//!
70//! let edges = vec![(0, 1), (0, 2), (1, 2)];
71//! let graph = Graph::<(), (), Directed>::from_edges(&edges);
72//! let canon = canonize(&graph);
73//! assert_eq!(canon.edge_count(), 3);
74//! ```
75//!
76//! #### Undirected Graphs
77//! ```
78//! use petgraph::{Undirected, Graph};
79//! use graph_canon::canonize;
80//!
81//! let edges = vec![(0, 1), (0, 2), (1, 2)];
82//! let graph = Graph::<(), (), Undirected>::from_edges(&edges);
83//! let canon = canonize(&graph);
84//!
85//! // There are currently twice as many edges but may change in the future
86//! assert_eq!(canon.edge_count(), 6);
87//! ```
88//!
89//! ### Recovering the automorphism group of a `Graph`
90//!
91//! If you're interested in the automorphism group of a graph, you can use the `autom` module.
92//!
93//! #### Directed Graphs
94//! ```
95//! use petgraph::{Directed, Graph};
96//! use graph_canon::autom::AutoGroups;
97//!
98//! let edges = vec![(0, 1), (1, 2), (2, 0)];
99//! let graph = Graph::<(), (), Directed>::from_edges(&edges);
100//! let aut = AutoGroups::from_petgraph(&graph);
101//!
102//! assert_eq!(aut.size(), 3);
103//! ```
104
105pub mod autom;
106pub mod canon;
107pub mod dense;
108pub use canon::{canonize, CanonLabeling};
109pub use dense::DenseGraph;