canonical labelling in nauty (McKay)

So firstly, there is a good explanation (with diagrams) in the 'Introduction' page of the website you link to : https://pallini.di.uniroma1.it/Introduction.html

However, understanding that explanation may require some more basic aspects of these types of algorithm. Sadly, it requires some terminology. So consider this:

1. An isomorphism between two graphs is a mapping between the vertices
2. For example, in the diagram you show, you could map vertex 7 in the top left graph to 5 in the top right graph
3. Continuing, we could map {2 -> 3, 1 -> 1, 6 -> 0 } and so on
4. Of course this ignores the colors of the vertices

One really simple way to find this mapping (isomorphism) would be to rearrange the labels (the numbers) on one of the graphs in all possible ways, and check if that makes the 'same' graph. Unfortunately there are n! permutations of n elements, so that's not an efficient approach.

A key detail here is how to check if a rearrangement of the labels (a 'labelling') makes an isomorphism. Since the labels are numbers, they have a natural order (1, 2, 3, 4...). So an obvious way to check is to write out the structure of the labelled graph as a string - like the top-right example you have would be 0:1,0:7,1:2,1:3,1:6,2:3,2:4,2:6 and so on. This is a 'certificate' for the graph.

When we try all possible labellings, we are essentially generating a set of certificates for the graph. If we pick one of these and consider it to be 'canonical' then all we need to do is compare the canonical certificates for two graphs and check if the certificates are equal.

For the example you give, the canonical labelling procedure has given different certificates for the two colored graphs. This is clear from just comparing the edges of vertex 0 - {0:1,0:4,0:6,0:7} on the left and {0:1,0:5,0:6,0:7} on the right.

Now, finally we have the point of nAUTy's algorithm (and that of many similar ones) - to efficiently generate a canonical member of the isomorphism class of a graph. Doing this with partition refinement means, roughly:

1. Creating an initial partition of the vertices
2. Refining that partition until equitable
3. Using individualization-refinement to refine partitions until discrete

So a lot of that terminology is undescribed (but see the nAUTy/Traces page) but it is essentially a method to search through a tree of partitions where the leaves are relabellings of the vertices. It does so efficiently by not visiting every leaf, pruning by tree node invariants.