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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

//! This library provides a simple method to find the normal/canonical form
//! of a structure, as long as it implements the provided `Normalize` trait.
//! It is an implementation of *Practical graph isomorphism, II*
//! [[McKay 2013]](https://arxiv.org/pdf/1301.1493.pdf) and heavily inspired by
//! the [canonical-form](https://crates.io/crates/canonical-form) crate with the
//! addition of caching and associated abstraction types.
use std::collections::BTreeMap;

mod coloring;
pub mod set;
mod tree;

pub use coloring::{Coloring, ReversibleColoring};
pub use set::Map;
pub use set::Set;

/// Type for which a canonical form can be found.
pub trait Normalize: Sized {
	/// Set of elements that can be permuted in order to find the canonical form.
	type Elements: Set;

	/// Initial coloring of the permutable elements.
	type Color: Ord;

	/// Cached data used to refine the coloring at each step.
	///
	/// You can put in there the result of preliminary computations and allocations.
	type Cache;

	type Morphed: Ord;

	/// Initialize the cache.
	///
	/// This is the place to perform preliminary computations and allocations that will be
	/// useful every time the coloring must be refined.
	fn initialize_cache(&self) -> Self::Cache;

	/// Returns a reference to the permutable elements.
	fn elements(&self) -> &Self::Elements;

	/// Returns the initial coloring of the permutable elements.
	fn initial_coloring(&self) -> <Self::Elements as Set>::Map<Self::Color>;

	/// Refine the current coloring.
	fn refine_coloring(
		&self,
		_cache: &mut Self::Cache,
		_coloring: &mut ReversibleColoring<Self::Elements>,
	) {
		// nothing by default.
	}

	/// Apply the given morphism.
	fn apply_morphism<F>(&self, morphism: F) -> Self::Morphed
	where
		F: Fn(&<Self::Elements as Set>::Item) -> usize;

	/// Computes the canonical form of this object.
	fn normal_form(&self) -> Self::Morphed
	where
		<Self::Elements as Set>::Map<usize>: Clone,
	{
		self.normalize().0
	}

	/// Computes the canonical permutation of this object.
	fn canonical_permutation(&self) -> <Self::Elements as Set>::Map<usize>
	where
		<Self::Elements as Set>::Map<usize>: Clone,
	{
		self.normalize().1
	}

	/// Computes the canonical form of this object, with the associated permutation.
	fn normalize(&self) -> (Self::Morphed, <Self::Elements as Set>::Map<usize>)
	where
		<Self::Elements as Set>::Map<usize>: Clone,
	{
		use std::collections::btree_map::Entry;
		let mut cache = self.initialize_cache();
		let elements = self.elements();
		let initial_coloring = self.initial_coloring();
		let mut node = Some(
			tree::Node::root(ReversibleColoring::from_coloring(
				elements,
				Coloring::from_map(elements, &initial_coloring),
			))
			.into_first_child_leaf(|coloring| self.refine_coloring(&mut cache, coloring)),
		);

		pub struct Automorphism<T: Normalize> {
			path: Vec<<T::Elements as Set>::Item>,
			permutation: <T::Elements as Set>::Map<usize>,
		}

		let mut automorphisms: BTreeMap<Self::Morphed, Automorphism<Self>> = BTreeMap::new();

		while let Some(mut n) = node {
			debug_assert!(n.coloring().is_discrete());
			let permutation = n.coloring().as_permutation().unwrap();
			let morphed = self.apply_morphism(|i| *permutation.get(i).unwrap());
			match automorphisms.entry(morphed) {
				Entry::Occupied(entry) => {
					// We found an automorphism with a previous branch, we can prune the search tree!
					// We can prune up to the parent node sharing the longest prefix path.
					// Why: because the first different choice lead to an automorphism.
					// Any other leaf node morphism in this branch will be an automorphism with
					// one of the leaves in the previous branch.
					let len = n.path().len();

					// Step 1: We find the longest common prefix path length.
					let prefix_len = longest_common_prefix_len(n.path(), &entry.get().path);

					// Step 2: We skip the other nodes in this branch and directly
					// go back to the parent node of depth `prefix_len`.
					// More precisely, we go back to the parent node of depth
					// `prefix_len + 1` (just after the divergence), and let the
					// call to `into_next_leaf` below move up to the parent and to the
					// next leaf node.
					n.restore(len - prefix_len - 1); // prune the search tree.
				}
				Entry::Vacant(entry) => {
					entry.insert(Automorphism {
						path: n.path().clone(),
						permutation: permutation.clone(),
					});
				}
			}

			node = n.into_next_leaf(|coloring| self.refine_coloring(&mut cache, coloring));
		}

		let (normal_form, data) = automorphisms.into_iter().next().unwrap();
		(normal_form, data.permutation)
	}
}

fn longest_common_prefix_len<T: PartialEq>(a: &[T], b: &[T]) -> usize {
	let mut n = 0;

	for (a, b) in a.iter().zip(b) {
		if a == b {
			n += 1
		} else {
			break;
		}
	}

	n
}