[Nauty] Vertex orbits in Nauty

[Kevin Ryde]

Lluís Alemany Puig <lluis.alemany.puig at upc.edu> writes:
>
> some references

If it may help,

     Colbourn and Booth, "Linear Time Automorphism Algorithms for Trees,
     Interval Graphs, and Planar Graphs", 1981

who in turn refer to (but I haven't seen)

    Fontet, "Linear Algorithms for Testing Isomorphism of Planar Graphs", 1976

The broad idea is work upwards from childless vertices to the
root, assigning "id" numbers to each vertex according to the
structure of the subtree below there.  Vertices must be sorted
by id at each phase to ensure same ids for same structure, but
that's a bucket sort so still linear time.

Using Nauty, I'd found sparsenauty() a bit faster on trees
(they're sparse :), and that for a rooted tree it helps to use
an undirected graph with root vertex distinguished (initial lab
and ptn), rather than a directed graph.