Skip to main content

Module graph

ocas_atom::tensor

Module graph 

Source
Expand description

McKay refinement-individualisation graph canonical labelling engine.

§Algorithm

This is an independent implementation of the nauty-family algorithm:

  1. Initial colouring — vertices grouped by their data value.
  2. 1-WL refinement — neighbour signatures (edge-data + direction) split cells iteratively until the partition is equitable.
  3. Individualisation-refinement search — pick a vertex from the smallest non-trivial cell, individualise, refine, recurse (DFS).
  4. Pruning — path invariants (cell-length sequences) and automorphism orbits eliminate isomorphic branches.
  5. Canonical form — the lexicographically largest certificate among all discrete labelings encountered during the search.

§References

  • McKay, “Practical Graph Isomorphism” (1981/2014)
  • Symbolica graphica crate (MIT, algorithm reference only — no code copied)

Structs§

CanonicalForm
Result of canonisation.
EdgeIter
Iterator over edges incident to a vertex.
EdgeView
A single incident-edge descriptor.
Graph
A graph suitable for canonical labelling.