[Nauty] sparse6 format and multigraphs

Fidel Schaposnik fidel.s at gmail.com
Fri Apr 29 23:43:49 AEST 2022


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

Graph 1, order 2.
  0 : ;
  1 : ;

- When I run showg instead (which again is supposed to support sparse6), I

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):


so adding an edge twice cancels out, whereas showg adds edges through (line
684 in showg.c):


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,

Fidel I. Schaposnik Massolo

More information about the Nauty mailing list