Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

The graph canonical labelling package nauty is widely regarded as one of the best (if not the best) around. Unfortunately, it's quite a large package, and making a GPU version seems to be a highly nontrivial task.

In my research into algorithms for network motif detection, we often require an effective solution to the problem of, what I like to call, "canonically labelling a billion smalls graphs". This should be a highly parallelisible problem, and therefore be suitable for the GPU architecture (although, there are issues of data transfer, memory usage, SIMD, etc., which I'm sweeping under the carpet).

This leads to the questions:

What other algorithms/packages are around that can perform graph canonical labelling?

For my purposes, it should ideally be lightweight and parallelisible, although, academic curiosity makes me interested in any alternatives. Note that these alternatives do not necessarily need to be faster than nauty.

Nauty has been well-established since well before I started in mathematics, so I'm not at all familiar with what people did before nauty came along.

share|cite|improve this question
I dig the title. :) – J. M. Aug 22 '11 at 7:23
I also dig the title, but do we really need a specialized tag for this package? – Asaf Karagila Aug 22 '11 at 7:40
Might get more answers at – Nick Alger Aug 4 '12 at 17:47
By the way, if anyone's interested in how we solved this problem -- we generated all the canonical labels by brute force, and stored them in memory. After which, it was like having a canonical labelling Oracle. – Douglas S. Stones Aug 4 '12 at 23:16
up vote 5 down vote accepted

There are a number of alternatives:

  • Bliss - similar to nauty
  • ConAuto - better search tree pruning
  • GI-Ext - already parallelized
  • Nishe - avoids some pathological slowness in nauty
  • Saucy - specializes in sparse output
  • Traces - small addition to nauty to help with pathologies
share|cite|improve this answer
Thanks for that, it was a while ago when I asked this question and I since found several of those. But was unaware of GI-Ext and Nishe (which has an parallel MPI version). – Douglas S. Stones Aug 4 '12 at 23:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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