[Nauty] performance question

J.K.R. Bausch jkrb2 at cam.ac.uk
Tue Feb 26 02:36:40 AEDT 2019


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:

My task is to take the following graph:
https://i.ibb.co/X41KpsS/image.png
(in case the link does not work: https://imgur.com/H1FTZyQ or: it's a 
Star Graph with 12 spokes, on one of which we put another star graph of 
5 spokes, so it has 17 vertices overall; one has degree 12, another one 
has degree 6, and all others have degree 1).

1. For this graph, we randomly color it and want to find its canonical 
image.
2. I do this ~500k times.
3. This takes about 10000ms.
4. On average, this means one call is 0.02ms.

Is this the expected runtime? I would have assumed this to be faster, 
but maybe I'm mistaken. I've checked whether this has something to do 
with the coloring, but that makes negligible difference -- i.e. 
canonicalizing said graph 500k times without coloring takes about 10s as 
well.

This is compiled under gcc8, with O3 optimizations, static allocation, 
and MAXN set to 32, on an i5 4570.

Here's also a picture of valgrind's output:
http://i.imgur.com/qVEZ5xW.png

I'd be happy for any pointers.

Thanks!
- Johannes


More information about the Nauty mailing list