2
$\begingroup$

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?

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

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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?) $\endgroup$
    – Andrew D. King
    May 29, 2012 at 15:57
  • $\begingroup$ 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. $\endgroup$
    – Brendan McKay
    May 30, 2012 at 0:18

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