[Nauty] sparse6 format and multigraphs

[Fidel Schaposnik]

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