[−][src]Trait canonical_form::Canonize
Objects that can be reduced modulo the actions of a permutation group.
An object implement this trait if it has elements and if the group of permutations on of this elements acts on the object.
Required methods
fn size(&self) -> usize
Returns the number of vertices.
The elements of x
are assimilated to the number of 0..x.self()
.
fn apply_morphism(&self, perm: &[usize]) -> Self
Returns the result of the action of a permuation perm
on the object.
The permutation perm
is represented as a slice of size self.size()
where perm[u]
is the image of u
by the permutation.
Provided methods
fn invariant_coloring(&self) -> Option<Vec<u64>>
Can return a coloring that is invariant by isomorphism.
This coloring is expressed as a vector c
such that c[u]
is the color of u
. It need to 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.
The output inv
is a vector such that each inv[i]
is a vector
of distinct vertices [v1, ..., vk]
(so the vi
elements of 0..self.size()
) such that
for every permutation perm
,
self.invariant_neighborhood(perm[u])[i]
is equal to [perm[v1], ..., perm[vk]]
up to reordering.
The length of the output (the number of lists) has to be independent
of u
.