Deprecate sorting by default in connected component methods to avoid type errors

[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.

Did you read the documentation and troubleshoot guide?

• I have read the documentation and troubleshoot guide

Environment

- **OS**: all
- **Sage Version**: 10.1.beta5

Steps To Reproduce

This issue was reported in https://groups.google.com/g/sage-devel/c/grTffw3S15E for feedback_vertex_set but is actually located in connected_component_containing_vertex

G = Graph([("A",1)])
G.connected_component_containing_vertex(1)

Expected Behavior

['A', 1]

Actual Behavior

sage: G.connected_component_containing_vertex(1)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In [23], line 1
----> 1 G.connected_component_containing_vertex(Integer(1))

File ~/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 'str' and 'int'

Additional Information

We should deprecate sorting vertices by default in connected_components and connected_component_containing_vertex to avoid type errors when vertices are of incomparable types. Users can pass a sorting key to deal with vertices of different types.

[jhpalmieri]

Something like

diff --git a/src/sage/graphs/connectivity.pyx b/src/sage/graphs/connectivity.pyx
index 0cbcb87dd8d..a2f8cb8994d 100644
--- a/src/sage/graphs/connectivity.pyx
+++ b/src/sage/graphs/connectivity.pyx
@@ -119,7 +119,7 @@ def is_connected(G):
         return len(conn_verts) == G.num_verts()
 
 
-def connected_components(G, sort=True):
+def connected_components(G, sort=False):
     """
     Return the list of connected components.
 

?

[dcoudert]

That's the idea but we have to change other parts to really fix the issue.

[videlec]

Maybe this could be fixed together with #35897?

[videlec]

And possibly, add a battery of tests for graphs without sortable vertices...

[dcoudert]

I'm currently working on deprecating sorting by default in connected_components and connected_component_containing_vertex. This is, I think, the best option. Then, if a user wants to sort vertices with incomparable types, this user can design a specific method to order vertices (i.e. the sorting key).

[dcoudert]

I change the title and description of this issue to better reflect it's goal.