[Nauty] isomorphism of graphs generated by geng
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 is the OLD name of vertex 0 in the canonical graph, lab
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 to lab2, lab1 to lab2 and
More information about the Nauty