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

[Brendan McKay]

It crashed for me, but that's because you forgot to zero the graph
before adding edges.  Adding  "EMPTYSET(g,MAXN*MAXM);"  it does indeed
take a surprising amount of time.  You can fix that by increasing
the workspace.  Instead of 5*MAXM, try 50*MAXM.  Then it will take
about 1 millisecond.  I never saw an example where the amount of
workspace has such a dramatic effect.  There is a better mechanism
under development for the next release.

The maximum usable amount of workspace is 2*m*k where k is the
number of generators.

Brendan.

* Josh Jordan <josh at joshjordan.name> [100604 20:22]:
> 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);
> }

> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list