[Nauty] sparsenauty and multigraphs

[Brendan McKay]

Sparsenauty does NOT work on multigraphs.  There are several key
routines that are simple-graph only.

This is clearly unsatisfactory and one day it will change. Meanwhile
you can use the method described in the manual for representing
a multigraph as a simple graph.

Adolfo Piperno is fine-tuning a version of Traces that handles
multigraphs, but it isn't available for production work yet.

Brendan.

On 29/9/20 7:17 am, Erik Panzer wrote:
> Hello,
>
> does anyone here know if sparsenauty is supposed to work on multigraphs?
>
> The sparsegraph data structure and the sparse6 file​ format support multigraphs, and I have used the function sparsenauty() to obtain canonical labels. This works fine in many cases, but not always: the canonicalized graph always appears to be isomorphic to the input, but there are examples of isomorphic graphs that yield different canonicalizations (see below).
>
> I know that there are ways to transform multigraphs into simple graphs (which is perfectly fine as a workaround in my application, since nauty is so incredibly efficient), and there are plenty disclaimers in the manual that dreadnaut and most of the tools provided with nauty/traces do not support multigraphs. But reading the documentation, I was left under the impression that these were merely shortcomings of the toolkit programs, and not limitations to sparsenauty() itself. I found no indication against the use of multigraphs in the relevant section 12 of the manual, and sparsenauty() runs fine, without any error messages, for multigraph inputs.
>
> With thanks, and best wishes,
> Erik
>
> Example graphs with 6 vertices and 11 edges:
>
> sg1 = :E_GEA_w at N
> 0 : 1 1 2 3 4 5 5
> 1 : 2
> 2 : 3
> 3 : 4
> 4 : 5
> 5 :
> sg2 = :E_HEQcwDN
> 0 : 1 1 5
> 1 : 2 2 3 4 5
> 2 : 3
> 3 : 4
> 4 : 5
> 5 :
>
> Using sparsenauty(&sg,...,&cg) and sortlists_sg(&cg) I get
>
> cg1 = :EgW_WCaKs
> 0 : 3 4 5
> 1 : 2 4 5
> 2 : 5 5
> 3 : 5 5
> 4 : 5
> 5 :
> cg2 = :EgW_gCQKs
> 0 : 3 4 5
> 1 : 2 5 5
> 2 : 4 5
> 3 : 5 5
> 4 : 5
> 5 :
>
> which are isomorphic (relabel 1<->2) but not aresamge_sg(&cg1,&cg2).
>
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> http://mailman.anu.edu.au/mailman/listinfo/nauty