sparse data structures. This gave it a very large advantage for many graphs of practical
interest, prompting the first author to release a version of nauty for sparse graphs. Saucy
has since introduced some important innovations, such as the ability to detect some types
of automorphism (such as those implied by a locally tree-like structure) very early (Darga
et al., 2008). Soon afterwards Juntilla and Kaski (2007, 2011) introduced Bliss, which
also used the same algorithm but had some extra ideas that helped its performance on
difficult graphs. In particular, it allowed refinement operations to be aborted early in
some cases. The latter idea reached its full expression in Traces, which we introduce in
this paper. More importantly, Traces pioneered a major revision of the way the search
tree is scanned, which we will demonstrate to produce great efficiency gains.
Another program worthy of consideration is conauto (L´opez-Presa and Fern´andez
Anta, 2009; L´opez-Presa et al., 2011). It does not feature canonically labelling, though
it can compare two graphs for isomorphism.
In Section 2, we provide a description of algorithms based on the individualization-
refinement paradigm. It is sufficiently general to encompass the primary structure of all
of the most successful algorithms. In Section 3, we flesh out the details of how nauty and
Traces are implemented, with emphasis on how they differ from differ. In Section 4, we
compare the performance of nauty and Traces with Bliss, saucy and conauto when
applied to a variety of families of graphs ranging from those traditionally easy to the
most difficult known. Although none of the programs is the fastest in all cases, we will
see that nauty is generally the fastest for small graphs and some easier families, while
Traces is better, sometimes in dramatic fashion, for most of the difficult graph families.
2. Generic Algorithm
In this section, we give formal definitions of colourings (partitions), invariants, and
group actions. We then define the search tree which is at the heart of most recent graph
isomorphism algorithms and explain how it enables computation of automorphism groups
and canonical forms. This section is intended to be a self-contained introduction to the
overall strategy and does not contain new features.
Let G = G
n
denote the set of graphs with vertex set V = {1, 2, . . . , n}.
2.1. Colourings
A colouring of V (or of G ∈ G) is a surjective function π from V onto {1, 2, . . . , k} for
some k. The number of colours, i.e. k, is denoted by |π|. A cell of π is the set of vertices
with some given colour; that is, π
−1
(j) for some j with 1 ≤ j ≤ |π|. A discrete colouring
is a colouring in which each cell is a singleton, in which case |π| = n. Note that a discrete
colouring is a permutation of V .
If π, π
0
are colourings, then π
0
is finer than or equal to π, written π
0
π, if π(v) <
π(w) ⇒ π
0
(v) < π
0
(w) for all v, w ∈ V . (This implies that each cell of π
0
is a subset of a
cell of π, but the converse is not true.)
Since a colouring partitions V into cells, it is frequently called a partition. However,
note that the colours come in a particular order and this matters when defining concepts
like “finer”.
A pair (G, π), where π is a colouring of G, is called a coloured graph.
3
评论0