canonical-form

Algorithm to reduce combinatorial structures modulo isomorphism.

This can typically be used to to test if two graphs are isomorphic.

The algorithm manipulate its input by actions of permutations and by testing equallity, plus some user-defined functions that help to break symmetries.

```rust use canonical_form::Canonize;

// Simple Graph implementation as adjacency lists

[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!(c5.canonical(), other_c5.canonical());

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

let p = c5.morphismtocanonical(); asserteq!(c5.applymorphism(&p), c5.canonical()); ```

License: MIT