[Nauty-list] 30 seconds to canonize an 82-node digraph

[Josh Jordan]

The adjacencies invariant fixed my earlier problem, but now I've hit an
82-node colored digraph that takes 30 seconds to canonize on my Athlon 64
3000+. This seems excessive, especially given how quickly nauty processes
most graphs. For some reason, I wasn't able to reproduce the problem in
dreadnaut, so I've included a small C program instead.

$ time ./testnauty

real    0m29.687s
user    0m29.686s
sys     0m0.000s

testnauty.c:
#define MAXN 255
#include "naututil.h"
#include "nautinv.h"

#define E(x,y) do { ADDELEMENT(GRAPHROW(g,x,MAXM),y); } while(0)

int main(void) {
  int lab[MAXN] = {
      0, 1, 32, 57, 68, 2, 3, 33, 34, 58, 59, 69, 70, 4, 5, 8, 9, 12, 13,
16,
      17, 20, 21, 24, 25, 28, 29, 35, 36, 51, 52, 60, 61, 71, 72, 6, 7, 10,
11,
      14, 15, 18, 19, 22, 23, 26, 27, 40, 41, 48, 49, 30, 31, 37, 38, 42,
43,
      44, 45, 46, 47, 53, 54, 55, 56, 62, 63, 65, 66, 73, 74, 76, 77, 79,
80,
      50, 39, 64, 67, 75, 78, 81
  };
  int ptn[MAXN] = {
    0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1,
1,
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
0,
    0, 1, 1, 1, 1, 1, 0
  };

  int orbits[MAXN];
  graph g[MAXN*MAXM];
  graph canong[MAXN*MAXM];
  static DEFAULTOPTIONS_GRAPH(options);
  statsblk stats;
  setword workspace[5*MAXM];
  int worksize = 5*MAXM;

  E( 0, 1); E( 0,32); E( 0,57); E( 0,68); E( 1, 2); E( 1, 3); E( 2, 4);
  E( 2, 8); E( 2,12); E( 2,16); E( 2,20); E( 2,24); E( 2,28); E( 3, 5);
  E( 3, 9); E( 3,13); E( 3,17); E( 3,21); E( 3,25); E( 3,29); E( 4, 6);
  E( 5, 7); E( 8,10); E( 9,11); E(12,14); E(13,15); E(16,18); E(17,19);
  E(20,22); E(21,23); E(24,26); E(25,27); E(28,30); E(29,31); E(32,33);
  E(32,34); E(33,35); E(33,51); E(34,36); E(34,52); E(35,37); E(35,40);
  E(35,42); E(35,44); E(35,46); E(35,48); E(36,38); E(36,41); E(36,43);
  E(36,45); E(36,47); E(36,49); E(37,40); E(38,49); E(39,30); E(39,31);
  E(39,37); E(39,38); E(40,42); E(41,38); E(42,44); E(43,41); E(44,46);
  E(45,43); E(46,48); E(47,45); E(48,37); E(49,47); E(50,40); E(50,41);
  E(50,48); E(50,49); E(51,53); E(51,55); E(52,54); E(52,56); E(53,55);
  E(54,56); E(55,53); E(56,54); E(57,58); E(57,59); E(58,60); E(59,61);
  E(60,62); E(60,65); E(61,63); E(61,66); E(62,65); E(63,66); E(64,53);
  E(64,54); E(64,62); E(64,63); E(65,62); E(66,63); E(67,55); E(67,56);
  E(67,65); E(67,66); E(68,69); E(68,70); E(69,71); E(70,72); E(71,73);
  E(71,76); E(71,79); E(72,74); E(72,77); E(72,80); E(73,76); E(74,80);
  E(75,42); E(75,43); E(75,73); E(75,74); E(76,79); E(77,74); E(78,44);
  E(78,45); E(78,76); E(78,77); E(79,73); E(80,77); E(81,46); E(81,47);
  E(81,79); E(81,80);

  options.getcanon = TRUE;
  options.defaultptn = FALSE;
  options.digraph = TRUE;
  options.invarproc = adjacencies;
  options.mininvarlevel = 0;
  options.maxinvarlevel = 99;

  /* this takes 30 seconds */
  nauty(g,lab,ptn,NULL,orbits,&options,&stats,workspace,worksize,MAXM,82,canong);
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20100604/f8346729/attachment.html