canonical-form

Algorithms to reduce combinatorial structures modulo isomorphism.

This can typically be use to to test if two graphs are isomorphic. ```rust use canonical_form::*;

// Simple Graph implementation as adjacency list

[derive(Ord, PartialOrd, PartialEq, Eq, Clone, Debug)]

struct Graph { adj: Vec>, }

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 } } }

// The Canonize trait allows to use the canonial form algorithms impl Canonize for Graph { fn size(&self) -> usize { self.adj.len() } fn applymorphism(&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 invariantneighborhood(&self, u: usize) -> Vec> { vec![self.adj[u].clone()] } }

// Usage of library functions let c5 = Graph::new(5, &[(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]); let otherc5 = Graph::new(5, &[(0, 2), (2, 1), (1, 4), (4, 3), (3, 0)]); asserteq!(canonicalform(&c5), canonicalform(&other_c5));

let p5 = Graph::new(5, &[(0, 1), (1, 2), (2, 3), (3, 4)]); assert!(canonicalform(&c5) != canonicalform(&p5));

let p = canonicalformmorphism(&c5); asserteq!(c5.applymorphism(&p), canonical_form(&c5)); ```

License: MIT