LabelledRootedTree requires comparable labels in some cases #37631
Description
Steps To Reproduce
With Sage 10.2, the following code raises a TypeError:
from sage.graphs.graph_decompositions.modular_decomposition import NodeType
a = LabelledRootedTree ([], label='a')
b = LabelledRootedTree ([], label='b')
c = LabelledRootedTree ([], label='c')
d = LabelledRootedTree ([], label='d')
e = LabelledRootedTree ([], label='e')
ab = LabelledRootedTree ([a, b], label=NodeType.PARALLEL)
cdp = LabelledRootedTree ([c, d], label=NodeType.PARALLEL)
cds = LabelledRootedTree ([c, d], label=NodeType.SERIES)
cde = LabelledRootedTree ([c, d, e], label=NodeType.SERIES)
LabelledRootedTree ([ab, cde], label=None)
LabelledRootedTree ([ab, cdp], label=None)
LabelledRootedTree ([ab, cds], label=None) # TypeError is raised by this lineExpected Behavior
No error
Actual Behavior
File ~/src/sage-10.2/src/sage/misc/classcall_metaclass.pyx:320, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__()
318 """
319 if cls.classcall is not None:
--> 320 return cls.classcall(cls, *args, **kwds)
321 else:
322 # Fast version of type.__call__(cls, *args, **kwds)
File ~/src/sage-10.2/src/sage/combinat/rooted_tree.py:868, in LabelledRootedTree.__classcall_private__(cls, *args, **opts)
852 @staticmethod
853 def __classcall_private__(cls, *args, **opts):
854 """
855 Ensure that trees created by the sets and directly are the same and
856 that they are instances of :class:`LabelledRootedTree`.
(...)
866 <class 'sage.combinat.rooted_tree.LabelledRootedTrees_all_with_category.element_class'>
867 """
--> 868 return cls._auto_parent.element_class(cls._auto_parent, *args, **opts)
File ~/src/sage-10.2/src/sage/misc/classcall_metaclass.pyx:323, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__()
321 else:
322 # Fast version of type.__call__(cls, *args, **kwds)
--> 323 return (<PyTypeObject*>type).tp_call(cls, args, kwds)
324
325 def __get__(cls, instance, owner):
File ~/src/sage-10.2/src/sage/combinat/abstract_tree.py:2098, in AbstractLabelledTree.__init__(self, parent, children, label, check)
2096 else:
2097 self._label = label
-> 2098 super().__init__(parent, children, check=check)
File ~/src/sage-10.2/src/sage/combinat/rooted_tree.py:198, in RootedTree.__init__(self, parent, children, check)
195 #if not (children.__class__ is self.__class__
196 # and children.parent() == parent):
197 children = [self.__class__(parent, x) for x in children]
--> 198 NormalizedClonableList.__init__(self, parent, children, check=check)
File ~/src/sage-10.2/src/sage/structure/list_clone.pyx:1813, in sage.structure.list_clone.NormalizedClonableList.__init__()
1811 """
1812 ClonableList.__init__(self, parent, lst, False, False)
-> 1813 self.normalize()
1814 self._is_immutable = immutable
1815 if check:
File ~/src/sage-10.2/src/sage/structure/list_clone.pyx:1835, in sage.structure.list_clone.NormalizedClonableList.normalize()
1833 return ClonableList.__exit__(self, typ, value, tracback)
1834
-> 1835 cpdef normalize(self) noexcept:
1836 """
1837 Normalize ``self``
File ~/src/sage-10.2/src/sage/combinat/rooted_tree.py:299, in RootedTree.normalize(self)
297 for st in self:
298 assert st.is_immutable(), "Subtree {} is not normalized".format(st)
--> 299 self._get_list().sort(key=lambda t: t.sort_key())
300 # ensure unique representation
301 self.set_immutable()
TypeError: '<' not supported between instances of 'NodeType' and 'NodeType'Additional Information
The exemple is given with label from sage.graphs.graph_decompositions.modular_decomposition because I stumbled into this bug while calling modular_decomposition(style='tree') for some graphs. All the examples from the doc of the method modular_decomposition works but when I tried with a more complicated graph, it raises the error leading to the bug.
Note that there is nothing special about the class NodeType, to trigger the bug the labels only need to be hashable (required by LabelledRootedTree) but not comparable.
From what I was able to understand the problem comes from the method normalize (inherited from RootedTree) that sort the children of the root using the method sort_key as key.
sage: ab.sort_key()
((2, PARALLEL), (0, 'a'), (0, 'b'))
sage: cdp.sort_key()
((2, PARALLEL), (0, 'c'), (0, 'd'))
sage: cds.sort_key()
((2, SERIES), (0, 'c'), (0, 'd'))
sage: cde.sort_key()
((3, SERIES), (0, 'c'), (0, 'd'), (0, 'e'))
When one tries to create a LabelledRootedTree with at least two children such that the first different tuple in the output of sort_key is not comparable, the assertion is raised.
LabelledRootedTree ([ab, cde], label=None)
This call works because the first tuples of the output of sort_key are comparable (as 2 < 3 the second item of the tuple is not needed for the comparison)
LabelledRootedTree ([ab, cdp], label=None)
This call works because the first tuples of the output of sort_key are equal (both are (2, PARALLEL)) and the remaining tuples are comparable.
LabelledRootedTree ([ab, cds], label=None) # TypeError is raised by this line
This call does not work because (2, PARALLEL) and (2, SERIES) are not comparable.
Environment
- **OS**: Debian
- **Sage Version**: 10.2Checklist
- 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