# [−][src]Crate canonical_form

Algorithms to reduce combinatorial structures modulo isomorphism.

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

```use canonical_form::*;

// Simple Graph implementation as adjacency list
#[derive(Ord, PartialOrd, PartialEq, Eq, Clone, Debug)]
struct Graph {
}

impl Graph {
fn new(n: usize, edges: &[(usize, usize)]) -> Self {
let mut adj = vec![Vec::new(); n];
for &(u, v) in edges {
}
}
}

// The Canonize trait allows to use the canonial form algorithms
impl Canonize for Graph {
fn size(&self) -> usize {
}
fn apply_morphism(&self, perm: &[usize]) -> Self {
let mut adj = vec![Vec::new(); self.size()];
for (i, nbrs) in self.adj.iter().enumerate() {
}
}
fn invariant_neighborhood(&self, u: usize) -> Vec<Vec<usize>> {
}
}

// Usage of library functions
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));```

## Structs

 AutomorphismIterator Iterator on the automorphisms of a combinatorial structure.

## Traits

 Canonize Objects that can be reduced modulo the actions of a permutation group.

## Functions

 canonical_form Computes a normal form of a combinatorial object. canonical_form_morphism Return a morphism `phi` such that `g.apply_morphism(phi) = canonical_form(g)`. canonical_form_typed Normal form of `g` modulo the isomorphisms that stabilize the sigma first vertices. canonical_form_typed_morphism Return a morphism `phi` such that `g.apply_morphism(phi) = canonical_form_typed(g, sigma)`.