[Nauty] Canonically labeled output of nauty/Traces actually byte-wise unique?

[Adolfo Piperno]

> Il giorno 20 feb 2024, alle ore 02:50, Brendan McKay via Nauty <nauty at anu.edu.au> ha scritto:
> 
> Hi Johann,
> 
> The sparsegraph structure for a labelled graph can be non-unique in three ways.
> 1. The neighbours for a vertex can be listed in any order.
> 2. The neighbour lists in the e array might be in any order.
> 3. The neighbour lists in the e array can have gaps between them.
> 
> The sortlists_sg function corrects issue 1 but not issues 2 and 3.
> 
> However, I believe that the canonical output of nauty has none of these issues.
> That is, the neighbour lists are always sorted and in the natural order without gaps.
> I suggest you add code to check that and let me know if you find an exception.
> 
> As for Traces, probably the same is true but I'll consult Adolfo.

The canonical form is produced by Traces using the function updatecan_tr()
which is essentially the same as nauty’’s updatecan_sg().
- A


------------------
Adolfo Piperno
Dipartimento di Informatica
Sapienza Università di Roma
web: pallini.di.uniroma1.it