[Nauty] Vertex orbits in Nauty

[Lluís Alemany Puig]

Hello,

I am using Nauty to enumerate all vertex orbits (automorphism orbits on 
vertices) in trees. To make nauty compute the vertex orbits, I declare a 
graph structure

    graph *g = NULL;
    DYNALLOC2(graph,g,g_sz,n,m,"dreadnaut");

and call the function

    ADDELEMENT(GRAPHROW(g,u,m), k);

to add edges to the graph. After allocating memory for many other 
variables, I use this loop

    actmult = 0;
    for (;;) {
         nauty(
    g,lab,ptn,NULL,orbits,&options,&stats,workspace,
             2*m*worksize,m,n,canong
         );
         if (stats.errstatus) {
             break;
         }
         options.writeautoms = FALSE;
         options.writemarkers = FALSE;
         ++actmult;
         if (multiplicity > 0 && actmult >= multiplicity) {
             break;
         }
    }

I am wondering what the complexity of this method is when the graph 
structure is that of a tree.

  * Does Nauty apply any special, faster algorithm to deal with this
    specific case?
  * If not, what is the expected complexity? I mean, perhaps the
    algorithm for general graphs has some exponential factor that
    disappears when it is run on trees. Could you point me to some
    references I can cite, please?

Thank you very much!

Lluís Alemany-Puig