Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#26931 closed defect (fixed)

Predictable sorting in simplicial_complex.py

Reported by: Jeroen Demeyer Owned by:
Priority: major Milestone: sage-8.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:

Status badges

Description (last modified by Jeroen Demeyer)

#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 Jeroen Demeyer

Description: modified (diff)

comment:2 Changed 4 years ago by Jeroen Demeyer

Description: modified (diff)

comment:3 Changed 4 years ago by Jeroen Demeyer

Branch: u/jdemeyer/predictable_sorting_in_simplicial_complex_py

comment:4 Changed 4 years ago by Jeroen Demeyer

Cc: John Palmieri added
Commit: 0e6b70ad657f257bed7c97e4fbcd31c6f430f566
Status: newneeds_review

New commits:

0e6b70aSort key as sort_facets parameter of SimplicialComplex

comment:5 Changed 4 years ago by John Palmieri

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 4 years ago by Jeroen Demeyer

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 4 years ago by Jeroen Demeyer

Replying to jhpalmieri:

Is operator.index(a) the way we should be checking whether a is an int or an Integer 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 git

Commit: 0e6b70ad657f257bed7c97e4fbcd31c6f430f566154b61536b55faca6f507c688881570fdc5812f8

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

154b615Sort key as sort_facets parameter of SimplicialComplex

comment:9 in reply to:  5 Changed 4 years ago by Jeroen Demeyer

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 John Palmieri

Reviewers: John Palmieri
Status: needs_reviewpositive_review

Great, thanks.

comment:11 Changed 4 years ago by Volker Braun

Branch: u/jdemeyer/predictable_sorting_in_simplicial_complex_py154b61536b55faca6f507c688881570fdc5812f8
Resolution: fixed
Status: positive_reviewclosed

comment:12 Changed 4 years ago by John Palmieri

Commit: 154b61536b55faca6f507c688881570fdc5812f8

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 4 years ago by Jeroen Demeyer

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 it's an improvement. The changes to the code make sense, so it should just be a matter of specifying the appropriate sorting key.

Version 0, edited 4 years ago by Jeroen Demeyer (next)

comment:14 Changed 4 years ago by John Palmieri

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

Note: See TracTickets for help on using tickets.