Non-linear complexity for OrderedTree.canonical_labelling()

[fwjmath]

Steps To Reproduce

1. In any sage environment, run the following commands

%timeit OrderedTrees(1000).random_element().canonical_labelling()
%timeit OrderedTrees(10000).random_element().canonical_labelling()
%timeit OrderedTrees(100000).random_element().canonical_labelling()

2. Compare the results

Expected Behavior

As we can go through the tree in linear time, we should be able to give canonical labeling (in this case, prefix labeling) in linear time. This is particularly useful for manipulating very large trees for random generation.

Actual Behavior

It seems that the runtime does not grow linearly. Here is the result on my machine for n=1000, 10000, 100000:

49.2 ms ± 2.96 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
1.3 s ± 358 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
38.3 s ± 9.66 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

Additional Information

It is because in AbstractTree.canonical_labelling(), the code does a sort of BFS and uses node_number() to compute the shift for the label of the roots of subtrees of the current tree. However, node_number() is implemented in a linear fashion (no extra field to store the number of nodes), so the combined complexity is much higher than linear (on average).

There are two solutions that I can think of. One is to get a field in AbstractTree to record the number of nodes and compute them on the fly using the information on subtrees. The other (what I used in my own code) is to simply do a DFS and put the labels accordingly. Here is the code, which is minimally written adapted to my own situation:

    @staticmethod
    def __canon_label(tree):
        r'''
        Internal function. Use a recursive approach to compute the canonical
        labeling of a tree without using node_number, which is very costly.
        More precisely, it is quadratic.
        '''
        def aux(tree, curl):
            l = curl[0]
            curl[0] += 1
            return LabelledOrderedTree([aux(x, curl) for x in list(tree)],
                                       label=l)
        return aux(tree, [1])

Environment

- **OS**: Ubuntu 22.04
- **Sage Version**: 9.5

Checklist

• I have searched the existing issues for a bug report that matches the one I want to file, without success.
• I have read the documentation and troubleshoot guide

[DaveWitteMorris]

I don't think the proposed function is a valid canonical labelling. A canonical labelling has to give the same result (up to an automorphism of the graph) even if the vertices are listed in a different order. (I.e., isomorphic trees must have equal labellings, as mentioned in the docstring.) This function does not have that property, so I think we should close this ticket.

[fwjmath]

I don't think the proposed function is a valid canonical labelling. A canonical labelling has to give the same result (up to an automorphism of the graph) even if the vertices are listed in a different order. (I.e., isomorphic trees must have equal labellings, as mentioned in the docstring.) This function does not have that property, so I think we should close this ticket.

Indeed, as the method canonical_labelling is defined in the superclass AbstractTree, we need it to be canonical for this class. However, for OrderedTree, if we want a notion of canonical labelling, it will not be adapted to use the same, as there is an inherent order in an instance of OrderedTree. So I guess what may be more appropriate is to override canonical_labelling in OrderedTree, which also makes more sense, as we cannot use the one in AbstractTree to test isomorphism in OrderedTree.