#26931 closed defect (fixed)
Predictable sorting in simplicial_complex.py
Reported by:  jdemeyer  Owned by:  

Priority:  major  Milestone:  sage8.6 
Component:  python3  Keywords:  
Cc:  jhpalmieri  Merged in:  
Authors:  Jeroen Demeyer  Reviewers:  John Palmieri 
Report Upstream:  N/A  Work issues:  
Branch:  154b615 (Commits)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
#25932 introduced code of the form
try: vertices = tuple(sorted(vertex_set)) except TypeError: vertices = tuple(sorted(vertex_set, key=str))
The problem here is that sorting is not predictable: adding a vertex or considering a face containing only sortable vertices could suddenly change the ordering.
Instead, the sorting key should be explicitly given and the same key should always be used for the same simplicial complex.
Change History (14)
comment:1 Changed 13 months ago by
 Description modified (diff)
comment:2 Changed 13 months ago by
 Description modified (diff)
comment:3 Changed 13 months ago by
 Branch set to u/jdemeyer/predictable_sorting_in_simplicial_complex_py
comment:4 Changed 13 months ago by
 Cc jhpalmieri added
 Commit set to 0e6b70ad657f257bed7c97e4fbcd31c6f430f566
 Status changed from new to needs_review
comment:5 followups: ↓ 6 ↓ 7 ↓ 9 Changed 13 months ago by
I feel like a need a style guide. Is operator.index(a)
the way we should be checking whether a
is an int
or an Integer
or other suitable type? I don't remember seeing that before.
I think that the new doctest
+ The vertices can be sorted with a custom key:: + + sage: SimplicialComplex([10], sort_facets=str) + Simplicial complex with 11 vertices and facets {(0, 1, 10, 2, 3, 4, 5, 6, 7, 8, 9)}
should be at the class level so it appears in the reference manual.
comment:6 in reply to: ↑ 5 Changed 13 months ago by
Replying to jhpalmieri:
I don't remember seeing that before.
It's implicit in a lot of Cython code. But you're right that maybe no Python code in Sage uses it so far.
comment:7 in reply to: ↑ 5 Changed 13 months ago by
Replying to jhpalmieri:
Is
operator.index(a)
the way we should be checking whethera
is anint
or anInteger
or other suitable type?
It's also generally not needed in Sage since we typically convert to a Sage Integer
, not a Python int
. However, range()
requires an int
.
comment:8 Changed 13 months ago by
 Commit changed from 0e6b70ad657f257bed7c97e4fbcd31c6f430f566 to 154b61536b55faca6f507c688881570fdc5812f8
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
154b615  Sort key as sort_facets parameter of SimplicialComplex

comment:9 in reply to: ↑ 5 Changed 13 months ago by
Replying to jhpalmieri:
I think that the new doctest
+ The vertices can be sorted with a custom key:: + + sage: SimplicialComplex([10], sort_facets=str) + Simplicial complex with 11 vertices and facets {(0, 1, 10, 2, 3, 4, 5, 6, 7, 8, 9)}should be at the class level so it appears in the reference manual.
Done.
comment:10 Changed 13 months ago by
 Reviewers set to John Palmieri
 Status changed from needs_review to positive_review
Great, thanks.
comment:11 Changed 13 months ago by
 Branch changed from u/jdemeyer/predictable_sorting_in_simplicial_complex_py to 154b61536b55faca6f507c688881570fdc5812f8
 Resolution set to fixed
 Status changed from positive_review to closed
comment:12 followup: ↓ 13 Changed 13 months ago by
 Commit 154b61536b55faca6f507c688881570fdc5812f8 deleted
I was too quick on the positive review. This causes a lot of Python 3 test failures: see #26966.
comment:13 in reply to: ↑ 12 Changed 13 months ago by
Replying to jhpalmieri:
I was too quick on the positive review. This causes a lot of Python 3 test failures: see #26966.
Even then, I still think that this ticket is an improvement. The changes to the code make sense, so it should just be a matter of specifying the appropriate sorting key.
comment:14 Changed 13 months ago by
Okay, what is the appropriate sorting key? For example, if you take the disjoint union of two simplicial complexes which use different sorting keys, how do you sort the result?
We can put bandaids on this for now, and on one hand, with a few changes, I can decrease the number of failures quite a bit, so that it fixes not just the problems caused by this ticket but (combined with your changes) fixes other problems, too. On the other hand, the whole thing looks very fragile: someone could very easily construct simplicial complexes which break sorting, and once the sorting is lost, homology calculations are unreliable.
So I am not convinced that this ticket as it stands is an improvement.
One way to fix could be to create new classes for each construction, like DisjointUnion
, which keeps track of the factors and sorts in each factor separately. I am very much tempted to roll back this ticket and leave it open as a future enhancement.
Here are some methods which need attention:
 product
 join
 disjoint_union
 wedge
 connected_sum
 link
 star
 generated_subcomplex
 alexander_dual
 stellar_subdivision
 n_skeleton
 connected_component
 fixed_complex
 intersection
_contractible_subcomplex
_enlarge_subcomplex
__copy__
and there are probably others
New commits:
Sort key as sort_facets parameter of SimplicialComplex