[Nauty] Isomorphism test of labeled graphs

[Brendan McKay]

Sorry, I somehow missed your message before.  In order for two labelled
graphs to be isomorphic they must have the same number of vertices of
each colour.  This is not tested by nauty!

*If* the graphs have the same number of vertices of each colour, then
you can test the graphs for isomorphism by finding the canonical graphs
and comparing those.

Incidentally, the values you put in ptn[] are examined for zero or
non-zero only, so there is no point in using values other than 0 and 1
(but it doesn't hurt either).

Brendan.


> From Jacek P Kukluk <kukluk at uta.edu> -----
> 
> I am calling nauty functions to test isomorphism in larger program. I
> tested successfully unlabeled graphs. I need help in understanding how
> to use nauty for graphs with labels. For example the two graphs below
> are not isomorphic because they have different labels. 
>  
> G1= 
> A--------------------------A
>   |                                  |
>   |                                  |
>  A--------------------------A
>  
> G2= 
> A--------------------------A
>   |                                  |
>   |                                  |
>  B--------------------------B
>  
> According to nauty user;s guide I can use graph *g to represent the
> structure and arrays int  *lab, *ptn to represent labels as colors. My
> representation of G1 is 
>   0 :  1 3;
>   1 :  0 2;
>   2 :  1 3;
>   3 :  0 2;
> lab[0]=0;   lab[1]=1;   lab[2]=2;  lab[3]=3;
> ptn[0]=1;   ptn[1]=1;   ptn[2]=1;  ptn[3]=0;
>  
> G2 
>   0 :  1 3;
>   1 :  0 2;
>   2 :  1 3;
>   3 :  0 2;
> lab[0]=0;   lab[1]=1;   lab[2]=2;   lab[3]=3;
> ptn[0]=1;   ptn[1]=0;   ptn[2]=2;   ptn[3]=0;
>  
> I am setting 
> options.defaultptn = FALSE;
> and using modified dreadnaut to check isomorphism. I am comparing if the
> contents of canong produced by nauty for both graphs is the same. It
> works well for unlabeled graphs but seems to be not enough for labeled
> graphs.  What additional checking should I do? 
>  
> What would be the proper use of lab, ptn and nauty with labeled graphs,
> as in this case? How should I represent G1 and G2 if all vertices of G1
> would be labeled A and all vertices of G2 labeled B?
>  
> I will greatly appreciate any suggestion. 
>  
> Jacek
> 
> ----- End forwarded message -----
> 
> -- 
> Paulette Lieby
> 
> ph:     04 2222 4626
> email:	paule at maths.usyd.edu.au