[Nauty-list] 8 seconds to canonize a 21-node graph

[Brendan McKay]

Hi, It isn't a bug but rather a deficiency in how nauty treats directed
graphs.  There is an invariant "adjacencies" designed to prevent this.
In dreadnaut, add "*=13" before executing.  In general something like
"*=13 k=0 99" is good before processing digraphs with many strong
components.  This example takes about 40 microseconds by that method.

Brendan.

* Josh Jordan <josh at joshjordan.name> [100520 04:17]:
> nauty 2.4 (32 bits) on an Athlon 64 takes over 8 seconds to canonize the
> below 21-node digraph. Is this a bug? When I paste the input into dreadnaut,
> it prints:
> 
> 21 orbits; grpsize=1; 0 gens; 12004357 nodes (6220640 bad leaves); maxlev=14
> tctotal=12004356; canupdates=160; cpu time = 8.27 seconds
> 
> nauty 2.2 takes about the same amount of time.
> 
> ===== begin input to dreadnaut =======
> -a+c+d-m
> n=21
> e
>   0 :  1;
>   1 :  2 3 4;
>   2 :  3;
>   3 :  4;
>   4 :  2;
>   5 :  6;
>   7 :  2 8;
>   9 :  10 12;
>  10 :  11;
>  12 :  14;
>  13 :  3 14;
>  15 :  16 18;
>  16 :  17;
>  18 :  20;
>  19 :  20;
> .
> x
> ===== end input to dreadnaut =======

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