LabelledRootedTree requires comparable labels in some cases

cyrilbouvier commented 5 months ago

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 line

Expected 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.2

Checklist

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

fchapoton commented 5 months ago

It is certainly not safe to use rooted trees labelled by elements that cannot be sorted.

One can easily fix the specific issue in graphs by labeling this specific tree by strings everywhere.

Please provide if you can a minimal graph where the tree-styled decomposition fails.

cyrilbouvier commented 5 months ago

Please provide if you can a minimal graph where the tree-styled decomposition fails.
G = Graph('GxJEE?')
G.modular_decomposition(style='tuple') # works ('tuple' is the default value for the style parameter)
G.modular_decomposition(style='tree') # trigger the bug
It is certainly not safe to use rooted trees labelled by elements that cannot be sorted.

I agree, but it is not specified in the documentation, and it is only needed in some special cases. And, as illustrated by the modular_decomposition module, it is used with non sortable labels by Sage itself.

sagemath / sage