[Solved]: Simple graph canonization algorithm

Problem Detail: 

I'm looking for an algorithm that provides a canonical string for a given colored graph. Ie. an algorithm that returns a string for a graph, such that two graphs get the same string if and only if they are isomorphic.

In particular, I'm looking for a simple algorithm that is easy to implement with a reasonable performance on most graphs (worst case super-polynomial, of course). I'm expecting small graphs, so performance doesn't have to be stellar, just good enough.

Unfortunately, most things I've found are highly complex and more interested in expressing deep mathematical connections than simply describing the algorithm. I'm afraid I don't have the time to dive that deep. Can anyone give me a shortcut?

I'm hoping for something like the Floyd-Warshall algorithm. Not optimal, but good enough, and easy to implement.

Asked By : Peter

Answered By : Peter

I ended up implementing the Nauty algorithm, but in doing so, I did figure out an answer to my own question. Nauty extends this basic algorithm with many complicated heuristics:

Given a small graphs G of length n:

1. Loop over all $n!$ permutations of its vertices.
2. Generate a string representation of each (one-to-one).
3. Define some canonical ordering of strings, and remember the smallest string encountered.

This algorithm is $O(n!)$, but for small graphs it should work fine.

Nauty extends this algorithm primarily by pruning the search space of graphs to consider, when looking for the one with the smallest string representation.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14354