#graph #group #combinatorics

canonical-form

Reduce graphs and other combinatorial structures modulo isomorphism

12 releases (breaking)

0.9.4 Sep 6, 2020
0.9.2 Oct 23, 2019
0.8.0 Oct 20, 2019
0.6.0 Jun 26, 2019
0.5.0 Jan 22, 2019

#14 in Visualization

Download history 12/week @ 2020-06-27 13/week @ 2020-07-04 22/week @ 2020-07-11 2/week @ 2020-07-18 1/week @ 2020-08-01 25/week @ 2020-08-08 25/week @ 2020-08-15 6/week @ 2020-08-22 26/week @ 2020-08-29 50/week @ 2020-09-05 4/week @ 2020-09-12 4/week @ 2020-09-19 5/week @ 2020-09-26 16/week @ 2020-10-03 6/week @ 2020-10-10

63 downloads per month
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