[Nauty-list] 30 seconds to canonize an 82-node digraph
Josh Jordan
josh at joshjordan.name
Fri Jun 4 20:21:30 EST 2010
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
More information about the Nauty
mailing list