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

Priority:  major  Milestone:  sage8.6 
Component:  python3  Keywords:  
Cc:  John Palmieri  Merged in:  
Authors:  Jeroen Demeyer  Reviewers:  John Palmieri 
Report Upstream:  N/A  Work issues:  
Branch:  154b615 (Commits, GitHub, GitLab)  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 4 years ago by
Description:  modified (diff) 

comment:2 Changed 4 years ago by
Description:  modified (diff) 

comment:3 Changed 4 years ago by
Branch:  → u/jdemeyer/predictable_sorting_in_simplicial_complex_py 

comment:4 Changed 4 years ago by
Cc:  John Palmieri added 

Commit:  → 0e6b70ad657f257bed7c97e4fbcd31c6f430f566 
Status:  new → needs_review 
comment:5 followups: 6 7 9 Changed 4 years 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 Changed 4 years 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 Changed 4 years 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 4 years ago by
Commit:  0e6b70ad657f257bed7c97e4fbcd31c6f430f566 → 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 Changed 4 years 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 4 years ago by
Reviewers:  → John Palmieri 

Status:  needs_review → positive_review 
Great, thanks.
comment:11 Changed 4 years ago by
Branch:  u/jdemeyer/predictable_sorting_in_simplicial_complex_py → 154b61536b55faca6f507c688881570fdc5812f8 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:12 followup: 13 Changed 4 years ago by
Commit:  154b61536b55faca6f507c688881570fdc5812f8 

I was too quick on the positive review. This causes a lot of Python 3 test failures: see #26966.
comment:13 Changed 4 years 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 4 years 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