Trait canonical_form::Canonize

pub trait Canonize where
    Self: Sized + Ord + Clone, {
    fn size(&self) -> usize;
    fn apply_morphism(&self, p: &[usize]) -> Self;

    fn invariant_coloring(&self) -> Option<Vec<u64>> { ... }
    fn invariant_neighborhood(&self, _u: usize) -> Vec<Vec<usize>> { ... }
    fn canonical(&self) -> Self { ... }
    fn canonical_typed(&self, sigma: usize) -> Self { ... }
    fn morphism_to_canonical(&self) -> Vec<usize> { ... }
    fn morphism_to_canonical_typed(&self, sigma: usize) -> Vec<usize> { ... }
    fn automorphisms(&self) -> AutomorphismIterator<Self> { ... }
    fn stabilizer(&self, sigma: usize) -> AutomorphismIterator<Self> { ... }
}

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

An object that implement this trait has a set of elements assimilated to {0,...,n-1} on which the group of permutations can act. The purpose of the trait is to compute a normal form of the object modulo the permutation of its elements.

Required methods

fn size(&self) -> usize

Return the number of vertices.

The elements of self are assimilated to the number of 0..self.size().

fn apply_morphism(&self, p: &[usize]) -> Self

Return the result of the action of a permuation p on the object.

The input p is guarenteed to be a permutation represented as a slice of size self.size() where p[u] is the image of u by the permutation.

The action of the permutation set on Self is assumed to be a group action.

use canonical_form::Canonize;
use canonical_form::example::Graph;

let g = Graph::new(4, &[(1, 2), (2, 3)]);

let p = &[1, 2, 0, 3];
assert_eq!(g.apply_morphism(p), Graph::new(4, &[(2, 0), (0, 3)]));

let identity = &[0, 1, 2, 3];
assert_eq!(g.apply_morphism(identity), g);

let q = &[1, 0, 3, 2];
let p_circle_q = &[2, 1, 3, 0];
assert_eq!(
    g.apply_morphism(q).apply_morphism(p),
    g.apply_morphism(p_circle_q)
)

Loading content...

Provided methods

fn invariant_coloring(&self) -> Option<Vec<u64>>

Optionally returns a value for each node that is invariant by isomorphism.

If defined, the returned vector c must have size self.len(), where c[u] is the value associated to the element u. It must satisfy the property that if c[u] and c[v] are different then no automorphism of self maps u to v.

fn invariant_neighborhood(&self, _u: usize) -> Vec<Vec<usize>>

Return lists of vertices that are invariant isomorphism.

This function helps the algorithm to be efficient. The output invar is such that each invar[i] is a vector of vertices [v1, ..., vk] (so the vis are elements of 0..self.size()) such that for every permutation p, self.apply_morphism(p).invariant_neighborhood(p[u])[i] is equal to [p[v1], ..., p[vk]] up to reordering.

The length of the output (the number of lists) has to be independent from u.

fn canonical(&self) -> Self

Computes a canonical form of a combinatorial object.

This is the main function provided by this trait. A canonical form is a function that assigns to an object g (e.g. a graph) another object of sane type g.canonical() that is isomorphic to g with the property that g1 and g2 are isomorphic if and only if g1.canocial() == g2.canonical().

use canonical_form::Canonize;
use canonical_form::example::Graph;

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

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

fn canonical_typed(&self, sigma: usize) -> Self

The "typed" objects refers to the case where only the action of permutations that are constant on 0..sigma are considered.

So g.canonical_typed(sigma) returns a normal form of g modulo the permutations that stabilize the sigma first vertices.

use canonical_form::Canonize;
use canonical_form::example::Graph;

// p5 with the edge (0, 1) at an end
let p5 = Graph::new(5, &[(0, 1), (1, 2), (2, 3), (3, 4)]);
// p5 with the edge (0, 1) is in the middle
let p5_bis = Graph::new(5, &[(3, 4), (4, 1), (1, 0), (0, 2)]);
// If we fix the vertices 0 and 1, these two (rooted) graphs are different
assert!(p5.canonical_typed(2) != p5_bis.canonical_typed(2));

let p5_ter = Graph::new(5, &[(0, 1), (1, 3), (3, 4), (4, 2)]);
assert_eq!(p5.canonical_typed(2), p5_ter.canonical_typed(2));

fn morphism_to_canonical(&self) -> Vec<usize>

Return a permutation p such that self.apply_morphism(&p) = self.canonical().

use canonical_form::Canonize;
use canonical_form::example::Graph;

let g = Graph::new(6, &[(0, 1), (1, 2), (2, 3), (3, 4), (3, 5)]);
let p = g.morphism_to_canonical();
assert_eq!(g.apply_morphism(&p), g.canonical());

fn morphism_to_canonical_typed(&self, sigma: usize) -> Vec<usize>

Return a permutation phi such that g.apply_morphism(&phi) = canonical_typed(&g, sigma).

use canonical_form::Canonize;
use canonical_form::example::Graph;

let g = Graph::new(5, &[(0, 1), (1, 2), (2, 3), (3, 4)]);
let p = g.morphism_to_canonical_typed(2);
assert_eq!(g.apply_morphism(&p), g.canonical_typed(2));

fn automorphisms(&self) -> AutomorphismIterator<Self>

Iterator on the automorphism group of g.

The input g must be in normal form.

use canonical_form::Canonize;
use canonical_form::example::Graph;

let c6 = Graph::new(6, &[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)]).canonical();

let mut count = 0;
for p in c6.automorphisms() {
    assert_eq!(c6.apply_morphism(&p), c6);
    count += 1;
}
assert_eq!(count, 12);

fn stabilizer(&self, sigma: usize) -> AutomorphismIterator<Self>

Iterator on the automorphisms of g that fix the sigma first vertices.

The input g must be in normal form computed with canonical_typed.

use canonical_form::Canonize;
use canonical_form::example::Graph;

// Cube graph with one fixed vertex
let cube = Graph::new(8, &[(0, 1), (1, 2), (2, 3), (3, 0),
                           (4, 5), (5, 6), (6, 7), (7, 4),
                           (0, 4), (1, 5), (2, 6), (3, 7)]).canonical_typed(1);

let mut count = 0;
for p in cube.stabilizer(1) {
    assert_eq!(cube.apply_morphism(&p), cube);
    assert_eq!(p[0], 0);
    count += 1;
}
assert_eq!(count, 6);

Loading content...

Implementors

impl Canonize for Graph

fn size(&self) -> usize

fn apply_morphism(&self, perm: &[usize]) -> Self

fn invariant_neighborhood(&self, u: usize) -> Vec<Vec<usize>>

Loading content...