graph relabel() assumes sortable vertices

[jdemeyer]

There are several cases in relabel() which assume sorting of vertices.

The following cases are fixed:

1. perm=None. This should just relabel with integers from 0 to N-1 in an arbitrary order (as the documentation already says).

2. perm is a callable. This is easy to avoid, as the ordering of the vertices is not used in the code:

           elif callable(perm):
               perm = dict( [ i, perm(i) ] for i in self.vertices() )
               complete_partial_function = False
   

This broke several functions which did assume a particular ordering for G.relabel(perm=None). Those are fixed by using G.relabel(perm=range(G.order())) instead.

Furthermore, we allow arbitrary iterables to be given for relabeling instead of only list and tuple. This improves things with Python 3 where range() becomes an iterator.

[dcoudert]

You could use G.relabel(list(range(G.order()))) instead of G.relabel(list(range(len(G)))).

In generic_graph.py, you changed the doctest G.relabel(return_map=True) == expecting. Isn't it risky to do that ? the ordering of the keys of a dictionary might differ in py2 and py3, no ?

---

New commits:

​4e3dbd7

Avoid sorting vertices in relabel()

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​fe559c5

Avoid sorting vertices in relabel()

[jdemeyer]

Update, still work in progress.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​6f92367

Avoid sorting vertices in relabel()

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​ab00c17

Avoid sorting vertices in relabel()

[jdemeyer]

Green patchbot!

[dcoudert]

Unless I'm mistaken, range is an iterator in py3. Therefore, we cannot do G.relabel(range(G.order())) (several places). Or we must add a specific rule for iterators.

[jdemeyer]

Replying to dcoudert:

Or we must add a specific rule for iterators.

Indeed. This is what I did in this patch.

[dcoudert]

For me this patch is good to go. I did several tests without detecting any hidden issue.

[embray]

Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sage-pending or sage-wishlist.

[vbraun]

Merge conflict

[jdemeyer]

The issue in src/sage/combinat/cluster_algebra_quiver/quiver.py was already fixed by #26985.

So I'm just reverting any changes to that file.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​a7eaec9

Avoid sorting vertices in relabel()

[jdemeyer]

At least one green patchbot, so I'm restoring positive review.

[dcoudert]

OK

[vbraun]

sage -t --long src/sage/combinat/root_system/coxeter_matrix.py
**********************************************************************
File "src/sage/combinat/root_system/coxeter_matrix.py", line 1041, in sage.combinat.root_system.coxeter_matrix.recognize_coxeter_type_from_matrix
Failed example:
    CoxeterMatrix(CoxeterType(['A',10,1]).coxeter_graph()).coxeter_type()
Expected:
    Coxeter type of ['A', 10, 1]
Got:
    Coxeter type of ['A', 10, 1] relabelled by {0: 2, 1: 3, 2: 4, 3: 5, 4: 6, 5: 7, 6: 8, 7: 9, 8: 10, 9: 0, 10: 1}
**********************************************************************
1 item had failures:
   1 of  39 in sage.combinat.root_system.coxeter_matrix.recognize_coxeter_type_from_matrix
    [181 tests, 1 failure, 0.51 s

[jdemeyer]

This failure is caused by interactions with #27029. It doesn't happen by itself.

[dcoudert]

I'm a bit lost here... at least, I don't have errors when testing this ticket alone.

[jdemeyer]

As I said, it's because of this ticket together with #27029.