nauty/genbg apparently hitting 32-bit limit, failing silently

[Andrew Juell]

As I discovered on CoCalc running Sage 9.1, it appears that any attempt to use nauty/genbg to build bipartite/hyper-/di- graphs with more than 32 total vertices fails silently.

Please compare the results of:

---------

L=list(hypergraphs.nauty(13, 13, uniform=2, regular=2,max_intersection=1))

for i in L:

    print i

print "done"

---------

L=list(hypergraphs.nauty(17, 17, uniform=2, regular=2,max_intersection=1))

for i in L:

    print i

print "done"

---------

CoCalc support confirmed the behavior, and suggested the issue was in Sage, referring me (through the FAQ) to address it here.

I believe there's a nauty compiler option that defaults to 32-bit words but can be set to use 64-bit .... WORDSIZE? Shouldn't happen often, but even then would probably be best to give an error for going over 64 vertices.

Thanks!

[Dima Pasechnik]

The code in question calls nauty's genbg program, and hypergraphs are
encoded as vertex-(hyper)edge incidence graphs. It seem that one needs
to read its source code (e.g. here:
https://github.com/lonnen/nauty/blob/nauty27/genbg.c)
to understand how the limits are controlled, there are parameters
called MAXN (defaulting to WORDSIZE), MAXN1 (probably, the number of
vertices in one part of the graph, at most 24 or 30, something like
this - and this is probably the # of vertices of the hypergraph)

It should not be too hard to change, but it would to good to to know
how exactly.

HTH
Dima

> --
> You received this message because you are subscribed to the Google Groups "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/13c7e84e-a172-473d-a548-c65ff24924cao%40googlegroups.com.

[slelievre]

Le samedi 6 juin 2020 22:53:13 UTC+2, Dima Pasechnik a écrit :
>
> The code in question calls nauty's genbg program, and hypergraphs are
> encoded as vertex-(hyper)edge incidence graphs. It seem that one needs
> to read its source code (e.g. here:
> https://github.com/lonnen/nauty/blob/nauty27/genbg.c)
> to understand how the limits are controlled, there are parameters
> called MAXN (defaulting to WORDSIZE), MAXN1 (probably, the number of
> vertices in one part of the graph, at most 24 or 30, something like
> this - and this is probably the # of vertices of the hypergraph)
>

> It should not be too hard to change, but it would be good to know
> how exactly.

Brendan McKay asks me to post this on his behalf:

> The nauty makefile has a target genbgL which makes

> a version allowing up to 30 vertices on the first side

> and 64 vertices altogether.
>
> There are two versions because using 64-bit words

> gives a tiny inefficiency for small sizes.  But this is now

> quite small (less than 1% usually) so I recommend that

> sage uses genbgL for everything.

[Dima Pasechnik]

will be fixed on https://trac.sagemath.org/ticket/29821

> --
> You received this message because you are subscribed to the Google Groups "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/f0cdf1f8-67f8-488b-a2d0-4247bd88fa38o%40googlegroups.com.

[Dima Pasechnik]

done, please review