[Nauty] sparse6 format and multigraphs

[Fidel Schaposnik]

Dear Brendan,

Thanks for your prompt and clear reply, I will proceed as you suggest. I'm
guessing implementing this transformation under-the-hood in nauty is not an
option, since it would be less efficient than implementing
multigraph-isomorphism algorithms directly, right? Anyway, it would be nice
to have nauty and gtools report errors / skip graphs when encountering
invalid input, since the current situation (quietly producing incorrect
output) may lead to confusion.

Best regards,
Fidel

PS: I am ashamed, but in my original email I forgot to say, first and
foremost, thanks for making available and maintaining such a great set of
tools :-)

On Fri, Apr 29, 2022 at 4:40 PM Brendan McKay <Brendan.McKay at anu.edu.au>
wrote:

> 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
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> https://mailman.anu.edu.au/mailman/listinfo/nauty
>