[Nauty-list] graph isomorphism

[Gordon Royle]

On 20/01/2009, at 7:35 AM, Abid Muslim Malik wrote:

> Dear all;
>
> I am using the Nauty to find graph isomorphism in a problem. In the  
> problem each node is colored. Now my questions are:
>
> 1) How can I insert/jeep record of each node in the graph. You have  
> "ADDELEMENT(s,i)" function,  which adds  element i  to set s etc.  
> But, I could not find a function which keeps a record of a  
> particular characteristic of a given node; e.g. color. May be I am  
> missing here. ( I am dealing with Directed Acyclic Graphs (DAGs) in  
> compiler where each node is an instruction,  which can be store/ 
> load, branch, floating point, fixed point instruction. I need to  
> compare this information as well to check the isomorphism).

You need to keep track of any auxiliary information, such as vertex  
colours, yourself...

If you want nauty to only permute vertices within colour classes then  
you use the arrays "lab" and "ptn" to define an initial partition on  
the vertex set.

For example, if vertices 0, 4 and 5 are "green", vertices 1 and 3 are  
"red" and vertex 2 is "blue" then you would make sure that "lab"  
contains

0 4 5 1 3 2

and "ptn" contains markers to show where each colour class ends...

1 1 0 1 0 0

Then nauty will only consider permutations that permute vertices  
WITHIN each colour class..

>

> 2) In order to check two graphs, you have to produce canonical  
> labelling of each graph. If they are same then they are identical.  
> right???

If the canonical labelling is the same then the graphs are isomorphic


A/Prof Gordon Royle
gordon at maths.uwa.edu.au
School of Mathematics & Statistics
University of Western Australia