1

Let $G$ be a graph. I've heard that, if we use nauty to canonically label $G$ on two different platforms, it's possible to obtain distinct labels. However, I've never actually seen this occur.

The nauty user guide (pdf) writes:

Beginning at version 2.1, the canonical labelling does not depend on the compiler, the system, or the word size.

This seems to imply that it's still possible to receive distinct canonical labels on different platforms. (This might also be somewhat out of context, since this sentence is written in the "dreadnaut" section.)

Question: What is an example of a situation where, on two different platforms, nauty would canonically label the same graph differently (if there are any)?

If it can still occur, is it a rare occurrence?

flag
are you sure this is an ok question for MO? i thought such software related questions were not really entertained here...? – S. Sra May 29 at 3:29
Some obscure CPU/compiler/OS bug certainly will lead to different result. CPU bugs are not uncommon, check the errata. – joro May 29 at 5:16
This is not apprpropriate, as @Suvrit notes. I am sure @Brendan would be happy to enlighten you over email. – Igor Rivin May 29 at 12:40

closed as off topic by Igor Rivin, George Lowther, Tom Leinster, Andy Putman, S. Sra May 30 at 4:56

1 Answer

5

It's only possible if there's a bug, and since there are no bugs it doesn't happen.

link|flag
Is this comment tongue-in-cheek, or has the implementation somehow been verified using formal methods? (Or do you just mean, if such an example was known it would have been fixed?) – Andrew D. King May 29 at 15:57
It's tongue in cheek. No counterexample is known, though. The runtime behaviour of C is specified by the standard to be platform-independent except for a few features that nauty doesn't rely on anyway. So an actual bug in nauty, the compiler, the run-time system, or the hardware is the only possibility. – Brendan McKay May 30 at 0:18
That's good then. Thanks Brendan. – Douglas S. Stones May 30 at 0:42

Not the answer you're looking for? Browse other questions tagged or ask your own question.