[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