Algoritmo de canonização de gráfico simples

Estou procurando um algoritmo que forneça uma string canônica para um determinado gráfico colorido. Ou seja. um algoritmo que retorna uma string para um gráfico, de modo que dois gráficos obtenham a mesma string se e somente se forem isomórficos.

Em particular, estou procurando um algoritmo simples que seja fácil de implementar com um desempenho razoável na maioria dos gráficos (no pior dos casos, super polinomial, é claro). Estou esperando gráficos pequenos, para que o desempenho não precise ser estelar, apenas bom o suficiente.

Infelizmente, a maioria das coisas que encontrei são altamente complexas e mais interessadas em expressar conexões matemáticas profundas do que simplesmente descrever o algoritmo. Receio não ter tempo de mergulhar tão fundo. Alguém pode me dar um atalho?

Espero algo como o algoritmo de Floyd-Warshall. Não é ideal, mas bom o suficiente e fácil de implementar.

Brendan McKay e Adolfo Piperno escreveram uma pesquisa sobre esta questão em 2013. Eles apresentam vários programas de computador eficientes que canonizam muitos gráficos mais rapidamente do que você imagina. Não é necessário (e não faz sentido) implementar esses algoritmos você mesmo - eles estão disponíveis online, mesmo como código-fonte.

Acabei implementando o algoritmo Nauty, mas, ao fazê-lo, descobri uma resposta para minha própria pergunta. Nauty estende esse algoritmo básico com muitas heurísticas complicadas:

Dado um pequeno gráfico G de comprimento n:

1. Loop sobre todos ospermutações de seus vértices.$n!$
2. Gere uma representação de string de cada um (um para um).
3. Defina alguma ordem canônica de seqüências de caracteres e lembre-se da menor string encontrada.

Esse algoritmo é , Mas para gráficos pequenos deve funcionar bem.$O(n!)$

O Nauty estende esse algoritmo principalmente removendo o espaço de pesquisa dos gráficos a considerar, ao procurar aquele com a menor representação de string.