[Nauty] limit on graph size

Brendan McKay Brendan.McKay at anu.edu.au
Thu Jul 14 20:03:47 AEST 2016

Hi Simon,

I can recall when I couldn't imagine that anyone would ever need more 
than 32,000 vertices.

You are right: in the present code there are very many places where 
"int" is used for a vertex number, or perhaps one more than a vertex number.

On the other hand, I can't think of a fundamental reason why it wouldn't 
work past 2^32 vertices just by changing all the necessary ints into 
long ints.  Probably the simplest way would be to change all ints into 
long ints and then back off for the few library functions, etc, that 
need genuine ints. If you try this and it works, please let me know.


On 14/07/2016 7:10 PM, Simon Burton wrote:
> Hi,
> I'm building some large sparse graphs, with 10^6 nodes,
> and so far nauty has no trouble with these because the
> nodes are sufficiently well partitioned and the degree
> of each vertex is small.
> The documentation seems to suggest that there is an
> upper limit of 2*10^9 nodes? Is this correct? I have a
> graph with 2^32 nodes which exceeds this.
> It seems there are plenty of uses of the "int" datatype
> in nauty which is still only 4 bytes on a 64 bit machine.
> This would seem to prohibit making such a large graph.
> thanks,
> Simon.
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> http://mailman.anu.edu.au/mailman/listinfo/nauty

More information about the Nauty mailing list