Trait canonical_form::Canonize

source · [−]
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>ⓘNotable traits for AutomorphismIterator<F>impl<F: Canonize> Iterator for AutomorphismIterator<F>    type Item = Vec<usize>; { ... }

    fn stabilizer(&self, sigma: usize) -> AutomorphismIterator<Self>ⓘNotable traits for AutomorphismIterator<F>impl<F: Canonize> Iterator for AutomorphismIterator<F>    type Item = Vec<usize>; { ... }
}
Expand description

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

Return the number of vertices.

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

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)
)

Provided methods

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.

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.

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());

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));

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());

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));

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);

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);

Implementors