[Nauty-list] When shortprune() is called?
oga
nauty at oga-site.org
Sun Apr 13 18:27:39 EST 2008
Dear all,
I am a newcomer in nauty-list. I appreciate that I can join the list.
I am reading the paper "Practical Graph Isomorphism"
and studying how the algorithm is implemented in nauty now.
I have some questions about shortprune() in the source code.
(1) When is shortprune() called in firstpathnode0() or firstpathnode()?
# line 615-619 of nauty.c, Version 2.2
# if (needshortprune)
# {
# needshortprune = FALSE;
# shortprune(tcell,fmptr-M,M);
# }
needshortprune seems to be set to TRUE in processnode()
only when the algorithm backtracks to a node that isn't on the first path of the search tree.
(gca_canon != gca_first implies gca_canon > gca_first because the algorithm always generates
earlier nodes before later nodes, and bsf leaf and gca_canon node cannot be on the first path
in the case, right?)
Moreover, needshortprune is set to FALSE and shortprune() is called immediately after
backtracking to the node.
Therefore I cannot find the case where shortprune() in firstpathnode0() is called.
(2) If shortprune() is called and a target cell is changed, is allsamelevel correctly updated?
# line 627-628 of nauty.c, Version 2.2
# if (tcellsize == index && allsamelevel == level + 1)
# --allsamelevel;
A target cell might be changed by calling shortprune(), but tcellsize seems not to be changed.
Is a condition 'tcellsize == index' still valid?
Thank you in advance for any help.
Best regards,
More information about the Nauty
mailing list