Meta-ticket: Audit/fix graph methods failing when vertices or edges are of incomparable types

[dcoudert]

Is there an existing issue for this?

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

Problem Description

Several methods are failing when the vertices of the graph are of incomparable type. For instance:

sage: Graph([('A','B'),(1,2)]).edges()
<ipython-input-27-266d02e19563>:1: DeprecationWarning: parameter 'sort' will be set to False by default in the future
See https://github.com/sagemath/sage/issues/27408 for details.
  Graph([('A','B'),(Integer(1),Integer(2))]).edges()
<repr(<sage.graphs.views.EdgesView at 0x156af0280>) failed: TypeError: unsupported operand parent(s) for <: 'Integer Ring' and '<class 'str'>'>

sage: Graph([('A', 1)]).faces()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In [26], line 1
----> 1 Graph([('A', Integer(1))]).faces()

File ~/sage/src/sage/graphs/generic_graph.py:6434, in GenericGraph.faces(self, embedding)
   6432 # Storage for face paths
   6433 faces = []
-> 6434 minedge = min(edgeset)
   6435 path = [minedge]
   6436 edgeset.discard(minedge)

TypeError: '<' not supported between instances of 'int' and 'str'

sage: Graph([("A", 1)]).feedback_vertex_set()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In [2], line 1
----> 1 Graph([("A", Integer(1))]).feedback_vertex_set()

File /home/dcoudert/sage/src/sage/graphs/generic_graph.py:9150, in GenericGraph.feedback_vertex_set(self, value_only, solver, verbose, constraint_generation, integrality_tolerance)
   9145     raise ValueError("the only implementation available for "
   9146                      "undirected graphs is with constraint_generation "
   9147                      "set to True")
   9149 # It would be a pity to start a LP if the graph is already acyclic
-> 9150 if ((not self.is_directed() and self.is_forest()) or
   9151         (self.is_directed() and self.is_directed_acyclic())):
   9152     if value_only:
   9153         return 0

File /home/dcoudert/sage/src/sage/graphs/graph.py:1639, in Graph.is_forest(self, certificate, output)
   1608 @doc_index("Graph properties")
   1609 def is_forest(self, certificate=False, output='vertex'):
   1610     """
   1611     Tests if the graph is a forest, i.e. a disjoint union of trees.
   1612 
   (...)
   1637         (False, [68, 66, 69, 67, 65])
   1638     """
-> 1639     connected_components = self.connected_components()
   1640     number_of_connected_components = len(connected_components)
   1641     isit = (self.order() ==
   1642             self.size() + number_of_connected_components)

File /home/dcoudert/sage/src/sage/graphs/connectivity.pyx:166, in sage.graphs.connectivity.connected_components()
    164 for v in G:
    165     if v not in seen:
--> 166         c = connected_component_containing_vertex(G, v, sort=sort)
    167         seen.update(c)
    168         components.append(c)

File /home/dcoudert/sage/src/sage/graphs/connectivity.pyx:284, in sage.graphs.connectivity.connected_component_containing_vertex()
    282 
    283     if sort:
--> 284         c.sort()
    285     return c
    286 

TypeError: '<' not supported between instances of 'int' and 'str'

Proposed Solution

Stop sorting vertices by default whenever possible and add relevant tests / documentation when necessary.

Alternatives Considered

None.

Additional Information

Related issues / PR:

• Deprecate sorting of Graph vertices and edges by default #22349
• Deprecate sorting by default in connected component methods to avoid type errors #35889
• Deprecate sorting by default in connected component methods for graphs #35891
• Add parameter key to methods multiple_edges and edge_boundary #35903
• Make SubgraphSearch robust to vertex labels #35904
• Fix several issues in find_hamiltonian #35956
• Make min_spanning_tree robust to incomparable vertex labels #36232

Relevant discussions on sage-devel:

• https://groups.google.com/g/sage-devel/c/JGtEsRNhKaY
• https://groups.google.com/g/sage-devel/c/BCPeOLIZPwE
• https://groups.google.com/g/sage-devel/c/eZN7lexOvhI
• https://groups.google.com/g/sage-devel/c/euP8tjlWVK8
• https://groups.google.com/g/sage-devel/c/ibjU-ml_vhw

[guninski]

G=Graph([('\x03', '\x05'), ('\x01', 4), ('\x06', 4), ('\x05', 0), (0, 5), ('\x04', 0), (1, 2), (1, 4), ('\x04', 1), ('\x05', 2), ('\x02', 2), ('\x03', 3), ('\x01', 3), ('\x06', 3), ('\x03', 5), ('\x04', 5), ('\x01', '\x02'), ('\x02', '\x06')])
r=G.is_perfect()

TypeError Traceback (most recent call last)
Cell In [1], line 2

[guninski]

This is with different traceback from the is_perfect() testcase

G=graphs.CompleteGraph(4)
H=Graph([("A",1)])
G.subgraph_search(H)

11369 if sort:
> 11370     return sorted(self.vertex_iterator(degree=degree, vertex_property=vertex_property), key=key)

[dcoudert]

Thanks for reporting. With #35904 we have:

sage: G = Graph([('\x03', '\x05'), ('\x01', 4), ('\x06', 4), ('\x05', 0), (0, 5), ('\x04', 0), (1, 2), (1, 4), ('\x04', 1), ('\x05', 2), ('\x02', 2), ('\x03', 3), ('\x01', 3), ('\x06', 3), ('\x03', 5), ('\x04', 5), ('\x01', '\x02'), ('\x02', '\x06')])
sage: G.is_perfect()
False

and

sage: G = graphs.CompleteGraph(4)
sage: H = Graph([("A",1)])
sage: G.subgraph_search(H)
Subgraph of (Complete graph): Graph on 2 vertices

[guninski]

Have you checked regressions? You allow new codepaths, which were not reachable on python3.

[dcoudert]

Have you checked regressions? You allow new codepaths, which were not reachable on python3.

I'm not sure to understand your question. With #35904, we only make SubgraphSearch robust to vertex labels. So the overall code is more robust. Have a look at the code.

[guninski]

I mean are you sure you don't introduce new bugs in extreme cases?

[dcoudert]

Well, previous doctests are satisfied and I added new doctests... Furthermore, the referees may ask for further changes.

[guninski]

I don't have sage-latest and am working on 9.6 from fedora and check the testcases on sagecell.

Is there another place to check testcases on sage-latest?

[dcoudert]

You may use cocalc.com. It should use the last release (10.0).