11
$\begingroup$

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.

  • 0
    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.2012-08-04

1 Answers 1

6

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
  • 0
    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).2012-08-04