[Nauty] performance question

[J.K.R. Bausch]

Dear all,

@Brendan, Adolfo: thanks a lot! That was really helpful, seems like I'm 
using it correctly.

A quick question: is there a flag one can set for the special case of 
trees? I.e. if I'm promised to be given a tree and want to find its 
canonical image (with vertex colors), can we solve this problem faster?

Thanks a lot again!
Best,
Johannes

On 2019-02-25 17:11, Adolfo Piperno wrote:
> Hi Johannes
> 
>> Il giorno 25 feb 2019, alle ore 16:36, J.K.R. Bausch <jkrb2 at cam.ac.uk> 
>> ha scritto:
>> 
>> Hey everyone,
>> 
>> quick question. On http://pallini.di.uniroma1.it under "Experiments" 
>> the general performance appears to be such that a graph of <100 
>> vertices takes from 1e-6 to 1e-2 ms, depending on the family of 
>> course. As a sanity check I wanted to compare this to my setup:
> 
> in all performance figures, time is in secs, not ms. By the way, I
> attach what I get
> on my mac with an Apple LLVM compiler (O3 flag on, 3,1 GHz Intel Core 
> i7).
> Best
> - A
> 
> nauty27rc2 17:36 $ ./dreadnaut
> Dreadnaut version 2.7 (64 bits).
>> AS
>> <G/G17
>> t
>   1 :  2 3 4 5 6 7 8 9 10 11 12;
>   2 :  1;
>   3 :  1;
>   4 :  1;
>   5 :  1;
>   6 :  1;
>   7 :  1;
>   8 :  1;
>   9 :  1;
>  10 :  1;
>  11 :  1;
>  12 :  1 13 14 15 16 17;
>  13 :  12;
>  14 :  12;
>  15 :  12;
>  16 :  12;
>  17 :  12;
>> M500000
>> -acx
> 4 orbits; grpsize=435456000; 13 gens; 105 nodes; maxlev=14
> canupdates=1; cpu time = 0.0000127 seconds         <—— SPARSE NAUTY
>> AT+
>> x
> 4 orbits; grpsize=435456000; 4 gens; 1 node (1 peak); maxlev=0
> canupdates=0; cpu time = 0.0000096 seconds      <—— TRACES
>> AD+
>> x
> 4 orbits; grpsize=435456000; 13 gens; 105 nodes; maxlev=14
> canupdates=1; cpu time = 0.0000144 seconds       <—— DENSE NAUTY
> 
> 
> 
> ------------------------------------
> Adolfo Piperno
> Dipartimento di Informatica
> Sapienza Università di Roma
> tel: +39 06 49918514
> web: pallini.di.uniroma1.it