[Nauty] graph compression of sparsegraphs

[Brendan McKay]

Hi Ibrahim,

If you want to store sparse graphs in memory, one way is to use sparse6
strings.  There are procedures for this in the file naugstrings.c in the
nauty package.  For example, a cubic graph with 1000 vertices needs
2973 bytes.

If you want to compare canonical forms without needing to reconstruct
the graphs, and you are willing to bear a probability less than 10^{-70}
that two might compare equal when they aren't, you can use the
procedures in nausha.c to make 32-byte hash codes of cryptographic
quality.  If you do find two different graphs with the same hash codes
make sure you keep them as you will be famous.

Cheers, Brendan.

On 28/10/2025 10:24 pm, ibrahim via Nauty wrote:
> Dear all
>
> I was wondering if someone within the nauty community knows of a 
> particular
> library or piece of code that compresses nauty graphs as compactly as 
> possible
> but also as fast as possible (analogously, decompresses as fast as 
> possible).
>
> For example
>
> ```c
> typedef struct
> {
>     size_t nde;  /* Number of directed edges (loops contribute only 1) */
>     size_t *v;   /* Array of indexes into e[*] */
>     int nv;      /* Number of vertices */
>     int *d;      /* Array with out-degree of each vertex */
>     int *e;      /* Array to hold lists of neighbours */
>     sg_weight *w;      /* Not implemented, should be NULL. */
>     size_t vlen,dlen,elen,wlen;  /* Sizes of arrays in units of type */
> } sparsegraph;
> ```
>
> Given an adjacency list representation of a graph, such as the struct 
> sparsegraph,
> if there are only 1024 vertices in the graph, you only need 10 bits to 
> represent
> each vertex. Reducing the space needed from 32 bits or 64 bits to 10 
> bits per vertex.
>
> Did someone maybe already do this that I'm unaware of ? thanks!
>
>
> Kind regards
> El Kaddouri Ibrahim
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> https://mailman.anu.edu.au/mailman/listinfo/nauty