[Nauty] all nonisomorphic graphs with 10 vertices

[Brendan McKay]

* Thomas Ortlepp <ortlepp at gmx.de> [021010 16:49]:
> Hello again,
> 
> >> How long does it take, to calculate all
> >> nonisomorthic graphs with up to 10
> >> vertices by using nauty?
> 
> >On my 866 MHz Pentium III (running Linux) it takes 38 seconds.
> >It can be done in less than 20 seconds by generating them up
> >to 22 edges then adding the complement of each graph.
> 
> Its clear to go from 0 to 22 edges and mirror the data,
> but your anser is very suprising for me?
> Just for 22 edges, you have to generate 45 over 22 different
> graphs. These are  4.116.715.363.800  graphs witch have
> to sorted by using an isomorpic algorithm.
> It is well known, that the number of nonisomorphic graph
> for 10 vertices is 12.005.168. Please make sure that you
> find this number of graphes?

Correct.  The algorithm does not make all graphs then sort
them for isomorphism.  It uses a more complicated method that
does not require storing more than a few graphs at a time.
It is described in
   B. D. McKay, Isomorph-free exhaustive generation,
   J Algorithms, 26 (1998) 306-324.
A copy with errata included can be found at
   http://cs.anu.edu.au/~bdm/publications.html  (paper 96).
 
Making the 11-vertex graphs takes a bit less than an hour,
and the 12-vertex graphs about 6 days.  As far as I know
nobody ever made all 50502031367952 of the 13-vertex graphs,
but it could be done on one of our big parallel machines in
a few weeks if there was ever a good reason.

> I am not sure how fast your algorithm is, but if
> your calculation is correct I have to take my hat off.

Well, thank you :-).

Brendan.