[Nauty] Another isomorphism problem for labeled graphs

Arto J Akerlund, tkol akerlund at cs.helsinki.fi
Thu Jul 22 11:19:01 EST 2004


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




More information about the Nauty mailing list