Is there a canonical labelling package optimised for small graphs?

Question

Recently, I've been looking into motifs in networks (directed graphs) -- small connected induced subgraphs that appear significantly more frequently than in a "similar random graph".

In practice, we need to enumerate the induced subgraphs (up to isomorphism) in thousands of large random networks, which can take a long time, and requires some form of canonical labelling (e.g. FANMOD uses nauty). My feeling is that nauty is quite bulky and seems likely to be overkill for this feature because e.g. we only need to canonically label small graphs (in FANMOD they have at most 8 vertices -- although I haven't seen much interest in motifs with more than 4 vertices).

Question: Is there a package that specialises in the canonical labelling of small directed graphs?

In the case I'm interested in, we need to label millions of graphs on a small number of vertices.

Answer 1

Nauty really is optimized for small graphs, if you use the C library interface. McKay (and others, such as myself) frequently use this library to generate all graphs of a given small order, which requires canonical labeling of small graphs very quickly. This happens many many many times (see http://oeis.org/A000088 for the growth of the number of unlabeled graphs). In fact, McKay's program geng can compute all 12,005,168 graphs on 10 nodes in less than an hour on my laptop.