1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

//! # Graph Canon
//!
//! This crate provides a graph canonization algorithm for directed and undirected graphs
//! by calling the C library [nauty](https://pallini.di.uniroma1.it/) via [nauty-Traces-sys](https://crates.io/crates/nauty-Traces-sys)
//!
//! This crate is built on top of the [petgraph](https://crates.io/crates/petgraph) crate, but is
//! considerably faster than an existing crate [nauty-pet](https://crates.io/crates/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);
//! ```

pub mod canon;
pub mod dense;
pub use canon::{canonize, CanonLabeling};
pub use dense::DenseGraph;