A Generic Framework for Engineering
Graph Canonization Algorithms
Jakob L. Andersen (B)1-4 and Daniel Merkle1

arXiv:1711.08289v1 [cs.DS] 22 Nov 2017

1

Department of Mathematics and Computer Science, University of Southern Denmark,
Odense M DK-5230, Denmark daniel@imada.sdu.dk
2
Research group Bioinformatics and Computational Biology, Faculty of Computer Science,
University of Vienna, 1090 Vienna, Austria jakob.lykke.andersen@univie.ac.at
3
Institute for Theoretical Chemistry, University of Vienna, 1090 Wien, Austria
4
Earth-Life Science Institute, Tokyo Institute of Technology, Tokyo 152-8550, Japan

Abstract

comparing such canonical representations, which especially is useful when we want to test isomorphism
against a large collection of graphs, e.g., for database
querying. There is a rich literature on the complexity
of both graph canonization and graph isomorphism.
For longer discussion we refer to [15], and simply note
that for general graphs the problems are not known to
be NP-complete,
√ and the best bound for canonization
O( n log n)
[4, 6], while a quasi-polynomial
is currently e
bound for isomorphism was recently presented [5].
For practical graph canonization there has also been
extensive work, with several competitive tools being
published in the last decades. They are all build on
the same core idea of a tree search over gradually
more refined partitions of the vertex set, also called
the individualization-refinement paradigm. Their difference is thus essentially in the heuristics for traversing and pruning the search tree, and how partitions are
being refined. One of the most successful tools is nauty
[14], which not only finds a canonical representation
but also computes the automorphism group, which
during the canonization is used for pruning the search
tree. Later tools, Bliss [9, 10] and Traces [15], also use
this technique with the latter introducing a new way to
exploit the discovered automorphisms. A related tool
is Saucy [7, 11] which only performs computation of
the automorphism group, for which it introduced new
heuristics to discover them. Similarly there is Conauto
[13] which performs isomorphism testing directly without computing a canonical form. Each new tool and
updated versions of tools has incorporated ideas from
the other tools, with further development of heuristics.
However, the performance comparisons have been done
between the tools in their entirety, making it exceedingly difficult to discover exactly which combination of
ideas lead to better or worse performance on particular
classes of graphs. As the tools are almost completely

The state-of-the-art tools for practical graph canonization are all based on the individualization-refinement
paradigm, and their difference is primarily in the
choice of heuristics they include and in the actual tool
implementation. It is thus not possible to make a direct comparison of how individual algorithmic ideas
affect the performance on different graph classes.
We present an algorithmic software framework that
facilitates implementation of heuristics as independent
extensions to a common core algorithm. It therefore becomes easy to perform a detailed comparison of
the performance and behaviour of different algorithmic ideas. Implementations are provided of a range of
algorithms for tree traversal, target cell selection, and
node invariant, including choices from the literature
and new variations. The framework readily supports
extraction and visualization of detailed data from separate algorithm executions for subsequent analysis and
development of new heuristics.
Using collections of different graph classes we investigate the effect of varying the selections of heuristics,
often revealing exactly which individual algorithmic
choice is responsible for particularly good or bad performance. On several benchmark collections, including
a newly proposed class of difficult instances, we additionally find that our implementation performs better
than the current state-of-the-art tools.

1

Introduction

Graph canonization is the process of finding a canonical representation of a graph, such that all isomorphic graphs are assigned the same representation. The
graph isomorphism problem can thus be reduced to
1

independent implementations it is additionally hard to
make a fair comparison, even if individual innovations
could be isolated.
To address these problems we have developed a
generic framework for constructing variations of graph
canonization algorithms, where new ideas can be implemented as separate plugins, and injected into a common core algorithm. Not only does this framework
solve the problem of fairly comparing heuristics, but
it also significantly lowers the barrier of entry for people to test new ideas in practice. We provide implementations of a core set of heuristics, including new
variations of node invariants and a memory sensitive
tree traversal algorithm. Contrary to the established
tools the framework allows for direct canonization of
graphs with edge attributes, and we have developed
a generalization of the widely used Weisfeiler-Leman
refinement function which can exploit such attributes.
Using established benchmark graphs we discover interesting performance differences among combinations
of heuristics, including combinations with significantly
different scaling behavior and better performance than
the established tools. For a recently proposed collection of six difficult graphs classes [18, 19] we perform
a detailed benchmark of the effects of node invariants
which suggests why some of them are more difficult
than the others. Plots for all benchmarks can be found
in the GitHub repository [1].
The framework is implemented as a C++ library,
called GraphCanon, with heavy use of generic programming [17] with influences from and compatibility
with the Boost Graph library [12, 22]. It is available on
GitHub [1] along with the accompanying PermGroup
library [2] for handling permutation groups. In App. C
we provide additional details of the framework, including pseudocode with direct links to the corresponding
C++ code. The appendix also contains additional visualizations of search trees and data from experiments.
In Sec. 2 and 3 we lay out the mathematical description of the individualization framework, setting
the stage for the description of the framework in Sec. 4.
The experimental results are presented in Sec. 5, and
a summary with future developments is in Sec. 6.

and ΩE are totally ordered sets. We denote the set
of all attributed graphs on n vertices as Gn or simply as G. For the remainder of this contribution we
assume an attributed graph G = (V, E, lV , lE ) with
n vertices is given. Note that in related works, e.g.,
[9] and [15], they use so-called colored graphs that are
equivalent to graphs only with vertex attributes, and
they do not consider edge attributes directly. We assume the set of graphs G is totally ordered. For example, if the graphs are represented as adjacency matrices
we can lexicographically compare the matrices.1 For
graphs with vertex and/or edge attributes this comparison must also account for those attributes. For
two graphs G1 , G2 ∈ G with the same underlying representation we say they are representationally equal,
r
written G1 = G2 . When they are not we may say that
r
one is representationally smaller, written G1 < G2 .
A canonization algorithm starts with the assumption
that all vertices are unordered, and then incrementally
introduces order. To represent these intermediary partial orders we use the following construct. An ordered
partition of V is a sequence π = (W1 , W2 , . . . , Wr ) of
non-empty sets of vertices that partitions V . Each of
the constituent vertex sets is called a cell of π. For a
vertex v in the j-th cell, we define cell(v, π) = j. A
cell of size 1 is called a singleton, and if all cells are
singletons we call the partition discrete. If the ordered
partition only has one cell, i.e., π = (V ), it is called
the unit partition.
The set of all ordered partitions over V is denoted
Π. An ordered partition π 0 is at least as fine as π,
written π 0  π, when cell(u, π) < cell(v, π) implies
cell(u, π 0 ) < cell(v, π 0 ) for all u, v ∈ V . That is, π 0 can
be obtained from π by only subdividing cells.
Ordered partitions are used to represent intermediary states of the canonization procedure, in the sense
that for a partition π the vertices of a cell Wi are said to
be ordered before vertices of a cell Wj when i < j. The
unit partition thus represents no ordering information,
while each discrete ordered partition is a canonical order candidate.
Let Sn denote the symmetric group on the set of vertices V . For a permutation γ ∈ Sn we denote the image
of an element v ∈ V as v γ . Composition of permutations is thus written from left to right, i.e., v γ1 γ2 =
2 Preliminary Definitions
(v γ1 )γ2 . The inverse of a permutation γ is denoted γ.
The permutation of a subset of vertices W ⊆ V with
We denote an undirected graph as G = (V, E), with V γ ∈ S is defined as W γ = {wγ | w ∈ W }, while the
n
as the vertices and E as the edges. The goal is to find permutation of a sequence Q = (q , q , . . . , q ) ∈ V k
1 2
k
a canonical representation of G, and we therefore as- is Qγ = (q γ , q γ , . . . , q γ ). Similarly we extend permu1 2
k
sume the vertices already to have associated IDs. For tation to combinations of these structures, all derived
ease of notation we assume V = {1, 2, . . . , n}. An at- from V , which in particular means we can permute
tributed graph is a tuple G = (V, E, lV , lE ) of a graph
1 An illustrated example of comparison using adjacency lists
(V, E) and two attribution functions lV : V → ΩV and
lE : E → ΩE . We assume that the attribute sets ΩV can be found in App. A.
2

ordered partitions and (representations of) graphs.
We interpret a discrete ordered partition π as a permutation in Sn , that maps each cell index to its contained vertex. That is, if cell(v, π) = j then j π = v.
The inverse permutation π thus maps vertices to their
cell indices. Note that if we use a discrete ordered
partition π to represent a candidate for the canonical order, we then have π as a permutation from the
candidate canonical indices to the indices in the input
graph. Permuting the input graph with the inverse
permutation Gπ thus gives us the actual candidate for
the canonical representation.
Two graphs G1 , G2 ∈ G are isomorphic, denoted
G1 ∼
= G2 if there exists a permutation γ ∈ Sn such
r
that Gγ1 = G2 . The permutation γ is then called an
isomorphism, and if G1 and G2 refer to the same object, it is further called an automorphism. The set of
all automorphisms of a graph G, the automorphism
group, is denoted Aut(G).
A canonization algorithm can be seen as a function
on graphs, C : G → G, with the following properties,
r
[15, C1 and C2]: C(G) ∼
= G and C(Gγ ) = C(G), for all
γ ∈ Sn . That is, it returns a graph isomorphic to its
input, and it is invariant with respect to permutations
of its input. The second property is also called isomorphism invariance, and we will require this property for
most of the procedures we describe in the following
sections.

3

The algorithm is defined using several abstract functions. The first one is a refinement function R : G ×
Π → Π, with the properties [15]: R(G, π)  π and
R(Gγ , π γ ) = R(G, π) for all γ ∈ Sn . That is, it produces a partition that is finer or equal to its input, and
it is isomorphism invariant. When the refinement function produces non-discrete partitions we must decide
on a cell where we will artificially introduce cell splits.
For this we need a target cell selector T : G × Π → 2V
that for a non-discrete partition returns one of the
non-singleton cells. This function must also be isomorphism invariant, i.e., T (Gγ , π γ ) = T (G, π)γ , for all
γ ∈ Sn . The introduction of artificial splits is done
by vertex individualization. For an ordered partition
π with a non-singleton cell W and a vertex v ∈ W ,
we define π ↓ v as the ordered partition where W is
replaced by two cells {v} and W \{v}, in that order.
That is π ↓ v is the partition strictly finer than π obtained by individualizing v to the left from the rest of
its cell.
Canonization as a Tree Search A search tree can
now be formally defined as follows. Each node τ of
the tree is identified by a sequence of vertices, and it
implicitly defines an associated ordered partition πτ
defined in the following manner. Let π0 be the initial
ordered partition constructed from vertex attributes
as described above. The root of the search tree is
then the empty sequence τroot = (), with the associated ordered partition πτroot = R(G, π0 ). For a node
τ = (v1 , v2 , . . . , vk ), if πτ is discrete then τ is a leaf.
Otherwise, let W = T (G, πτ ) be the target cell selected
by T . For each vertex w ∈ W there is a child node
τchild = (v1 , v2 , . . . , vk , w), with the associated ordered
partition πτchild = R(G, πτ ↓ w). That is, for each
child we individualize a different vertex of the target
cell, and then perform refinement on the partition.2
We now define the canonical form of the abstract
algorithm. Note though that we will slightly alter this
definition later in order to facilitate pruning of the
search tree. Recall that the associated ordered partition of each leaf τ is a discrete partition πτ , which
represents a candidate canonical ordering of the vertices. Specifically, the permutation πτ maps the input
vertices to their new index, and the graph Gπτ is thus a
candidate for the canonical form. Let L(G) denote all
leaf nodes of the search tree starting from the graph G.
The canonical form C(G) is then the permuted graph
indicated by the leaf node with the representationally
πτcanon
smallest permuted graph. That
 π is C(G) = G
τ
with τcanon = arg minτ ∈L(G) G
.

The Abstract Algorithm

For a high-level description of the individualizationrefinement approach with proofs of correctness we refer
to [15]. The following description follows the same
principles, but we opt for a description that more easily
maps to the generic implementation presented in the
next section.
The individualization-refinement approach is a tree
search starting from the unit partition in the root
with each leaf of the search tree corresponding to a
discrete ordered partition. The canonical form then
corresponds to a “minimum” leaf, where “minimum”
is defined in conjunction by the graph representation
r
comparator <, and by so-called node invariants that
will be discussed in the end of this section. Instead
of comparing the vertex attributes in the leaves usr
ing < we can instead exploit them from the beginning
by starting with a specific ordered partition instead
of the unit partition. The initial partition is then
π0 = (V1 , V2 , . . . , Vk ) with the property that for all
u ∈ Vi and v ∈ Vj , if lV (u) = lV (v) then i = j, otherwise lV (u) < lV (v) implies i < j. That is, the vertices
2 An example of search tree with ordered partitions can be
are partitioned by their attribute, and the cells are ordered by the attribute.
found in App. B.
3

4

Pruning with Automorphisms Let τa , τb ∈ L(G)
be distinct leaves of the search tree, for which the permuted graphs are representationally equal. That is,
r
with α = πτa and β = πτb then Gα = Gβ . Permuting
r
both sides with β gives Gαβ = Gββ = G, meaning that
αβ is an automorphism of G. During the tree traversal, when finding new leaves that give representations
equal to our currently best leaf, we can derive an automorphism. We call this an explicit automorphism, and
the complete automorphism group can be computed by
considering all such pairs of leaf nodes [15]. Sometimes
it is possible to deduce automorphisms from internal
nodes of the search tree. We call automorphisms found
in this manner implicit automorphisms [14].
During the canonization procedure, let τ =
(v1 , v2 , . . . , vk ) be an internal node of the search tree
and u, v ∈ T (G, πτ ) two vertices in the target cell for
this node. Further, let γ ∈ Aut(G) be some known
automorphism that fixes all vertices individualized on
the path from the root to τ but moves u to v. That
is, viγ = vi for 1 ≤ i ≤ k, and uγ = v. As u and
v are equivalent under γ the two subtrees rooted at
(v1 , v2 , . . . , vk , u) and (v1 , v2 , . . . , vk , v) will be isomorphic, and we can safely skip traversal of one of them
[15, Operation PC ].

A Generic Algorithm Framework

From the abstract canonization algorithm we see that
each concrete algorithm is defined by specific choices
of sub-procedures for the six categories in the table
below.
Extension Category

Abstract Function

Tree traversal
—
Target cell selection
T : G × Π → 2V
Refinement
R: G × Π → Π
Pruning with automorphisms
—
Detection of implicit automorphisms
—
Node invariants
φ: G × T → Ω

Section
4.1
4.2
4.3
4.4
4.5
4.6

The goal of the present framework is to provide an
implementation of functionality common to all algorithms, and provide a facility for attaching extensions
for the six categories. Note that while only one option
for target cell selection and tree traversal must be chosen, it can be beneficial to use multiple algorithms in
conjunction for the remaining categories.
Using generic programming [17] we have designed a
single common extension infrastructure, based on the
idea of a visitor, similar to those used in the Boost
Graph library [12, 22]. The core canonization procedure is given a visitor object vis which must fulfill a
collection of requirements, i.e., it must model a specific Visitor concept. The concept specifies that a concrete visitor must implement a collection of callbacks
that will be invoked at various points during algorithm.
Each visitor must additionally specify two data structures; one that will be instantiated per search tree, and
one instantiated for each node in each search tree.3
We provide a compound visitor, which for a sequence
of individual visitors aggregates the associated data
structures and dispatches method calls to all of the
contained visitors. The compound visitor enforces that
exactly one visitor has implemented a tree traversal
algorithm, and exactly one has a target cell selector.
For the following sections we assume the object vis
is such a compound visitor aggregating the sequence
(vis1 , vis2 , . . . , vist ) of visitors.
The common functionality of the framework further
consists of data structures for tree nodes and ordered
partitions, along with methods for creation and destruction of tree nodes, including vertex individualization and invocation of target cell selection and refinement through the visitors.4
In the following sections we provide further details
for each of the six extension categories. Outside those
categories we provide two additional visitors; a debug

Pruning with Node Invariants During the construction of a tree node it is often possible to extract
isomorphism invariant information. The path from the
root to a leaf thus has a sequence of such extracted information, which again is isomorphism invariant. We
then redefine the canonical form to be the one with
the lexicographically smallest of such information sequences.
Formally, let T denote the set of all search tree
nodes, and Ω an arbitrary totally ordered set. An invariant function φ : G × T → Ω then assigns a value to
each tree node. The function must be isomorphism invariant, i.e., φ(Gγ , τ γ ) = φ(G, τ ). For convenience we
~ : G × T → Ω∗ . For
define the path invariant function φ
~
a tree node τ = (v1 , v2 , . . . , vk ) the value is φ(G,
τ) =
(φ(G, v1 ), φ(G, v2 ), . . . , φ(G, vk )). That is, it is the sequence of all node invariants from the root down to τ .
We compare such sequences lexicographically. Finally
the canonical form is then redefined to be the one with
the smallest permuted graph among the leaves with
the smallest path invariant:
~ )
φ∗ = min φ(τ
τ ∈L(G)
o
n
~ ) = φ∗
τcanon = arg min Gπτ φ(τ

3 The

τ ∈L(G)

details of the Visitor concept can be found in App. C.1.
for the framework methods can be found in the
appendix, Fig. 5.
4 Pseudocode

C(G) = G

πτcanon

4

visitor for collecting detailed logs, and a stats visitor,
e.g., for counting the number of tree nodes created
and even for creating an annotated visualization of the
search tree.5

4.1

Tree Traversal and
Garbage Collection

the first either smallest or largest cell. A property used
in more advanced target cell selectors is the following
[9]: for two cells U, W ∈ π we say that U is nonuniformly joined to W if for all vertices u ∈ U there
are two vertices w1 , w2 ∈ W such that (u, v1 ) ∈ E
and (u, v2 ) 6∈ E. That is, all vertices of U have both
neighbours and non-neighbours in W .
In the present framework the target cell selection is
done during construction of each internal tree node,
using a dedicated visitor method. Exactly one visitor
must indicate that it implemented this method.
We provide three target cell selectors: select the first
non-singleton cell (F), select the first largest cell (FL),
and select the first largest cell that is non-uniformly
joined to the most cells (FLM).

Automatic

Most of the published algorithms and tools, including
nauty [14, 15] and Bliss [9, 10] use depth-first traversal
of the search tree. Bliss notably exploits this traversal
order to use a more efficient data structure for ordered
partitions. The tool Traces [15] uses a different traversal scheme which combines a breadth-first traversal
with so-called experimental paths to find leaves early.
As noted in [18], this means that Traces can consume
much more memory than tools using depth-first traversal.
The framework directly allows for arbitrary tree
traversal algorithms to be used, by defining appropriate visitors. The lifetime of tree nodes is managed
using reference counting, where each node has a owning reference to its parent and the parent has a nonowning reference to its children. Each visitor is thus
responsible to keep owning references to nodes they
are interested in. The creation of new children is done
through a framework method, while discovered leaf
nodes must be reported through another framework
method that handles comparison of permuted graphs
and potentially updating the current best leaf. To facilitate pruning, a specific visitor method should be invoked before deciding which child node to create next.
We provide an implementation of the classical
depth-first traversal (DFS)6 and a traversal similar to
Traces (BFSExp). We have also developed a memory sensitive hybrid of those two traversals (BFSExpM), which trades time for guaranteed memory usage. Based on a given memory limit it uses BFSExp
when the number of tree nodes is low, and uses DFS
when above the limit. It may therefore switch back
to BFSExp if a sufficient amount of the search tree
is deallocated. With the provided debug visitor it is
directly possible to investigate how the number of currently allocated tree nodes develops through the course
of the algorithm.7

4.2

4.3

The basic refinement function used in most tools is the
1-dimensional Weisfeiler-Leman algorithm (WL-1)[23],
that iteratively separates vertices in a cell depending
on their degree with respect to other cells. Traces [15]
can also use the 2-dimensional variant. The tool nauty
includes a selection of additional refinement functions
[15].
Refinement is invoked during the construction of
a tree node, through the refinement visitor method.
Multiple visitors may do refinement, so the formal refinement function R is derived from the composition
Rt ◦ · · · ◦ R2 ◦ R1 , where Ri is the refinement function
implemented by visitor visi . The compound visitor coordinates the invocation using returned status codes,
e.g., indicating whether any refinement was performed,
or if it was aborted due to node invariant pruning. To
support calculation of node invariants and discovery
of implicit automorphisms there are multiple visitor
methods that refinement algorithms, especially WL-1,
can call. The simplest being the method called for each
cell split performed.
We provide the WL-1 algorithm for refinement,
which based on the observations in [9], uses custom
implementations of counting sort and array partitioning to perform fast sorting for low degree cases. As
the framework directly allows for canonization of edge
attributes, we have also generalized the WL-1 implementation to exploit the attributes for even stronger
refinement.8

Target Cell Selection

A large variety of target cell selectors are available in
Bliss, Traces, and nauty, with the simplest selecting
5 Examples

Refinement

4.4

of search tree visualizations can be found in

Pruning With Automorphisms

Let A be the list of discovered automorphisms at
some stage in the algorithm. As automorphisms are

App. D.
6 Pseudocode for the implementation of DFS is shown in the
appendix, Alg. 6.
7 An example of investigating the number of tree nodes allocated can be found in App. E.

8 The details of the generalized WL-1 algorithm can be found
in App. C.3.

5

closed under composition, we can consider the subgroup Φ ≤ Aut(G) generated from A. For a tree
node τ = (v1 , v2 , . . . , vk ) we are then interested in
pruning with all permutations in the stabilizer of Φ
with respect to the individualized vertices in τ , i.e.,
StabΦ (τ ) = {γ ∈ Φ | viγ = vi , 1 ≤ i ≤ k}. This
is for example done in Traces and newer versions of
nauty [15], using random Schreier methods [21]. A
computational less intensive method is used in Bliss
and earlier versions of nauty, where only the subset
Aτ = {γ ∈ A | viγ = vi , 1 ≤ i ≤ k} is considered, i.e.,
a direct filtering of the found automorphisms without
composition. However, only a fixed number of permutations are stored at a time to conserve memory [9, 14].
The framework provides explicit automorphisms to
the visitors, and they may report implicit automorphisms to each other. The actual pruning can be done
in the visitor method that the tree traversal visitor is
expected to invoke before deciding which child to create next.
We have implemented a visitor for automorphism
pruning which itself is parameterized, such that it can
work with different implementations of permutations,
groups, and stabilizer chains. For each tree node the
visitor maintains the orbit partition of the target cell,
using a union-find data structure. In the present version we provide a parameterization that maintains Aτ
in each node, similar to the strategy in Bliss and earlier
versions of nauty but without a limit on the number
of stored automorphisms.9

4.5

degree 1 vertices and reporting the implicit automorphisms discovered in the process.

4.6

Pruning With Node Invariants

In the abstract algorithm we used a single node invariant function, though in practice we may want to use
multiple functions. For example, one source of invariant data is from the sequence of cell splits performed
by the refinement function, introduced in Traces [15].
Another important example is the partial leaf invariant introduced in Bliss [9], calculated when new singleton cells arise in the refinement procedure. Third, the
WL-1 algorithm in general computes many different
counts of edges, and this sequence of numbers can also
be used as an invariant. Importantly, both Bliss and
nauty use hashing during node invariant computation,
which may diminish the pruning power when collisions
occur.
In the framework the calculation of and pruning
with node invariants can be implemented entirely as
visitors. A visitor for coordinating multiple invariants is provided both for ensuring correct pruning,
but also to minimize the overhead of implementing
a new invariant. Let Ωi be the domain of invariant values produced by visi , then the node invariant
values for a given tree node is a sequence of pairs
(hi1 , ω1 i, hi2 , ω2 i, . . . , hik , ωk i) where ij is a visitor index and ωj ∈ Ωij . The first component of each pair
is stored in the coordinating visitor, while the second
component is stored in the corresponding visitor. The
coordinating visitor handles invalidation of the current
best leaf when a better path invariant is found, and
handles pruning of children of nodes that has already
been created, but where a better invariant was found
later.
We implement three invariants: the cell splitting
trace introduced in Traces (T), a trace of values for
the quotient graph also introduced in Traces [15] (Q),
and the partial leaf invariant introduced in Bliss (PL).
Note that we do not hash the information in any of
these visitors.

Detecting Implicit Automorphisms

There are several known methods for finding additional
automorphisms during the tree search. For example,
Lemma 2-25 [14] describes three cases where all refinements of certain ordered partitions lead to isomorphic
leaf nodes. The simplest, and most common, of those
cases is where the partition has singleton cells or cells
of size 2.10 Saucy [7, 11] introduced another heuristic for finding primarily sparse automorphisms, where
for each non-leaf node a guess for an automorphism
is made. Traces [15] reportedly generalizes this heuristic, though the details have not been described. Traces
also has heuristics for finding automorphisms when all
vertices in non-singleton cells have certain degrees, but
it is not clear what those heuristics are.
We have implemented two visitors in this category:
one for the most common case of Lemma 2-25 [14],
described above, and one for refining cells with only

5

Experimental Results

While the framework is capable of handling both
vertex and edge attributes there are unfortunately
no comprehensive collections with such graphs. We
have therefore benchmarked our implementation using both the collections of unattributed graphs from
[16], and using a proposed collection of difficult graphs,
9 Pseudocode for the generic automorphism pruner visitor can
cfi-rigid [18, 19]. All executions were repeated 5
be found in the appendix, Alg. 7.
10 Pseudocode for the simplest case of Lemma 2-25 [14] can be
times with random permutations of the input graph,
found in Alg. 8.
always with a maximum of 8 GB memory and a 1000
6

second time limit. Of the repetitions that succeeded
we plot the average time spend, as well as markers if
at least one execution ran out of memory (OOM) or
out of time (OOT). We have also recorded the number of tree nodes created, but as the elapsed time to
a large degree is proportional to the number of nodes
we only show time plots. The full set of plots can be
found at [1]. For comparison of absolute performance
we also benchmarked the default configurations of Bliss
v0.73 as well as v26r6 of nauty (dense and sparse) and
Traces. All experiments were run on compute nodes
with two Intel E5-2680v3 CPUs (24 cores), using in
total 12,000 compute node hours. In the first part we
investigate the effect of tree traversal algorithm and
target cell selector, while we focus in the second part
on the cfi-rigid collections where we also investigate
the effect of different subsets of node invariants. In the
third part we illustrate how the BFSExpM traversal
provides a memory-safe alternative to BFSExp at the
expense of time.

figurations is similar to Traces (which is also breadthfirst-based), while for the union of strongly regular
graphs (usr, Fig. 1c) the BFSExp-F and BFSExpFLM configurations perform distinctly better than all
other algorithms. Surprisingly the FL counterpart is
one of the worst performing algorithms on the same
collection.
The original collection of product graphs f-lex
contains two types of graphs where the algorithms
perform differently, so we have split it into the two
groups f-lex-reg and f-lex-srg, Fig. 1e and 1f. For
f-lex-reg we again see a separation by tree traversal algorithm, with the DFS configurations not being
able to solve any instances. However, Bliss also uses
DFS but still solves many of the instances. For the
f-lex-srg part of the collection only BFSExp-F of all
algorithms solve instances, though only for some executions.
The cfi-rigid Collections This package of six collections of graphs [19], was recently proposed [18] explicitly as difficult instances for graph isomorphism,
and by construction they have very little symmetry.
Each collection (see Tab. 1) is constructed using a
group, D3 , Z3 , or Z2 . For Z2 there are further 3
variations where the instances have gone through either a single or both of two reduction techniques (here
denoted as R∗ , B ∗ , and R∗ ◦ B ∗ ). We have benchmarked all combinations, including subsets of node invariants, on all instances. That is the 48 combinations
{BFSExp, DFS} × {F, FL, FLM} × 2{PL,Q,T} .
For the four Z2 -based collections Bliss and nauty
(sparse) perform well, though both FLM configurations with all invariants have similar performance on
s2 and t2. On the two other collections, d3 and z3,
the BFSExp-FLM configuration with all invariants is
the best performing algorithm, with the corresponding DFS-FLM configuration slightly behind. There is
however a significant separation up to F and FL configurations (Fig. 1b). We do not see this separation in
the plain Z2 -based collection (z2) or in those with just
one reduction applied, but interestingly the separation
occurs when both reductions are applied at the same
time, t2.
In the investigation of the effect of node invariants
we first of all found that the relative effect on performance is independent of tree traversal and target cell
selector, within the same graph collection. For d3, z3,
and z2, i.e., the collections without reductions, it improves performance when enabling any one invariant.
Though the effect of enabling additional invariants is
minor or non-existing. Intriguingly, for r2 where the
R∗ reduction were used to create the instances, the
node invariants do not seem to have any effect at all.
When the other reduction, B ∗ , has been applied (s2),

Tree Traversal and Target Cell Selector For all
graph collections from [16] we benchmarked the set
{BFSExp, DFS} × {F, FL, FLM} of algorithm configurations, with all node invariants enabled. Overall we
found that no single configuration is the best performing on all instances, though BFSExp-FLM is often performing well. In the following we focus on a selection of
graph collections where we find that different subsets
of algorithm configurations have significantly different
performance behaviors, and where some perform significantly better than the established tools.
On several of the (augmented) Miyazaki graphs we
see that the performance largely is determined by the
target cell selector. Fig. 1a shows the result for the
mz-aug2 collection, where the three pairs of F, FL,
and FLM configurations have widely different performance. From the number of tree nodes explored (see
[1]) we see that the FLM target cell selector scales
similar to Traces (sub-exponential), while F and FL
both have exponential behavior similar to Bliss and
the two nauty modes. This behavior we also see in
the cmz collection, while for mz-aug only the F configurations scale exponentially. In both mz-aug and
mz the BFSExp-FLM configuration, for n > 400, will
hit the memory limit for some executions but not all.
We attribute this to the automorphism pruning where
we do not perform composition via random Schreier
methods. Thus, if the BFSExp tree traversal finds explicit automorphisms with few fixed vertices it may
have fewer chances of using them for pruning.
On other collections, such as the non-disjoint union
of tripartite graphs (tnn, Fig. 1d), the algorithm configurations are separated by the tree traversal algorithms. For tnn the performance of the BFSExp con7

OOM
OOT

104
103

101
100

10−2

(b) cfi-rigid-d3

nauty (s)

Traces

Bliss

BFSExp-F

BFSExp-FL

BFSExp-FLM

DFS-F

DFS-FL

DFS-FLM

OOM
OOT

101
100

104
103
102

Time (s)

nauty (d)

10−2

10−2

DFS-F

DFS-FL

DFS-FLM

101
100

10−2

nauty (s)

Traces

Bliss

BFSExp-F

BFSExp-FL

BFSExp-FLM

DFS-F

DFS-FL

DFS-FLM

4,

3,

0

0
50

00

00

0
3,

00

5
2,

00

0
2,

00

5
1,

0
00
1,

00

0

50

8
1,

00

6
1,

00

4
1,

00

00

2
1,

0
1,

0

80

0

60

0
40

n

nauty (d)

00

BFSExp-FLM

00

BFSExp-FL

102

1
1,

BFSExp-F

0
1,

Bliss

103

10−2

(e) f-lex-reg

0

nauty (s)

Traces

10−1

nauty (d)

90

nauty (d)

104

10−1

n

0

100

0

101

OOM
OOT

80

DFS-FLM

(d) tnn

70

DFS-FL

0

DFS-F

0

BFSExp-FLM

60

102

50

BFSExp-FL

DFS-FLM

0

BFSExp-F

DFS-F

DFS-FL

40

103

BFSExp-FL

BFSExp-FLM

0
30
0

Bliss

Bliss

BFSExp-F

20

Traces

n

0
10

nauty (s)

0

0
00
1,
0
90
0
80
0
70
0
60
0
50

0
40
0

30

0

20

0

10

0

nauty (d)

nauty (s)

Traces

100
10−1

104

nauty (d)

101

10−1

(c) usr

0
50
4,
0
00
4,
0
50
3,
0
00
3,
0
50
2,
0
00
2,
0
50
1,
0
00
1,

102

0

103

n

50

104

0

0
30
1, 0
20
1, 0
10
1, 0
00
1,
0
90
0
80
0
70
0
60
0
50
0
40
0
30
0
20
0
10

0

Time (s)

100

10−2

n

Time (s)

101

10−1

(a) mz-aug2

OOM
OOT

103

10−1

n

OOM
OOT

104

102

Time (s)

102

Time (s)

Time (s)

OOM
OOT

(f) f-lex-srg

nauty (s)

Bliss
Figure 1: SelectedTraces
benchmark results
for all combinations {BFSExp, DFS} × {F, FL, FLM}, with all node
BFSExp-F
BFSExp-FL
invariants enabled.

Col.
d3
z3
z2
r2
s2
t2

BFSExp-FLM

DFS-F

DFS-FL

DFS-FLM

Group

Reduction

D3
Z3
Z2
Z2
Z2
Z2

—
—
—
R∗
B∗
R∗ ◦ B ∗

Best Algorithm

BFSExp-FLM
BFSExp-FLM
Bliss, nauty (s)
Bliss, nauty (s)
FLM, Bliss, nauty (s)
FLM, Bliss, nauty (s)

Invariants Matter

FLM Sep.

yes (any)
yes (any)
yes (any)
no
yes (PL or Q)
yes (PL or Q)

yes
yes
no
no
no
yes

Max. Solved n
3,600
3,780
2,992
1,584
2,496
1,056

Table 1: Summary of results for the cfi-rigid collections. The right-most column is the largest instance that
any of the configurations or the tools solved.
we find that the cell splitting invariant (T) has no effect, but either PL, Q, or both have the same improving effect. Surprisingly, we also see that pattern of

effect on t2 which has undergone both reductions. We
hope that future in-depth studies on these graphs and
node invariants may lead to new insights, both for de8

OOM
OOT

general enough to for example handle attributes used
for encoding stereo-chemistry in molecule graphs [3, 8].
In our preliminary investigations we find that it is possible to lift this restriction, and that a novel type of
node invariant can be introduced to exploit complex
attributes for pruning.

105
104

Time (s)

103
102
101
100

BFSExpM
BFSExp
DFS

10−1
10−2

Acknowledgements

0
50
4,
0
00
4,
0
50
3,
0
00
3,
0
50
2,
0
00
2,
0
50
1,
0
00
1,

0
50

0

n

This work was supported in part by the COSTFigure 2: Comparison of tree traversal algorithms on Action CM1304 “Systems Chemistry”, by the Indepencfi-rigid-d3, using FLM for target cell selection and dent Research Fund Denmark, Natural Sciences, grant
all three node invariants.
DFF-7014-00041, and by the ELSI Origins Network
(EON), which is supported by a grant from the John
Templeton Foundation. Computation for the work developing better invariants but potentially also for cre- scribed in this paper was supported by the DeiC Naating even more difficult benchmark graphs.
tional HPC Centre, SDU. The opinions expressed in
this publication are those of the authors and do not
Memory Sensitive BFSExp In some contexts it necessarily reflect the views of the John Templeton
is highly undesirable to run out of memory, and we Foundation.

have therefore developed the BFSExpM tree traversal
as described earlier. We have tested it using FLM as
target cell selector on cfi-rigid-d3 with a limit to ensure the whole process does not hit the 8 GB hard-cap.
Varying the memory limit (down to 1 GB) did not result in different performances. In Fig. 2 a comparison
is shown with the BFSExp and DFS configurations.
We clearly see that for the instance sizes where BFSExp go out of memory on some executions, the BFSExpM configuration increase in average time spend.
Notably it still performs better than DFS, thereby being a viable alternative when a memory limit must be
honored. For this experiment we let all executions run
for 10,000 seconds, and we see that BFSExpM is the
only configuration to solve the largest instance, though
with some executions exceeding the time limit.

6

References
[1] Jakob L. Andersen.
GraphCanon repository on GitHub, 2017. http://github.com/
jakobandersen/graph_canon.
[2] Jakob L. Andersen.
PermGroup repository on GitHub, 2017. http://github.com/
jakobandersen/perm_group.
[3] Jakob L. Andersen, Christoph Flamm, Daniel
Merkle, and Peter F. Stadler. Chemical graph
transformation with stereo-information. In Graph
Transformation - 10th International Conference,
ICGT 2017, Held as Part of STAF 2017, Marburg, Germany, July 18-19, 2017, Proceedings,
pages 54–69, 2017.

Concluding Remarks

[4] László Babai. Automorphism groups, isomorphism, reconstruction. In Handbook of combinatorics (vol. 2), pages 1447–1540. MIT Press, 1996.

We have presented a versatile framework for fast graph
canonization algorithms that makes it easy to implement and compare heuristics. Not only does it perform better than the established tools on several graph
classes, but we find interesting performance separations between different choices of heuristics which is
not immediately possible with the established tools. In
the future we will expand the set of available heuristics,
to approach a full algorithm library for graph canonization. While the established tools can handle graphs
with vertex attributes, the presented framework can
also directly handle edge attributes, and even exploit
them for refinement. Though, the attribute sets are
currently limited to totally ordered sets, which is not

[5] László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings
of the Forty-eighth Annual ACM Symposium on
Theory of Computing, STOC ’16, pages 684–697,
New York, NY, USA, 2016. ACM.
[6] László Babai and Eugene M. Luks. Canonical labeling of graphs. In Proceedings of the Fifteenth
Annual ACM Symposium on Theory of Computing, STOC ’83, pages 171–183, New York, NY,
USA, 1983. ACM.
9

[7] Paul T. Darga, Karem A. Sakallah, and Igor L.
ESA 2017, September 4-6, 2017, Vienna, Austria,
Markov. Faster symmetry discovery using sparsity
pages 60:1–60:14, 2017.
of symmetries. In Proceedings of the 45th Annual
Design Automation Conference, DAC ’08, pages [19] Daniel Neuen and Pascal Schweitzer. Benchmark
graphs for practical graph isomorphism, 2017.
149–154, New York, NY, USA, 2008. ACM.
https://www.lii.rwth-aachen.de/research/
[8] Stephen R. Heller, Alan McNaught, Igor Pletnev,
95-benchmarks.html.
Stephen Stein, and Dmitrii Tchekhovskoi. Inchi,
the iupac international chemical identifier. Jour- [20] Adolfo Piperno. Search space contraction in
canonical labeling of graphs (preliminary version).
nal of Cheminformatics, 7(1):23, May 2015.
CoRR, abs/0804.4881, 2008.
[9] Tommi Junttila and Petteri Kaski. Engineering
an efficient canonical labeling tool for large and [21] Á. Seress. Permutation Group Algorithms. Camsparse graphs. In 2007 Proceedings of the Ninth
bridge Tracts in Mathematics. Cambridge UniverWorkshop on Algorithm Engineering and Experisity Press, 2003.
ments (ALENEX), pages 135–149. SIAM, 2007.
[22] Jeremy G Siek, Lie-Quan Lee, and Andrew Lums[10] Tommi Junttila and Petteri Kaski. Conflict Propdaine. Boost Graph Library: The User Guide
agation and Component Recursion for Canonical
and Reference Manual. Pearson Education, 2001.
Labeling, pages 151–162. Springer Berlin Heidelhttp://www.boost.org/libs/graph/.
berg, Berlin, Heidelberg, 2011.
[23] Boris Weisfeiler. On construction and identifica[11] Hadi Katebi, Karem A Sakallah, and Igor L
tion of graphs, volume 558. Springer, 2006.
Markov. Symmetry and satisfiability: An update. In Theory and Applications of Satisfiability Testing–SAT 2010, pages 113–127. Springer,
2010.
A Comparison of Graph Repre[12] Lie-Quan Lee, Jeremy G. Siek, and Andrew Lumssentations
daine. The generic graph component library. SIGThe canonization algorithm relies on a total order to
PLAN Not., 34(10):399–414, October 1999.
exist on the set of all graph representations. For adja[13] José Luis López-Presa and Antonio Fernán- cency matrices we can find the order among two graphs
dez Anta. Fast Algorithm for Graph Isomorphism for example by lexicographic comparison of the matriTesting, pages 221–232. Springer Berlin Heidel- ces. When edge attributes are present we can imagberg, Berlin, Heidelberg, 2009.
ine them being stored in the matrix and then require
[14] Brendan D. McKay. Practical graph isomor- the attribute domain to be totally ordered. With verphism. In Congressus Numerantium, volume 30, tex attributes we can simply modify the comparison
pages 45–97. Utilitas Mathematica Pub. Incor- such that we first lexicographically compare vertex atporated, 1981. http://cs.anu.edu.au/~bdm/ tributes in order of the vertex index, and then the matrices.
papers/pgi.pdf.
For adjacency lists a similar comparison can be de[15] Brendan D. McKay and Adolfo Piperno. Prac- fined. Assuming the vertex indices are defined by the
tical graph isomorphism II. Journal of Symbolic position of the vertices in the data structure, we still
have freedom to order each of the lists of incident
Computation, 60:94–112, 2014.
edges. We can say that an adjacency list is globally
[16] Brendan D. McKay and Adolfo Piperno. ordered if each edge list is sorted by the neighboring
nauty and traces, 2017. http://pallini.di. vertex index, and with edge attributes and multigraphs
uniroma1.it/Graphs.html.
we further require parallel edges to be ordered by the
[17] David R Musser and Alexander A Stepanov. edge attribute. Two globally ordered adjacency lists
Generic programming. In International Sympo- can then be compared lexicographically in the natural
sium on Symbolic and Algebraic Computation, manner. Vertex attributes can be trivially incorporated in this procedure. An example of globally orpages 13–25. Springer, 1988.
dered adjacency lists are shown in Fig. 3, along with
[18] Daniel Neuen and Pascal Schweitzer. Bench- a visualization of how automorphisms can be detected
mark graphs for practical graph isomorphism. In by comparing graph representations from different per25th Annual European Symposium on Algorithms, mutations of the input indices.
10

1
4
3

2

2

π1 = (1 2 4)(3)

1
3

4

G1
1:
2:
3:
4:

4
3, 4
2, 4
1, 2, 3

1

π2 = (1 2 3 4)

4

G
1:
2:
3:
4:

2

3
G2

2, 3, 4
1
1, 4
1, 3

1:
2:
3:
4:

4
3, 4
2, 4
1, 2, 3

Figure 3: Three isomorphic graphs represented as adjacency lists. The underlying indices of the vertices are
shown, and the permutations π1 and π2 (in cycle notation) describe the relationship between the indices of
the graphs. From the adjacency lists we see that G1 is representationally equal to G2 , and representationally
different from G. The permutation π 0 = π1 π2 = (2 3)(1)(4) thus represents an isomorphism from G1 to G2 .

B

Search Tree Example

• τ , an arbitrary tree node
• γ, a non-trivial permutation in Sn

An example of a search tree is shown in Fig. 4.

• position, an integer indicating the start of a cell

C
C.1

Framework Details

Valid Expressions

Visitor Concept

The following is an outline of the Visitor concept, ommitting technical details and several methods, e.g., for
callbacks during refinement. The concept is not explicitly codified in the implementation, but the compound
visitor (BC++) in practice enforces it.
A type Vis satisfies the Visitor concept if the following requirements are fulfilled.

• vis.traverseTree(τroot ), if CanSelectTargetCell is
convertible to TrueType
Must implement a tree traversal algorithm.
Called from canon, Alg. 1, line 5.
• vis.selectTargetCell(τ ), if CanSelectTargetCell
is convertible to TrueType
Must implement a target cell selector, T . Called
from makeTreeNode, Alg. 3, line 9.
• vis.isomorphicLeaf(τ )
Called from addLeaf, Alg. 2, line 12.

Associated Types
Vis must have the following nested types:
• TreeData: the type of a data structure to be instantiated for each search tree.
• NodeData: the type of a data structure to be instantiated for each search tree node.

• vis.implicitAutomorphism(γ)
May be called at any time by visitors.
• vis.treeNodeCreateBegin(τ )
Called from makeTreeNode, Alg. 3, line 5.
• vis.treeNodeCreateEnd(τ )
Called from makeTreeNode, Alg. 3, line 13.

• CanSelectTargetCell: a type convertible to TrueType or FalseType indicating whether the visitor
implements target cell selection.
• CanTraverseTree: a type convertible to TrueType
or FalseType indicating whether the visitor implements tree traversal.

• vis.treeNodeDestroy(τ )
Called
destroyTreeNode, Alg. 3, line 19.

from

• vis, an object of type Vis

• vis.refine(τ )
Must implement a refinement function R, but inplace. Must call refineAbort on the overall visitor object if it returns due to the tree node becomming pruned. Called from makeTreeNode, Alg. 3,
line 7.

• τroot , a tree node representing the root of a search
tree

• vis.refineAbort(τ )
Called by refinement functions.

Syntax

11

5

9

5

9
2

2

7

2

7

4

7

4

4

6

8
1

6

8
1

3

1

3

10

π(1) = [1 | 2 | 7 8 9 10 | 5 6 | 3 4]

6

8

3

10

10

π() = [1 2 | 7 8 9 10 | 3 4 5 6]

π(2) = [2 | 1 | 7 8 9 10 | 3 4 | 5 6]

5

9

5

9

5

9
2

2

7
4

4

6

8
1

7

2

1

7

10

8

9

10

7

8

π(1,7) = [1 | 2 | 7 | 10 | 8 | 9 | 6 | 5 | 4 | 3]

5

9

2
7
4
6

8
1

6

8
1

3

3
10

π(1,8) = [1 | 2 | 8 | 9 | 7 | 10 | 5 | 6 | 3 | 4]

9

3

10

10
π(2,7) = [2 | 1 | 7 | 10 | 8 | 9 | 4 | 3 | 6 | 5]

1
2
3
4
5
6
7
8
9
10

5

9

2
7
4
6

8
1

3
10

Colour order

π(1,9) = [1 | 2 | 9 | 8 | 10 | 7 | 6 | 5 | 3 | 4]

Figure 4: A search tree starting with the refinement of the unit partition in the root. The refinement function
used is the WL-1 algorithm, the target cell selector is selecting the first non-singleton cell, and no node invariants
are used. Each node in the tree represents a sequence of vertex individualizations, where the latest vertex being
individualized is shown in the nodes. For most tree nodes the corresponding partition is shown along with the
colored graph it represents. In the colored graphs the vertices are labeled with the vertex indices from the
input graph, and colored with “numbers” corresponding to the potential canonical vertex indices. Note that
the colored graphs in the leaves of the left half of the tree (the children of τ = (1)) are all isomorphic. This
is also true among the children in the right half of the tree (the children of τ = (2). However between the
halves of the tree, the graphs are not isomorphic. The grayed out nodes correspond to nodes pruned from
automorphism discovery, when depth-first traversal of the tree is used. The example is heavily inspired by [20,
Figure 3], though here using different functions for refinement and target cell selection.
• vis.beforeDescend(τ )
Should be called by tree traversal algorithms before deciding which child to create next.

C.2

The pseudocode is shown in Fig. 5.

C.3
• vis.newCell(τ , position)
Must be called by refinement functions for each
new cell split.

Pseudocode for Framework Methods

Weifeler-Leman Refinement and
Edge Attributes

The WL-1 algorithm refines a cell by distinguishing
the vertices by their degree to other cells. That is,
for a cells to be refined X ⊆ V and a cell to refine
12

Algorithm 1: Canonization Function
1

2
3
4
5
6

7

Algorithm 3: Tree Node

def canon(G, vis, vComp, eHandler):
BC++
// We implicitly assume that references to
// the following variables are passed
// recursively to all functions:
// G, vis, eHandler, and canonLeaf.
canonLeaf ← nil
π0 ← The ordered partition (V1 , V2 , . . . , Vk ) as described in
Sec. 3, but using vComp for vertex comparison. BC++
τroot ← makeTreeNode(nil, π0 )
vis.traverseTree(τroot )
πcanon ← canonLeaf.π
// Return just the permutation. It is then
// up to the user to permute the graph.
return πcanon

1
2
3
4
5
6
7
8
9

10
11
12
13
14

Algorithm 2: Tree Traversal Support
1
2
3
4
5
6

def addLeaf(τleaf ):
if canonLeaf = nil then
canonLeaf = τleaf
return
πcanon ← canonLeaf.π
πleaf ← τleaf .π

7

Gcanon ← Gπcanon

8

Gleaf ← Gπleaf

15
16
17

BC++

18

19
20
21
22
23

r
9
10

if Gleaf < Gcanon then
canonLeaf ← τcanon

13
14
15
16
17
18
19
20
21

else if Gleaf = Gcanon then
vis.isomorphicLeaf(τleaf )
def makeChildNode(τparent , w):
πchild ← τparent .π ↓ w
τchild ← makeTreeNode(τparent , πchild )
if τchild = nil then
τparent .childPruned[w] ← true
else
τchild .individualizedVertex ← w
τparent .child[w] ← nonOwningRef(τchild )
return τchild

BC++

def destroyTreeNode(τ ):
// Automatically called when
// the reference count for τ goes to 0.
vis.treeNodeDestroy(τ )
if τ .parent 6= nil then
w ← τ .individualizedVertex
τ .parent.child[w] ← nil
τ .parent.childPruned[w] ← true

BC++

Algorithm 4: Tree Pruning Support

r

11
12

def makeTreeNode(τparent , π):
τ .parent ← τparent
τ .π ← π
τ .isPruned ← false
vis.treeNodeCreateBegin(τ )
if not τ .isPruned then
vis.refine(τ )
if not τ .isPruned and not τ .π discrete then
τ .targetCell ← vis.selectTargetCell(τ )
// Initialize children references
// and pruning status.
foreach w ∈ τ .targetCell do
τ .child[w] ← nil
τ .childPruned[w] ← false
vis.treeNodeCreateEnd(τ )
if τ .isPruned then
return nil
else
return τ

1

BC++

2
3
4
5
6
7
8
9
10

def pruneTree(τ ):
if τ .π is discrete then
if τ = canonLeaf then
canonLeaf ← nil
return
foreach w ∈ τ .targetCell do
τ .childPruned[w] ← true
τchild ← τ .child[w]
if τchild 6= nil then
pruneTree(τchild )

BC++

Figure 5: The core of the canonization algorithm framework. Alg. 1: the entry point for canonization, called
with the input graph, a compound visitor, and objects for incorporating vertex and edge attributes. Alg. 2: the
supporting methods for tree traversal algorithms, with makeChildNode for making new child nodes specified
by the vertex to individualize, and the method addLeaf for initiating leaf comparison. Alg. 3: the constructor
and destructor methods for tree nodes. Note that the destructor is automatically called when the reference
count of a node reaches zero. Alg. 4: the method for marking a subtree as pruned. Note that each core method
calls specific methods on the visitors to facilitate injection of code at appropriate points. Also, each tree node
reference is an owning reference, except the one created with nonOwningRef in Alg. 3, line 20. Additionally,
the C++ implementation on GitHub can be reached via the ‘BC++’ hyperlinks in the right margin.
with W ⊆ V , the degrees d(x, W ) for each x ∈ X are
considered. We have generalized the WL-1 algorithm
to exploit edge attributes, essentially by abstracting
the degree function. Ordinarily it is assumed to have
the signature d : V × 2V → N0 , but we generalize it
to return a map from each possible edge attribute to
the number of edges with that attribute. That is d has
the signature V × 2V → (ΩE → N0 ). Such mappings
are totally ordered, as we assume ΩE is to be totally
ordered.

A high-level description of the WL-1 algorithm without edge attribute handling is shown in Alg. 5. In this
formulation the delegation to the eHandler object happens in addition to line 4, 7, 9, and 10.

C.4

Tree Traversal

The tree traversal visitor uses the methods
makeChildNode and addLeaf, Fig. 5, to create
new tree nodes and report leaf nodes. Before deciding
which child to create next, it is expected to call the
In practice we delegate the edge handling to the visitor method beforeDescend to allow for pruning
given eHandler object, such that the user can decide of children. Pruning of tree nodes is done by visitors
the most efficient way to count edges and sort vertices. by calling the pruneTree procedure (Alg. 3, line 1),
13

Algorithm 5: WL-1 Refinement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

BC++

Input: π, a reference to an ordered partition
Input: Q, a non-empty FIFO queue of cells of π
Data: C, an associative array V → N0 , for counting neighbours
while Q not empty and π not discrete do
W ← Q.popFront()
foreach v ∈ V do
C[v] ← 0
foreach vertex w ∈ W do
foreach edge (w, x) ∈ E do
C[x] ← C[x] + 1
foreach cell X ∈ π do
Sort the vertices of X according to the counters in C.
Split X into cells X1 , X2 , . . . , Xk according to common
values of C.
Report each cell split using vis.newCell.
if X ∈ Q then
Q.remove(X)
foreach Xi ∈ {X1 , X2 , . . . , Xk } do
Q.pushBack(Xi )
else
Xmax ← the first cell of X1 , X2 , . . . , Xk of maximum
cardinality
foreach Xi ∈ {X1 , X2 , . . . , Xk }\{Xmax } do
Q.pushBack(Xi )

which does not remove the designated subtree, but
simply sets a flag isPruned on each node. Visitors are
then responsible for checking this flag before inspected
a tree node. An example of the DFS implementation
is shown in Alg. 6.

C.5

have a very large amount of tree nodes allocated at
the same time. For investigating how that number develops we can use the provided debug visitor (BC++), which facilitates printing of log messages. It additionally keeps track of the number of tree
nodes allocated, using the treeNodeCreateBegin and
treeNodeDestroy methods. We can thus immediately
visualize how the number of allocated nodes develop.
As an example we illustrate this for a relatively small
graph (cfi-rigid-d3-1260-04-2, 1260 vertices). We
ran the same input permutation with DFS, BFSExp,
and BFSExpM limited to 2 MB, see Fig. 9. The current implementation of BFSExpM estimates the memory usage conservatively from the number of arrays of
size n in each tree node and the selected integer type.
Currently we use 32 bit integers and there are 4 arrays per tree node, thereby allowing BFSExpM 104
tree nodes before it goes into DFS mode. Here the ordinary DFS memory usage is added, which in this case
is at most 7 tree nodes extra (the maximum distance
from the root for this search tree).

Automorphisms

Explicit automorphisms are provided by the core
through the visitor method isomorphicLeaf, where
some pruning is immediately done. Implicit automorphisms are reported from visitors through
implicitAutomorphism. Pruning of children takes
place in the beforeDescend visitor method. Pseudocode for a generic automorphism pruner is shown
in Alg. 7, while pseudocode for a visitor for deducing
implicit automorphisms in specific cases is shown in
Alg. 8.

D

Examples of Search Tree Visualization

The provided stats visitor (BC++) makes it trivial
to create visualizations of the explored search tree, in
addition to obtaining statistics. An example of search
tree visualization for a small graph is shown in Fig. 7
and for a larger graph in Fig. 8.

E

Investigating the Number of
Allocated Nodes

The reson for developing the memory sensitive tree
traversal BFSExpM is that the plain BFSExp may
14

Algorithm 6: Visitor: DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Algorithm 8: Visitor: Implicit Automorphisms,
Cell Size 2
BC++

BC++

@ traverseTree(τ ):
vis.beforeDescend(τ )
if τ .isPruned then
return
if τ .π is discrete then
addLeaf(τ )
return
foreach w ∈ τ .targetCell do
vis.beforeDescend(τ )
if τ .isPruned then
return
if τ .childPruned[w] then
continue
τchild ← makeChildNode(τ , w)
if τchild 6= nil then
traverseTree(τchild )

1
2
3
4
5
6

7
8
9

Algorithm 7: Visitor: Pruning With Automorphisms
BC++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Tree data: A = {}, a set of permutations, generating the
group hAi.
Node data: k = 0, number of permutations used for last
pruning.
Node data: stab = {}, (a subset of) the stabilizer of hAi with
respect to the tree node.
def pruneChildren(τ ):
if τ .parent = nil then
kp ← |A|
else
pruneChildren(τ .parent)
kp ← τ .parent.k
if τ .k = kp then
return
Update τ .stab and τ .k.
Prune children of τ , using the permutations of τ .stab,
while preserving canonLeaf.
@ beforeDescend(τ ):
pruneChildren(τ )
@ isomorphicLeaf(τa ):
τc ← canonLeaf
πc ← τc .π
πa ← τa .π
γ ← πc πa
A ← A ∪ {γ}
τp ← The ancestor of τa for which its parent is lca(τc , τa )
pruneTree(τp )

Tree data: γ = (1), a permutation, initial the identity.
Node data: fulfilled = false, whether the partition of the tree
node fulfills the conditions of the lemma.
@ treeNodeCreateBegin(π):
if π.parent = nil then
return
if not π.parent.fulfilled then
return
π.fulfilled ← true
// All cells in the parent have size 1 or 2, so the cell
with the individualized vertex has a singleton
neighbor. Add a swap of those two vertices to the
permutation.
u ← π.individualizedVertex
v ← vertex(pos(u, π)+1, π)
γ ← γ · (u v)
// Permutation composition.

10
11
12
13

14
15
16
17
18
19
20
21

22
23
24
25
26
27

28
29
30
31

@ newCell(π, p):
if not π.fulfilled then
return
// All cells have size 1 or 2, so the new cell at position
p has a neighbor which is also a singleton. Add a swap
of those two vertices to the permutation.
u ← vertex(p − 1, π)
v ← vertex(p, π)
γ ← γ · (u v)
@ treeNodeCreateEnd(π):
if π.isPruned then
if π.fulfilled then
γ ← (1)
return
// Report the automorphism or check if we now fulfill the
lemma.
if π.fulfilled then
vis.implicitAutomorphism(γ)
γ ← (1)
else if not π discrete then
if all cells of π have size 1 or 2 then
π.fulfilled ← true
// Perform pruning.
if π.fulfilled and not π discrete then
// The target cell only has two vertices.
u, v ← π.targetCell
// Other visitors may have already pruned children.
if not π.childPruned[u] and not π.childPruned[v] then
π.childPruned[v] ← true

@ implicitAutomorphism(γ):
A = A ∪ {γ}

Figure 6: Pseudocode for a selection of visitors. The visitor for automorphism pruning, Alg. 7, is in the
implementation parameterized such that it can be used with different implementations of permutation group
constructs. Alg. 8 is an implementation of one of the cases in Lemma 2-25 [14], where an automorphism can
be deduced when a WL-k algorithm is used to refine an ordered partition containing only cells of size 1 or 2.

15

0
2

id=0, (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)

0
2

id=0, (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)

1

1

0

1
2

0

1
2

1

1

0

15
12
10

id=1, (0 | 9 2 11 4 14 6 | 15 12 7 10 8 3 1 5 13)

id=11, (1 | 10 14 7 15 5 6 | 12 0 11 8 9 3 4 2 13)
2

12

7

id=14, (2 | 8 0 3 9 15 6 | 12 7 11 10 4 1 5 14 13)

15

12
11

7

12

id=1, (0 | 9 2 11 4 14 6 | 15 12 7 10 8 3 1 5 13)
10
3
0

2

id=10, (1 | 10 14 7 15 5 6 | 12 0 11 8 9 3 4 2 13)

id=15, (2 | 8 0 3 9 15 6 | 12 7 11 10 4 1 5 14 13)

7

12

12

0

15

7

12
10

12

12
7

15
12
7
10
3

0

12
11

12

12

7

12

10

0

7

12

11

id=2, (0 | 6 2 | 9 4 | 11 14 | 15 | 3 1 | 10 13 | 8 5 | 7 | 12)
15
id=4, (0 | 9 4 | 11 6 14 2 | 12 | 5 13 10 8 | 15 7 3 1)
12

10

id=7, (0 | 11 14 | 9 4 | 6 2 | 7 | 3 1 | 8 5 | 10 13 | 15 | 12)

id=12, (1 | 10 5 | 15 7 6 14 | 12 | 13 4 8 9 | 0 11 3 2)

id=9, (0 | 9 14 | 11 2 | 6 4 | 10 | 12 1 | 15 13 | 7 8 | 5 | 3)

id=15, (2 | 8 9 | 0 3 | 15 6 | 12 | 10 5 | 4 13 | 7 14 | 1 | 11)
7
id=17, (2 | 8 3 | 15 9 | 0 6 | 7 | 11 5 | 1 14 | 12 13 | 4 | 10)

id=2, (0 | 6 2 | 9 4 | 11 14 | 15 | 3 1 | 10 13 | 8 5 | 7 | 12)
15
id=4, (0 | 9 4 | 11 6 14 2 | 12 | 5 13 10 8 | 15 7 3 1)
12
id=5, (0 | 11 14 | 9 4 | 6 2 | 7 | 3 1 | 8 5 | 10 13 | 15 | 12)

id=7, (0 | 9 14 | 11 2 | 6 4 | 10 | 12 1 | 15 13 | 7 8 | 5 | 3)
3
id=9, (0 | 11 2 | 6 9 4 14 | 3 | 15 7 13 8 | 12 10 1 5)

id=11, (1 | 10 5 | 15 7 6 14 | 12 | 13 4 8 9 | 0 11 3 2)
12

11

id=12, (1 | 6 14 | 15 7 10 5 | 0 | 2 11 4 9 | 12 8 3 13)

id=13, (1 | 7 14 | 10 5 | 15 6 | 11 | 0 3 | 4 13 | 9 8 | 2 | 12)

id=16, (2 | 8 9 | 0 3 | 15 6 | 12 | 10 5 | 4 13 | 7 14 | 1 | 11)

9

6

9

11

15

15

0

9

9

11

10

0

9

6

11

9

11

15

0

15

9

9

11

10

0

9

6

11

15

0

15

9

9

11

10

0

9

id=3, (0 | 2 | 6 | 9 | 4 | 14 | 11 | 15 | 1 | 3 | 10 | 13 | 8 | 5 | 7 | 12)

aut = (1 3)(2 14)(5 13)(6 11)(7 15)(8 10), fixed={ 0 4 9 12 }

aut = (1 3)(2 6)(4 9)(5 8)(10 13)(11 14), fixed={ 0 7 12 15 }, tag=200

id=6, (0 | 4 | 9 | 6 | 2 | 14 | 11 | 12 | 5 | 8 | 10 | 13 | 15 | 1 | 3 | 7)

aut = (1 3)(2 6)(4 9)(5 8)(10 13)(11 14), fixed={ 0 7 12 15 }, tag=200

11

id=5, (0 | 4 | 9 | 11 | 14 | 2 | 6 | 12 | 13 | 10 | 8 | 5 | 7 | 3 | 1 | 15)

id=8, (0 | 14 | 11 | 9 | 4 | 2 | 6 | 7 | 3 | 1 | 8 | 5 | 10 | 13 | 15 | 12)

aut = (0 1)(2 7)(4 10)(5 9)(6 14)(11 15), fixed={ 3 8 12 13 }

aut = (1 12)(2 11)(4 6)(7 8)(9 14)(13 15), fixed={ 0 3 5 10 }, tag=200

aut = (0 3)(4 13)(5 10)(6 15)(7 14)(8 9), fixed={ 1 2 11 12 }, tag=200

id=10, (0 | 14 | 9 | 11 | 2 | 4 | 6 | 10 | 12 | 1 | 13 | 15 | 7 | 8 | 5 | 3)

id=16, (2 | 9 | 8 | 0 | 3 | 6 | 15 | 12 | 5 | 10 | 4 | 13 | 14 | 7 | 1 | 11)

aut = (0 6)(1 14)(3 8)(5 11)(9 15)(12 13), fixed={ 2 4 7 10 }, tag=200

id=13, (1 | 10 | 5 | 15 | 6 | 7 | 14 | 12 | 13 | 4 | 8 | 9 | 2 | 3 | 0 | 11)

id=18, (2 | 3 | 8 | 15 | 9 | 6 | 0 | 7 | 5 | 11 | 1 | 14 | 13 | 12 | 4 | 10)

aut = (1 3)(2 6)(4 9)(5 8)(10 13)(11 14), fixed={ 0 7 12 15 }, tag=200

aut = (1 3)(2 6)(4 9)(5 8)(10 13)(11 14), fixed={ 0 7 12 15 }, tag=200

id=3, (0 | 2 | 6 | 9 | 4 | 14 | 11 | 15 | 1 | 3 | 10 | 13 | 8 | 5 | 7 | 12)

id=6, (0 | 14 | 11 | 9 | 4 | 2 | 6 | 7 | 3 | 1 | 8 | 5 | 10 | 13 | 15 | 12)

aut = (1 12 3)(2 14 4)(5 8 7)(6 9 11)(10 13 15), fixed={ 0 }

aut = (1 3)(2 14)(5 13)(6 11)(7 15)(8 10), fixed={ 0 4 9 12 }

id=8, (0 | 14 | 9 | 11 | 2 | 4 | 6 | 10 | 12 | 1 | 13 | 15 | 7 | 8 | 5 | 3)

aut = (1 12)(2 11)(4 6)(7 8)(9 14)(13 15), fixed={ 0 3 5 10 }, tag=200

id=14, (1 | 14 | 7 | 10 | 5 | 15 | 6 | 11 | 3 | 0 | 13 | 4 | 9 | 8 | 2 | 12)

aut = (0 2 9)(1 5 7)(3 10 4)(6 8 14)(11 15 12), fixed={ 13 }

aut = (0 3)(4 13)(5 10)(6 15)(7 14)(8 9), fixed={ 1 2 11 12 }, tag=200

aut = (0 1 3)(2 14 15 11 6 7)(4 5 8 9 10 13), fixed={ 12 }

id=17, (2 | 9 | 8 | 0 | 3 | 6 | 15 | 12 | 5 | 10 | 4 | 13 | 14 | 7 | 1 | 11)

aut = (0 3)(4 13)(5 10)(6 15)(7 14)(8 9), fixed={ 1 2 11 12 }, tag=200

Figure 7: Example of search trees generated from the same graph (latin-4), with the same random permutation of the input. DFS was used for tree
traversal and FLM for target cell selection. In the top tree no node invariants were enabled, while all were enabled for the bottom tree. Each tree node
has a label with an ID, indicating the order of node creation, and the associated ordered partition. Each tree edge is labelled with the vertex being
individualilzed. The right-most gray nodes (with a label “aut = . . . “) are not tree nodes, but represent discovered automorphisms. Two types exist:
explicit automorphisms, having an in-edge and out-edge from/to leaves indicating which permuted graphs were used to discover the automorphism, and
implicit automorphisms, having only an in-edge from the tree node where some visitor (implicitly indicated by the “tag”) discovered it. In this case all
implicit automorphisms happened to be discovered in leaf nodes. A red node was pruned during creation, here because of node invariants. Purple means
that the node has been pruned (indirectly) through the pruneTree method. A brown leaf node was found worse by a comparison with the current best
leaf. A light green leaf node was once the best leaf, but was later discarded, while the dark green leaf is the resulting canonical form.

16

Figure 8: Example of search trees with different node invariants for a graph
(f-lex-reg-10-2) with 340 vertices. The root of the trees are towards the left, and
we have in these figures removed all labels. Left: the search tree when only PL is enabled, 6723 tree nodes. Middle: with PL and T enabled, 3174 nodes. Right: with all
three (PL, T, and Q) enabled, 2069 nodes. The left tree is down-scaled compared to the
middle and right trees. The FLM target cell selector was used, and the tree traversal was
BFSExp, with the characteristic experimental paths from the tree traversal are highly
visible in all three tress. The importance of node invariants is quite noticable, as entire
subtrees rooted high up in the tree are pruned when enabling more invariants.
17

DFS
BFSExp
BFSExpM

Allocated tree nodes

150

100

50

0
0

200

400

600

800

1,000

1,200

1,400

1,600

1,800

2,000

2,200

2,400

Total tree nodes
Figure 9: Trace of how many tree nodes were allocated every time a new tree node was created. We clearly see
BFSExpM hitting the limit of 104 tree nodes. A large amount of nodes are later deallocated it switches back
from DFS into BFSExp mode. For this choice of memory bound we see a clear trade-off between memory and
time, as BFSExpM finishes later than BFSExp. It is however still faster than DFS.

18

