Algoritma kanonisasi grafik sederhana

Saya mencari algoritme yang menyediakan string kanonik untuk grafik berwarna yang diberikan. Yaitu. sebuah algoritma yang mengembalikan string untuk grafik, sehingga dua grafik mendapatkan string yang sama jika dan hanya jika mereka isomorfik.

Secara khusus, saya mencari algoritma sederhana yang mudah diimplementasikan dengan kinerja yang masuk akal pada sebagian besar grafik (tentu saja kasus terburuk super-polinomial). Saya mengharapkan grafik kecil, jadi kinerja tidak harus menjadi bintang, cukup baik.

Sayangnya, sebagian besar hal yang saya temukan sangat kompleks dan lebih tertarik untuk mengekspresikan koneksi matematika yang mendalam daripada hanya menggambarkan algoritma. Saya khawatir saya tidak punya waktu untuk menyelam sedalam itu. Adakah yang bisa memberi saya jalan pintas?

Saya berharap untuk sesuatu seperti algoritma Floyd-Warshall. Tidak optimal, tetapi cukup baik, dan mudah diimplementasikan.

Brendan McKay dan Adolfo Piperno telah menulis makalah survei tentang pertanyaan ini pada tahun 2013. Mereka menyajikan beberapa program komputer yang efisien yang mengkanonik banyak grafik lebih cepat daripada yang Anda bayangkan. Tidak perlu (dan tidak ada gunanya) dalam mengimplementasikan algoritma ini sendiri - mereka tersedia secara online, bahkan sebagai kode sumber.

Saya akhirnya mengimplementasikan algoritma Nauty, tetapi dengan melakukannya, saya menemukan jawaban untuk pertanyaan saya sendiri. Nauty memperluas algoritma dasar ini dengan banyak heuristik rumit:

Diberikan grafik kecil G panjang n:

1. Ulangi semua $n!$ permutasi dari simpulnya.
2. Hasilkan representasi string masing-masing (satu-ke-satu).
3. Tetapkan beberapa urutan kanonik string, dan ingat string terkecil yang ditemui.

Algoritma ini adalah $O(n!)$, tetapi untuk grafik kecil itu harus berfungsi dengan baik.

Nauty memperluas algoritma ini terutama dengan memangkas ruang pencarian grafik untuk dipertimbangkan, ketika mencari yang memiliki representasi string terkecil.