## Search space traversal

in nauty and tracesIn **nauty**, the search tree is generated in depth-first order.
The lexicographically least leaf is kept.
If the canonical labelling is sought (rather than just the automorphism group),
the leaf with the greatest invariant discovered so far is also kept.
Pruning operations are performed wherever possible, as high in the
tree as possible.

**Traces** introduces an entirely different order of
generating the tree, as a variant of breadth-first order.

An apparent disadvantage of breadth-first order is that pruning by automorphisms is only possible when automorphisms are known, which in general requires leaves of the tree. To remedy this problem, for every node a single path, called an ''experimental path'' is generated from that node down to a leaf of the tree.

Automorphisms are found by comparing the labelled graphs that correspond to those leaves.

We have found experimentally that generating experimental paths randomly tends to find automorphisms that generate larger subgroups, so that the group requires fewer generators altogether and more of the group is available early for pruning.

The group generated by the automorphisms found so far is maintained using the random Schreier method.