Opened 2 years ago

Closed 2 years ago

# graph relabel() assumes sortable vertices

Reported by: Owned by: jdemeyer major sage-8.7 graph theory py3, graph dcoudert Jeroen Demeyer David Coudert N/A a7eaec9 a7eaec9a42dbdc6839fca59d2f42c8e1f07e6c07

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).
1. `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.

### comment:1 Changed 2 years ago by jdemeyer

• Description modified (diff)
• Summary changed from graph relabel() with callable should not sort vertices to graph relabel() assumes sortable vertices

### comment:2 Changed 2 years ago by jdemeyer

• Branch set to u/jdemeyer/graph_relabel___assumes_sortable_vertices

### comment:3 Changed 2 years ago by dcoudert

• Commit set to 4e3dbd7ca700fb7eec96e234e706897b0c04ac6a

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()`

### comment:4 Changed 2 years ago by git

• Commit changed from 4e3dbd7ca700fb7eec96e234e706897b0c04ac6a to fe559c5525eb5ca2f275f847c32e1869b9cbecea

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

 ​fe559c5 `Avoid sorting vertices in relabel()`

### comment:5 Changed 2 years ago by jdemeyer

Update, still work in progress.

### comment:6 Changed 2 years ago by jdemeyer

• Description modified (diff)

### comment:7 Changed 2 years ago by git

• Commit changed from fe559c5525eb5ca2f275f847c32e1869b9cbecea to 6f92367a436e9e71999a26ec6c7dee1246f9f347

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

 ​6f92367 `Avoid sorting vertices in relabel()`

### comment:8 Changed 2 years ago by jdemeyer

• Description modified (diff)

### comment:9 Changed 2 years ago by jdemeyer

• Description modified (diff)

### comment:10 Changed 2 years ago by jdemeyer

• Status changed from new to needs_review

### comment:11 Changed 2 years ago by jdemeyer

• Description modified (diff)

### comment:12 Changed 2 years ago by git

• Commit changed from 6f92367a436e9e71999a26ec6c7dee1246f9f347 to ab00c175178632d7dd1835bc618fa08bf5253aa8

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

 ​ab00c17 `Avoid sorting vertices in relabel()`

Green patchbot!

### comment:14 follow-up: ↓ 15 Changed 2 years ago by dcoudert

• Reviewers set to David Coudert

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.

### comment:15 in reply to: ↑ 14 Changed 2 years ago by jdemeyer

Or we must add a specific rule for iterators.

Indeed. This is what I did in this patch.

### comment:16 Changed 2 years ago by dcoudert

• Status changed from needs_review to positive_review

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

### comment:17 Changed 2 years ago by embray

• Milestone changed from sage-8.6 to sage-8.7

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.

### comment:18 Changed 2 years ago by vbraun

• Status changed from positive_review to needs_work

Merge conflict

### comment:19 Changed 2 years ago by 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.

### comment:20 Changed 2 years ago by git

• Commit changed from ab00c175178632d7dd1835bc618fa08bf5253aa8 to a7eaec9a42dbdc6839fca59d2f42c8e1f07e6c07

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

 ​a7eaec9 `Avoid sorting vertices in relabel()`

### comment:21 Changed 2 years ago by jdemeyer

• Status changed from needs_work to needs_review

### comment:22 Changed 2 years ago by jdemeyer

• Status changed from needs_review to positive_review

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

OK

### comment:24 Changed 2 years ago by vbraun

• Status changed from positive_review to needs_work
```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 of  39 in sage.combinat.root_system.coxeter_matrix.recognize_coxeter_type_from_matrix
[181 tests, 1 failure, 0.51 s
```

### comment:25 Changed 2 years ago by jdemeyer

• Dependencies set to #27033

### comment:26 Changed 2 years ago by jdemeyer

This failure is probably caused due to interactions with #27033. It doesn't happen by itself.

Version 0, edited 2 years ago by jdemeyer (next)

### comment:27 Changed 2 years ago by jdemeyer

• Dependencies changed from #27033 to #27029

### comment:28 Changed 2 years ago by jdemeyer

• Dependencies #27029 deleted
• Status changed from needs_work to positive_review

### comment:29 Changed 2 years ago by dcoudert

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

### comment:30 Changed 2 years ago by jdemeyer

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

### comment:31 Changed 2 years ago by vbraun

• Branch changed from u/jdemeyer/graph_relabel___assumes_sortable_vertices to a7eaec9a42dbdc6839fca59d2f42c8e1f07e6c07
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.