Opened 12 months ago

Closed 12 months ago

Last modified 12 months ago

#26931 closed defect (fixed)

Predictable sorting in simplicial_complex.py

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

#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 12 months ago by jdemeyer

  • Description modified (diff)

comment:2 Changed 12 months ago by jdemeyer

  • Description modified (diff)

comment:3 Changed 12 months ago by jdemeyer

  • Branch set to u/jdemeyer/predictable_sorting_in_simplicial_complex_py

comment:4 Changed 12 months ago by jdemeyer

  • Cc jhpalmieri added
  • Commit set to 0e6b70ad657f257bed7c97e4fbcd31c6f430f566
  • Status changed from new to needs_review

New commits:

0e6b70aSort key as sort_facets parameter of SimplicialComplex

comment:5 follow-ups: Changed 12 months ago by jhpalmieri

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 12 months ago by jdemeyer

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 12 months ago by jdemeyer

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 12 months ago by git

  • Commit changed from 0e6b70ad657f257bed7c97e4fbcd31c6f430f566 to 154b61536b55faca6f507c688881570fdc5812f8

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 12 months ago by jdemeyer

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 12 months ago by jhpalmieri

  • Reviewers set to John Palmieri
  • Status changed from needs_review to positive_review

Great, thanks.

comment:11 Changed 12 months ago by vbraun

  • 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 follow-up: Changed 12 months ago by jhpalmieri

  • 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 12 months ago by jdemeyer

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.

Last edited 12 months ago by jdemeyer (previous) (diff)

comment:14 Changed 12 months ago by jhpalmieri

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.