[Nauty] Vertex orbits in Nauty

[Lluís Alemany Puig]

Hello,

Well, that is very interesting. A colleague of mine actually proposed 
that vertex orbits in a tree should be computable in linear time in the 
number of vertices of the tree. So these references are very helpful.

Thank you!

Lluís

On 17/09/2023 02:09, Kevin Ryde wrote:
> 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.