[Nauty] limit on graph size

keith.briggs at bt.com keith.briggs at bt.com
Thu Jul 14 20:12:27 AEST 2016

Perhaps better than relying on int or long being a particular size is to use the C99 standard header [*]

#include <stdint.h>

and then uint64_t etc.


[*] http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/stdint.h.html

-----Original Message-----
From: Nauty [mailto:nauty-bounces at anu.edu.au] On Behalf Of Brendan McKay
Sent: 14 July 2016 11:04
To: nauty at anu.edu.au
Subject: Re: [Nauty] limit on graph size

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.

More information about the Nauty mailing list