[Nauty] sparsenauty and multigraphs

[Erik Panzer]

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