MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

closed as off topic by Igor Rivin, George Lowther, Tom Leinster, Andy Putman, Suvrit May 30 '12 at 4:56

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

are you sure this is an ok question for MO? i thought such software related questions were not really entertained here...? – Suvrit May 29 '12 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 '12 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 '12 at 12:40
up vote 5 down vote accepted

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

share|cite|improve this answer
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 '12 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 '12 at 0:18
That's good then. Thanks Brendan. – Douglas S. Stones May 30 '12 at 0:42

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