#graph #combinatorics #group

canonical-form

Reduce graphs and other combinatorial structures modulo isomorphism

13 releases (breaking)

0.10.0 Apr 2, 2022
0.9.4 Sep 6, 2020
0.9.2 Oct 23, 2019
0.6.0 Jun 26, 2019
0.5.0 Jan 22, 2019

#1301 in Algorithms


Used in flag-algebra

MIT license

36KB
645 lines

canonical-form

Algorithm to reduce combinatorial structures modulo isomorphism.

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

The algorithm manipulates its input as a black box by the action of permutations and by testing equallity with element of its orbit, plus some user-defined functions that help to break symmetries.

use canonical_form::Canonize;

// Simple Graph implementation as adjacency lists
#[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);
       }
       for list in &mut adj {
           list.sort() // Necessary to make the derived `==` correct
       }
       Graph { adj }
   }
}

// The Canonize trait allows to use the canonial form algorithms
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()]
   }
}

// Usage of library functions
// Two isomorphic graphs
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!(c5.canonical(), other_c5.canonical());

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

// Recovering the permutation that gives the canonical form
let p = c5.morphism_to_canonical();
assert_eq!(c5.apply_morphism(&p), c5.canonical());

// Enumerating automorphisms
assert_eq!(c5.canonical().automorphisms().count(), 10)

License: MIT

No runtime deps