[Nauty] isomorphism of graphs generated by geng

[Gordon Royle]

>
> does anyone know how to relable 2 isomorphic graphs so they are  
> identical - i think nauty should be able to do this, as it  
> generates the conanical form - you do that for both, and you should  
> be able to relable one to the other, but how do you get the  
> permutation to relable the input graph to the concanonised one?
>


This is relatively easy if you are calling nauty directly from your  
own C program...

When you make the call

nauty(g,lab,ptn, <other parameters omitted>)

(with options.getcanon = TRUE)  the array "lab" tells you how the  
vertices of the graph must be relabelled in order to produce the  
canonical labelling of the graph.

So lab[0] is the OLD name of vertex 0 in the canonical graph, lab[1]  
is the OLD name of the vertex 1 in the canonical graph etc.


So, let's suppose that you have done this with two graphs, g1 and g2,  
and have obtained two arrays lab1 and lab2 containing the labellings.

Then you will want to map lab1[0] to lab2[0], lab1[1] to lab2[1] and  
so on...