#![warn(
missing_docs,
missing_debug_implementations,
missing_copy_implementations,
trivial_casts,
trivial_numeric_casts,
unsafe_code,
unstable_features,
unused_import_braces,
unused_qualifications,
unused_labels,
unused_results
)]
mod refine;
use crate::refine::Partition;
use std::collections::BTreeMap;
pub trait Canonize
where
Self: Sized + Ord + Clone,
{
fn size(&self) -> usize;
fn apply_morphism(&self, perm: &[usize]) -> Self;
fn invariant_coloring(&self) -> Option<Vec<u64>> {
None
}
fn invariant_neighborhood(&self, _u: usize) -> Vec<Vec<usize>> {
Vec::new()
}
}
fn target_selector(part: &Partition) -> Option<usize> {
let mut min = std::usize::MAX;
let mut arg_min = None;
for i in part.parts() {
let length = part.part(i).len();
if 2 <= length && (length < min) {
min = length;
arg_min = Some(i);
}
}
arg_min
}
fn refine<F>(partition: &mut Partition, g: &F)
where
F: Canonize,
{
if !partition.is_discrete() {
let n = g.size();
assert!(n >= 2);
if let Some(coloring) = g.invariant_coloring() {
partition.refine_by_value(&coloring, |_| {})
}
let mut invariants = Vec::with_capacity(n);
for i in 0..n {
invariants.push(g.invariant_neighborhood(i))
}
let invariant_size = invariants[0].len();
assert!(invariants.iter().all(|v| v.len() == invariant_size));
let mut crible = vec![0; n];
let mut stack: Vec<_> = partition.parts();
let m = (n + 1) as u64;
let step = m.pow(invariant_size as u32);
let threshold = std::u64::MAX / step;
while !stack.is_empty() && !partition.is_discrete() {
for e in &mut crible {
*e = 0;
}
let mut weight = 1;
while let Some(part) = stack.pop() {
for i in 0..invariant_size {
weight *= m;
for &u in partition.part(part) {
for &v in &invariants[u][i] {
crible[v] += weight;
}
}
}
if weight > threshold {
break;
};
}
partition.refine_by_value(&crible, |new| {
stack.push(new);
});
}
}
}
fn fca(u: &[usize], v: &[usize]) -> usize {
let mut i = 0;
while i < u.len() && i < v.len() && u[i] == v[i] {
i += 1;
}
i
}
#[derive(Clone, Debug)]
struct IsoTreeNode {
pi: Partition,
children: Vec<usize>,
}
impl IsoTreeNode {
fn new<F: Canonize>(mut partition: Partition, g: &F) -> Self {
refine(&mut partition, g);
IsoTreeNode {
children: match target_selector(&partition) {
Some(set) => partition.part(set).to_vec(),
None => Vec::new(),
},
pi: partition,
}
}
fn explore<F: Canonize>(&self, v: usize, g: &F) -> Self {
let mut new_pi = self.pi.clone();
new_pi.individualize(v);
refine(&mut new_pi, g);
Self::new(new_pi, g)
}
fn empty() -> Self {
IsoTreeNode {
children: Vec::new(),
pi: Partition::simple(0),
}
}
}
fn canonical_form_constraint<F>(g: &F, partition: Partition) -> F
where
F: Canonize,
{
let mut zeta: BTreeMap<F, Vec<usize>> = BTreeMap::new();
let mut tree = Vec::new();
let mut path = Vec::new();
let mut node = IsoTreeNode::new(partition, g);
loop {
if let Some(phi) = node.pi.as_bijection() {
let phi_g = g.apply_morphism(phi);
if let Some(u) = zeta.get(&phi_g) {
let k = fca(u, &path) + 1;
tree.truncate(k);
path.truncate(k);
} else {
let _ = zeta.insert(phi_g, path.clone());
}
};
if let Some(u) = node.children.pop() {
path.push(u);
let new_node = node.explore(u, g);
tree.push(node);
node = new_node;
} else {
match tree.pop() {
Some(n) => {
node = n;
let _ = path.pop();
}
None => break,
}
}
}
zeta.keys().next_back().unwrap().clone()
}
#[derive(Clone, Debug)]
pub struct AutomorphismIterator<F> {
tree: Vec<IsoTreeNode>,
node: IsoTreeNode,
g: F,
}
impl<F: Canonize> AutomorphismIterator<F> {
fn with_partition(g: &F, partition: Partition) -> Self {
assert!(*g == canonical_form_constraint(g, partition.clone()));
AutomorphismIterator {
tree: vec![IsoTreeNode::new(partition, g)],
node: IsoTreeNode::empty(),
g: g.clone(),
}
}
pub fn typed(g: &F, sigma: usize) -> Self {
let mut partition = Partition::simple(g.size());
for i in 0..sigma {
partition.individualize(i)
}
Self::with_partition(g, partition)
}
pub fn new(g: &F) -> Self {
Self::typed(g, 0)
}
}
impl<F: Canonize> Iterator for AutomorphismIterator<F> {
type Item = Vec<usize>;
fn next(&mut self) -> Option<Self::Item> {
loop {
if let Some(u) = self.node.children.pop() {
let new_node = self.node.explore(u, &self.g);
let old_node = std::mem::replace(&mut self.node, new_node);
self.tree.push(old_node)
} else {
match self.tree.pop() {
Some(n) => self.node = n,
None => return None,
}
}
if let Some(phi) = self.node.pi.as_bijection() {
if self.g.apply_morphism(phi) == self.g {
return Some(phi.to_vec());
}
};
}
}
}
pub fn canonical_form_typed<F>(g: &F, sigma: usize) -> F
where
F: Canonize,
{
let mut partition = Partition::simple(g.size());
for i in 0..sigma {
partition.individualize(i)
}
canonical_form_constraint(&g, partition)
}
pub fn canonical_form<F>(g: &F) -> F
where
F: Canonize,
{
canonical_form_typed(g, 0)
}
fn canonical_form_morphism_constraint<F>(g: &F, partition: Partition) -> Vec<usize>
where
F: Canonize,
{
let mut tree = Vec::new();
let mut node = IsoTreeNode::new(partition, g);
let mut max = None;
let mut phimax = Vec::new();
loop {
if let Some(phi) = node.pi.as_bijection() {
let phi_g = Some(g.apply_morphism(phi));
if phi_g > max {
max = phi_g;
phimax = phi.to_vec();
}
};
if let Some(u) = node.children.pop() {
let new_node = node.explore(u, g);
tree.push(node);
node = new_node;
} else {
match tree.pop() {
Some(n) => node = n,
None => break,
}
}
}
phimax
}
pub fn canonical_form_typed_morphism<F>(g: &F, sigma: usize) -> Vec<usize>
where
F: Canonize,
{
assert!(sigma <= g.size());
let mut partition = Partition::simple(g.size());
for v in 0..sigma {
partition.individualize(v);
}
canonical_form_morphism_constraint(g, partition)
}
pub fn canonical_form_morphism<F>(g: &F) -> Vec<usize>
where
F: Canonize,
{
canonical_form_typed_morphism(g, 0)
}
#[cfg(test)]
mod tests {
use super::*;
#[derive(Ord, PartialOrd, PartialEq, Eq, Clone, Debug)]
struct Graph {
adj: Vec<Vec<usize>>,
}
impl Graph {
fn new(n: usize, edges: &[(usize, usize)]) -> Self {
let mut adj = vec![Vec::new(); n];
for &(u, v) in edges {
adj[u].push(v);
adj[v].push(u);
}
Graph { adj }
}
}
impl Canonize for Graph {
fn size(&self) -> usize {
self.adj.len()
}
fn apply_morphism(&self, perm: &[usize]) -> Self {
let mut adj = vec![Vec::new(); self.size()];
for (i, nbrs) in self.adj.iter().enumerate() {
adj[perm[i]] = nbrs.iter().map(|&u| perm[u]).collect();
adj[perm[i]].sort();
}
Graph { adj }
}
fn invariant_neighborhood(&self, u: usize) -> Vec<Vec<usize>> {
vec![self.adj[u].clone()]
}
}
#[test]
fn graph() {
let c5 = Graph::new(5, &[(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]);
let other_c5 = Graph::new(5, &[(0, 2), (2, 1), (1, 4), (4, 3), (3, 0)]);
assert_eq!(canonical_form(&c5), canonical_form(&other_c5));
let p5 = Graph::new(5, &[(0, 1), (1, 2), (2, 3), (3, 4)]);
assert!(canonical_form(&c5) != canonical_form(&p5));
let p = canonical_form_morphism(&c5);
assert_eq!(c5.apply_morphism(&p), canonical_form(&c5));
}
#[test]
fn automorphisms_iterator() {
let c4 = canonical_form(&Graph::new(4, &[(0, 1), (1, 2), (2, 3), (3, 0)]));
let mut count = 0;
for phi in AutomorphismIterator::new(&c4) {
assert_eq!(c4.apply_morphism(&phi), c4);
count += 1;
}
assert_eq!(count, 8)
}
}