enso-org / enso

Enso Analytics is a self-service data prep and analysis platform designed for data teams.
https://ensoanalytics.com
Apache License 2.0
7.38k stars 323 forks source link

Topological sort for partially comparable values #5834

Open JaroslavTulach opened 1 year ago

JaroslavTulach commented 1 year ago

The newest specification of ordering assumes sort falling back into topological sort as soon as incomparable values are found. While the sort has been enhanced and adjusted in #5742 - the topological sort yet needs to be implemented. There are two variants to implement:

Topological Sort

Objects with partial ordering can still be sorted by topological sort. We will optimistically speculate on linear order of all values, but as soon as we find out it is not there, we resort into topological sorting and attach warnings to notify the user.

Violated Transitivity or Anti-Symmetry

Custom Comparator.from may violate various partial ordering constraints, so a regular topological sort may not be possible. Usually that happens if there is a cycle (e.g. a < b < c < a ) in the ordering.

Even such situation has a reasonable solution (and I implemented it once in the past) - just detect each cycle and collapse the cycle into a single element. Perform a topological sort on the simplified graph (succeeds as all cycles have been eliminated) and then expand the collapsed elements back.

### Tasks
- [ ] Implement topological sort fallback when there are incomparable values
- [ ] Detect cycle, [collapse cycles into sets](https://github.com/apache/netbeans/blob/14b7e4b530f5ea9f9222bcd10a9558c809ede331/platform/openide.util/src/org/openide/util/TopologicalSortException.java#L85), sort the sets, expand them back to elements
JaroslavTulach commented 2 months ago

Nobody asked for this kind of sorting for a really long time.