[Nauty] isomorphism of graphs generated by geng
Gordon Royle
gordon at csse.uwa.edu.au
Mon Jun 27 13:56:01 EST 2005
>
> 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...
More information about the Nauty
mailing list