Automorphism groups for CSets - generalizing the nauty algorithm to a broad class of data structures
Author AlgebraicJulia
12 Stars
Updated Last
1 Year Ago
Started In
August 2021

CSetAutomorphisms.jl CSetAutomorphisms.jl Documentation Tests

Attributed C-sets encompass a broad class of data structures, including many generalizations of graphs (e.g. directed, symmetric, reflexive), tabular data (e.g. data frames), and combinations of the two (e.g. weighted graphs, relational databases). This repo generalizes the Nauty algorithm, which produces canonical members of an isomorphism class, to cover any data structure encompassed by C-Sets. Furthermore, we compute and represent orbits and full automorphism groups of a C-Set, which can be applied to solving certain problems (e.g. searching for homomorphisms from A to B, up to isomorphism).

More background is found in the documentation or this blog post.

To do

  • The recently-released CompTime.jl will make it feasible to reimplement the core algorithm using code custom generated for a given C-Set, offering new opportunities for performance improvements.
  • For now, it is recommended to just use NautyInterface which reduces a C-Set automorphism problem to an undirected simple graph automorphism problem, which is fed to nauty.c.