Opened 2 years ago
Closed 2 years ago
#27027 closed defect (fixed)
graph relabel() assumes sortable vertices
Reported by: | jdemeyer | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.7 |
Component: | graph theory | Keywords: | py3, graph |
Cc: | dcoudert | Merged in: | |
Authors: | Jeroen Demeyer | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | a7eaec9 (Commits, GitHub, GitLab) | Commit: | a7eaec9a42dbdc6839fca59d2f42c8e1f07e6c07 |
Dependencies: | Stopgaps: |
Description (last modified by )
There are several cases in relabel()
which assume sorting of vertices.
The following cases are fixed:
perm=None
. This should just relabel with integers from 0 to N-1 in an arbitrary order (as the documentation already says).
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.
Change History (31)
comment:1 Changed 2 years ago by
- 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
- Branch set to u/jdemeyer/graph_relabel___assumes_sortable_vertices
comment:3 Changed 2 years ago by
- Commit set to 4e3dbd7ca700fb7eec96e234e706897b0c04ac6a
comment:4 Changed 2 years ago by
- 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
Update, still work in progress.
comment:6 Changed 2 years ago by
- Description modified (diff)
comment:7 Changed 2 years ago by
- 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
- Description modified (diff)
comment:9 Changed 2 years ago by
- Description modified (diff)
comment:10 Changed 2 years ago by
- Status changed from new to needs_review
comment:11 Changed 2 years ago by
- Description modified (diff)
comment:12 Changed 2 years ago by
- 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()
|
comment:13 Changed 2 years ago by
Green patchbot!
comment:14 follow-up: ↓ 15 Changed 2 years ago by
- 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
Replying to dcoudert:
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
- Keywords py3 graph added
- 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
- 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:19 Changed 2 years ago by
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
- 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
- Status changed from needs_work to needs_review
comment:22 Changed 2 years ago by
- Status changed from needs_review to positive_review
At least one green patchbot, so I'm restoring positive review.
comment:23 Changed 2 years ago by
OK
comment:24 Changed 2 years ago by
- 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 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
comment:25 Changed 2 years ago by
- Dependencies set to #27033
comment:26 Changed 2 years ago by
This failure is caused by interactions with #27029. It doesn't happen by itself.
comment:27 Changed 2 years ago by
- Dependencies changed from #27033 to #27029
comment:28 Changed 2 years ago by
- Dependencies #27029 deleted
- Status changed from needs_work to positive_review
comment:29 Changed 2 years ago by
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
As I said, it's because of this ticket together with #27029.
comment:31 Changed 2 years ago by
- Branch changed from u/jdemeyer/graph_relabel___assumes_sortable_vertices to a7eaec9a42dbdc6839fca59d2f42c8e1f07e6c07
- Resolution set to fixed
- Status changed from positive_review to closed
You could use
G.relabel(list(range(G.order())))
instead ofG.relabel(list(range(len(G))))
.In
generic_graph.py
, you changed the doctestG.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:
Avoid sorting vertices in relabel()