Skip to content

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

@dcoudert

Description

@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:

Relevant discussions on sage-devel:

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions