normal_form/
lib.rs

1//! This library provides a simple method to find the normal/canonical form
2//! of a structure, as long as it implements the provided `Normalize` trait.
3//! It is an implementation of *Practical graph isomorphism, II*
4//! [[McKay 2013]](https://arxiv.org/pdf/1301.1493.pdf) and heavily inspired by
5//! the [canonical-form](https://crates.io/crates/canonical-form) crate with the
6//! addition of caching and associated abstraction types.
7use std::collections::BTreeMap;
8
9mod coloring;
10pub mod set;
11mod tree;
12
13pub use coloring::{Coloring, ReversibleColoring};
14pub use set::Map;
15pub use set::Set;
16
17/// Type for which a canonical form can be found.
18pub trait Normalize: Sized {
19	/// Set of elements that can be permuted in order to find the canonical form.
20	type Elements: Set;
21
22	/// Initial coloring of the permutable elements.
23	type Color: Ord;
24
25	/// Cached data used to refine the coloring at each step.
26	///
27	/// You can put in there the result of preliminary computations and allocations.
28	type Cache;
29
30	type Morphed: Ord;
31
32	/// Initialize the cache.
33	///
34	/// This is the place to perform preliminary computations and allocations that will be
35	/// useful every time the coloring must be refined.
36	fn initialize_cache(&self) -> Self::Cache;
37
38	/// Returns a reference to the permutable elements.
39	fn elements(&self) -> &Self::Elements;
40
41	/// Returns the initial coloring of the permutable elements.
42	fn initial_coloring(&self) -> <Self::Elements as Set>::Map<Self::Color>;
43
44	/// Refine the current coloring.
45	fn refine_coloring(
46		&self,
47		_cache: &mut Self::Cache,
48		_coloring: &mut ReversibleColoring<Self::Elements>,
49	) {
50		// nothing by default.
51	}
52
53	/// Apply the given morphism.
54	fn apply_morphism<F>(&self, morphism: F) -> Self::Morphed
55	where
56		F: Fn(&<Self::Elements as Set>::Item) -> usize;
57
58	/// Computes the canonical form of this object.
59	fn normal_form(&self) -> Self::Morphed
60	where
61		<Self::Elements as Set>::Map<usize>: Clone,
62	{
63		self.normalize().0
64	}
65
66	/// Computes the canonical permutation of this object.
67	fn canonical_permutation(&self) -> <Self::Elements as Set>::Map<usize>
68	where
69		<Self::Elements as Set>::Map<usize>: Clone,
70	{
71		self.normalize().1
72	}
73
74	/// Computes the canonical form of this object, with the associated permutation.
75	fn normalize(&self) -> (Self::Morphed, <Self::Elements as Set>::Map<usize>)
76	where
77		<Self::Elements as Set>::Map<usize>: Clone,
78	{
79		use std::collections::btree_map::Entry;
80		let mut cache = self.initialize_cache();
81		let elements = self.elements();
82		let initial_coloring = self.initial_coloring();
83		let mut node = Some(
84			tree::Node::root(ReversibleColoring::from_coloring(
85				elements,
86				Coloring::from_map(elements, &initial_coloring),
87			))
88			.into_first_child_leaf(|coloring| self.refine_coloring(&mut cache, coloring)),
89		);
90
91		pub struct Automorphism<T: Normalize> {
92			path: Vec<<T::Elements as Set>::Item>,
93			permutation: <T::Elements as Set>::Map<usize>,
94		}
95
96		let mut automorphisms: BTreeMap<Self::Morphed, Automorphism<Self>> = BTreeMap::new();
97
98		while let Some(mut n) = node {
99			debug_assert!(n.coloring().is_discrete());
100			let permutation = n.coloring().as_permutation().unwrap();
101			let morphed = self.apply_morphism(|i| *permutation.get(i).unwrap());
102			match automorphisms.entry(morphed) {
103				Entry::Occupied(entry) => {
104					// We found an automorphism with a previous branch, we can prune the search tree!
105					// We can prune up to the parent node sharing the longest prefix path.
106					// Why: because the first different choice lead to an automorphism.
107					// Any other leaf node morphism in this branch will be an automorphism with
108					// one of the leaves in the previous branch.
109					let len = n.path().len();
110
111					// Step 1: We find the longest common prefix path length.
112					let prefix_len = longest_common_prefix_len(n.path(), &entry.get().path);
113
114					// Step 2: We skip the other nodes in this branch and directly
115					// go back to the parent node of depth `prefix_len`.
116					// More precisely, we go back to the parent node of depth
117					// `prefix_len + 1` (just after the divergence), and let the
118					// call to `into_next_leaf` below move up to the parent and to the
119					// next leaf node.
120					n.restore(len - prefix_len - 1); // prune the search tree.
121				}
122				Entry::Vacant(entry) => {
123					entry.insert(Automorphism {
124						path: n.path().clone(),
125						permutation: permutation.clone(),
126					});
127				}
128			}
129
130			node = n.into_next_leaf(|coloring| self.refine_coloring(&mut cache, coloring));
131		}
132
133		let (normal_form, data) = automorphisms.into_iter().next().unwrap();
134		(normal_form, data.permutation)
135	}
136}
137
138fn longest_common_prefix_len<T: PartialEq>(a: &[T], b: &[T]) -> usize {
139	let mut n = 0;
140
141	for (a, b) in a.iter().zip(b) {
142		if a == b {
143			n += 1
144		} else {
145			break;
146		}
147	}
148
149	n
150}
normal_form/lib.rs

normal_form/
lib.rs
