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:  sage8.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 N1 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 followup: ↓ 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 sage8.6 to sage8.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 sagepending or sagewishlist.
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()