[Nauty] performance question
J.K.R. Bausch
jkrb2 at cam.ac.uk
Tue Mar 19 21:16:09 AEDT 2019
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
More information about the Nauty
mailing list