[Nauty] Canonically labeled output of nauty/Traces actually byte-wise unique?
Adolfo Piperno
piperno at di.uniroma1.it
Tue Feb 20 18:20:25 AEDT 2024
> 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
More information about the Nauty
mailing list