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

[Johann Birnick]

Okay forget the part with "same number of vertices and edges", otherwise 
they won't be isomorphic of course. I also now found the part of the 
documentation where it says that I should probably apply `sortlists_sg` 
if I understand it correctly. But I'm still interested if there are 
special cases where I can avoid this?

Johann

On 2/19/24 14:49, Johann Birnick wrote:
> Hello,
>
> for my application of nauty/Traces, I'm building a 'database' of some 
> data of some graphs in the form of a hashtable. That is, to store data 
> attached to some graph, my plan is to canonically label it and then 
> take the hash of the canonically labeled graph and then store some 
> data (think: graph invariants) of the graph in a hashtable.
>
> For this, it would be important to know if the canonically labeled 
> graph which is returned from say Traces is guaranteed to be unique up 
> to actual byte representation?
>
> More precisely: Take two isomorphic graphs. For each of them, 1. call 
> Traces and get a `sparsegraph` object which is the canonically labeled 
> graph, and then 2. compute the hash of this sparsegraph. Will the 
> hashes be the same?
>
> (It doesn't seem like it, as in the example programs always 
> `aresame_sg` is called, which seems to do some nontrivial things such 
> as skipping certain bytes.)
>
> If not, then are there perhaps special cases in which it will be 
> guaranteed? For example, say my two graphs really use the same number 
> of vertices (i.e. have no dead vertices of degree 0) and same number 
> of edges. Will it work in this special case?
>
> Thank you very much in advance!
>
> Johann
>