[Nauty] performance question

[Brendan McKay]

Hi Johannes,

There is no special option for trees.

There are practical very fast canonically labelling methods for trees,
but the following will be already 2-3 times faster than nauty or traces
applied routinely.  I'm assuming you don't want the group.

1.  Make the colour partition in lab/ptn.
2.  Call refine() with active set to the initial positions of each cell.
3.  While there is any nontrivial cell remaining do
        Individualise an arbitrary (say the first) vertex of the first 
nontrivial cell,
        and call refine() with active set to just that new singleton.

I hope this makes sense.  You have the choice of refine1() and refine()
in naugraph.c if your tree is in dense representation, or refine_sg() in
nausparse.c for sparse representation (which is probably better). Traces
also has a refinement routine you can use.

Brendan.

On 19/3/19 9:16 pm, J.K.R. Bausch wrote:
> 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
>
>
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> http://mailman.anu.edu.au/mailman/listinfo/nauty