[Nauty] sparse6 format and multigraphs

Brendan McKay Brendan.McKay at anu.edu.au
Sat Apr 30 00:34:12 AEST 2022


Hi Fidel,

Thanks for pointing this out.  Sparse6 format does support multigraphs,
but the tools in the package, including nauty itself, do not. Shortg
does not.  This should be corrected but it is a huge task as many
of the algorithms are limited to simple graphs.

What you need to do is encode your multigraphs as simple graphs.
The first example in chapter 14 of the manual explains it.

Good luck, Brendan.

On 29/4/2022 11:43 pm, Fidel Schaposnik wrote:
> Hi,
>
> I am having trouble understanding the sparse6 format, which seems like the
> (correct? intended? only?) way to use nauty with multigraphs. To put a
> concrete example, according to the format specification in the
> documentation the encoding for the graph with two nodes and two edges
> between these is ":Ab\n": the 'A' character corresponds to n = 2 nodes, and
> the 'b' character to (b=1, x=0) and (b=0, x=1) in the notation of the
> documentation. However:
>
> - When I run listg on this input (which is supposed to support sparse6), I
> get:
>
> Graph 1, order 2.
>    0 : ;
>    1 : ;
>
> - When I run showg instead (which again is supposed to support sparse6), I
> get:
>
> Graph 1, order 2.
>    0 : 1;
>    1 : 0;
>
> These two outputs are not consistent with one another, and moreover do not
> correspond to the input graph if I'm understanding the encoding correctly.
>
> Inspecting the source code, I believe the difference arises from the fact
> that listg adds edges through (line 896 in gtools.c):
>
> FLIPELEMENT(GRAPHROW(g,v,m),j);
>
> so adding an edge twice cancels out, whereas showg adds edges through (line
> 684 in showg.c):
>
> ADDELEMENT(GRAPHROW(g,v,m),j);
>
> and this is defined by
>
> #define ADDELEMENT(setadd,pos) ((setadd)[SETWD(pos)] |= bit[SETBT(pos)])
>
> so adding an edge more than once has no effect. Note that neither of these
> seems to be a viable choice for multigraphs, so my questions are:
>
> - Does nauty / gtools actually support multigraphs through the sparse6
> format? If so, which are the "safe" tools we can use in this case?
>
> - Most importantly, would the output of shortg be correct for a list of
> multigraphs in sparse6 format (at least when using the -k argument flag to
> keep the original labelling)?
>
> Thanks for your help,
>
> Best,
> Fidel I. Schaposnik Massolo
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> https://mailman.anu.edu.au/mailman/listinfo/nauty


More information about the Nauty mailing list