[Nauty] Canonically labeled output of nauty/Traces actually byte-wise unique?
Johann Birnick
johann.birnick at hotmail.de
Tue Feb 20 10:08:02 AEDT 2024
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
>
More information about the Nauty
mailing list