[Nauty] Another isomorphism problem for labeled graphs

[Brendan McKay]

The reason is that your coloured graphs are not isomorphic.  The
isomorphism is required to preserve the colours, so vertices in the
first cell of the first graph must map to vertices in the first cell
of the second graph.  However, in your colourings the first cell of the
first graph must map to vertices in the second cell of the second graph.
If you replace lab2[] by

  lab2[0] = 1;
  lab2[1] = 3;
  lab2[2] = 2;
  lab2[3] = 0;
  lab2[4] = 4;

then the result is "Identical".

If you want to have colours that can be swapped with other colours, you
can do it by appending additional vertices.  Add one vertex for each
colour and join it to the original vertices which have that colour.
Then use lab/ptn to distinguish between the old and new vertices and
also to indicate which new vertices can be exchanged.

Brendan.


* Arto J Akerlund, tkol <akerlund at cs.helsinki.fi> [040722 11:33]:
> Sorry for that lame newbie first post, I found the problem out by 
> myself. You can ignore it. Now here's a real trouble with which I've 
> had hard time trying to solve. I have two labeled graphs which should 
> be isomorphic, however, nauty says they aren't. The two graphs are as 
> follows and let's name them A and B:
> 
> Graph A:
>   0 :  1;
>   1 :  0 2;
>   2 :  1 3;
>   3 :  2 4;
>   4 :  3;
> 
> [ 0 4 | 1 3 | 2 ]
> 
> 
> Graph B:
>   0 :  1 4;
>   1 :  0;
>   2 :  3 4;
>   3 :  2;
>   4 :  0 2;
> 
> [ 0 2 | 1 3 | 4 ]
> 
> I hope there's just something I have done wrong and would be easily 
> corrected. This is a really important issue for me and I really 
> appreciate it if it'll get solved. 
> And here's the code which tests the isomorphism for those.
> 
> --BEGIN OF CODE
> 
> #define MAXN 100
> #include "nauty.h"
> #include "naututil.h"
> 
> main() {
>   static DEFAULTOPTIONS(options);
>   options.defaultptn = FALSE;
>   options.getcanon = TRUE;
>   options.writeautoms = FALSE;
>   statsblk(stats);
>   setword workspace[50*MAXN];
>   
>   graph g[MAXN*MAXN];
>   int lab[MAXN], ptn[MAXN], orbits[MAXN];
>   
>   int n,m;
>   set *gv;
>   
>   
>   n = 5;
>   m = (n + WORDSIZE - 1) / WORDSIZE;
>   nauty_check(WORDSIZE, m, n, NAUTYVERSIONID);
>   
>   gv = GRAPHROW(g, 0, m);
>   EMPTYSET(gv, m);
>   ADDELEMENT(gv, 1);
>   
>   
>   gv = GRAPHROW(g, 1, m);
>   EMPTYSET(gv, m);
>   ADDELEMENT(gv, 0);
>   ADDELEMENT(gv, 2);
>   
>   gv = GRAPHROW(g, 2, m);
>   EMPTYSET(gv, m);
>   ADDELEMENT(gv, 1);
>   ADDELEMENT(gv, 3);
>   
>   gv = GRAPHROW(g, 3, m);
>   EMPTYSET(gv, m);
>   ADDELEMENT(gv, 2);
>   ADDELEMENT(gv, 4);
>   
>   gv = GRAPHROW(g, 4, m);
>   EMPTYSET(gv, m);
>   ADDELEMENT(gv, 3);
>   
>   lab[0] = 0;
>   lab[1] = 4;
>   lab[2] = 1;
>   lab[3] = 3;
>   lab[4] = 2;
>   
>   ptn[0] = 1;
>   ptn[1] = 0;
>   ptn[2] = 1;
>   ptn[3] = 0;
>   ptn[4] = 0;
>   
>   
>   
>   
>   graph g2[MAXN*MAXN];
>   int lab2[MAXN], ptn2[MAXN];
>   
>   gv = GRAPHROW(g2, 0, m);
>   EMPTYSET(gv, m);
>   ADDELEMENT(gv, 1);
>   ADDELEMENT(gv, 4);
>   
>   gv = GRAPHROW(g2, 1, m);
>   EMPTYSET(gv, m);
>   ADDELEMENT(gv, 0);
>   
>   gv = GRAPHROW(g2, 2, m);
>   EMPTYSET(gv, m);
>   ADDELEMENT(gv, 4);
>   ADDELEMENT(gv, 3);
>   
>   gv = GRAPHROW(g2, 3, m);
>   EMPTYSET(gv, m);
>   ADDELEMENT(gv, 2);
>   
>   gv = GRAPHROW(g2, 4, m);
>   EMPTYSET(gv, m);
>   ADDELEMENT(gv, 0);
>   ADDELEMENT(gv, 2);
>   
>   lab2[0] = 2;
>   lab2[1] = 0;
>   lab2[2] = 1;
>   lab2[3] = 3;
>   lab2[4] = 4;
>   
>   ptn2[0] = 1;
>   ptn2[1] = 0;
>   ptn2[2] = 1;
>   ptn2[3] = 0;
>   ptn2[4] = 0;
>   
>   
>   
>   graph canong[MAXN*MAXN];
>   graph canong2[MAXN*MAXN];
>   
>   nauty(g, lab, ptn, NULL, orbits, &options, &stats, workspace, 50*MAXN, 
> m, n, canong);
>   nauty(g2, lab2, ptn2, NULL, orbits, &options, &stats, workspace, 
> 50*MAXN, m, n, canong2);
>   
>   if ( memcmp(canong,canong2,m*n*sizeof(graph)) ) {
>     printf("Not identical\n");
>   }
>   else {
>     printf("Identical\n");
>   }
> }
> 
> --END OF CODE
> 
> _______________________________________________
> This is the nauty mailing list
> Post messages to nauty-list at cs.anu.edu.au
> nauty page: http://cs.anu.edu.au/~bdm/nauty/
> list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list