-
-
Notifications
You must be signed in to change notification settings - Fork 657
Open
Description
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 - some care in
src/sage/graphs/comparability.pyx
#39220
Relevant discussions on sage-devel: