[Nauty] Vertex orbits in Nauty
Lluís Alemany Puig
lluis.alemany.puig at upc.edu
Thu Sep 14 19:47:06 AEST 2023
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
More information about the Nauty
mailing list