Opened 2 years ago
Last modified 3 months ago
#30263 new defect
declare_union yields wrong results
Reported by:  Michael Jung  Owned by:  

Priority:  major  Milestone:  sage9.8 
Component:  manifolds  Keywords:  sets, union 
Cc:  Eric Gourgoulhon, Travis Scrimshaw  Merged in:  
Authors:  Matthias Koeppe  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/mkoeppe/declare_union_yields_wrong_results (Commits, GitHub, GitLab)  Commit:  743f11446a96c32cde3873ebe0a907cdbd0c305b 
Dependencies:  #31764  Stopgaps: 
Description (last modified by )
(for the visualization of the posets, use #31680 and install the dot2tex
package  without that package, the layout is quite misleading)
sage: M = Manifold(3, 'M') sage: U = M.open_subset('U'); V = M.open_subset('V'); W = M.open_subset('W') sage: M.declare_union(U, V, W)  TypeError Traceback (most recent call last) <ipythoninput3c7f527dcc1ea> in <module>() > 1 M.declare_union(U, V, W) TypeError: declare_union() takes 3 positional arguments but 4 were given sage: def label(element): ....: try: ....: return element._name ....: except AttributeError: ....: return '[' + ', '.join(sorted(x._name for x in element)) + ']' sage: P = M.subset_poset(open_covers=True); P.plot(element_labels={element: label(element) for element in P}) sage: M.declare_union(U, V.union(W)) sage: P = M.subset_poset(open_covers=True); P.plot(element_labels={element: label(element) for element in P}) sage: U.union(V).union(W) Open subset U_union_V_union_W of the 3dimensional differentiable manifold M sage: P = M.subset_poset(open_covers=True); P.plot(element_labels={element: label(element) for element in P}) sage: U.union(V.union(W)) 3dimensional differentiable manifold M sage: P = M.subset_poset(open_covers=True); P.plot(element_labels={element: label(element) for element in P}) # same sage: M.is_subset(U.union(V).union(W)) False
#31764 adds support for arbitrary unions. But the main issue here is the failing associativity of the union.
We fix it as follows.
When creating a union, we update the open covers of the supersets of the members, replacing the union members by the union.
Change History (24)
comment:1 Changed 2 years ago by
Milestone:  sage9.2 → sage9.3 

comment:2 Changed 20 months ago by
Milestone:  sage9.3 → sage9.4 

comment:3 Changed 20 months ago by
Unions of several subsets also appear in another form  as open covers (which are merely lists of subsets and not manifold subsets in their own right). One might ask whether this could be unified as well.
comment:4 Changed 20 months ago by
Dependencies:  → #31680 

Description:  modified (diff) 
comment:5 Changed 20 months ago by
Description:  modified (diff) 

An issue with the existing code is that through a sequence of declare_union
calls, it is possible to obtain a situation in which two subsets must be the same, although declare_union
makes a (not very effective) attempt to stop the user from doing so (by checking whether the two arguments are the same).
In terms of the poset of subsets that is defined by the _subsets
(and _supersets
) attributes (which is visualized by the code from #31680), this is quite problematic.
This could be solved by introducing equivalence classes of subsets  for example by keeping the _subsets
relation acyclic and introducing an _equal_sets
attribute; loops that update subsets will have to be modified.
The elements of the poset introduced in #31680 then would be equivalence classes of subsets rather than subsets.
comment:6 Changed 20 months ago by
Description:  modified (diff) 

comment:7 Changed 20 months ago by
Dependencies:  #31680 → #31680, #31718 

comment:8 Changed 20 months ago by
Branch:  → u/mkoeppe/declare_union_yields_wrong_results 

comment:9 Changed 20 months ago by
Authors:  → Matthias Koeppe 

Commit:  → fca7e8988f5fb5175750252e9b71efea0cf9e483 
Last 10 new commits:
f095988  FiniteManifoldObjectFamily.__bool__: Remove, inherited from superclass after #31717

5d87cee  Manifold{Object,Subset}FiniteFamily: Rename from FiniteManifold{Object,Subset}Family

2f2ace2  src/doc/en/reference/manifolds/manifold.rst: Add sage.manifolds.family

1aff58a  Fix up docstring markup

b922066  ManifoldSubsetFiniteFamily: If all subsets are open, include 'open' in repr

30271af  Fixup doctest

adac07a  Merge #31680

78cc27a  ManifoldSubset.open_covers: Change to generator, add optional arg 'trivial'; update uses

e026e7a  ManifoldSubset.subset_digraph: Use open_covers method

fca7e89  ManifoldSubset.declare_empty etc.

comment:10 Changed 20 months ago by
Commit:  fca7e8988f5fb5175750252e9b71efea0cf9e483 → 26401dd40fb6f24ac1a7a3b5945e3c312c0e002d 

Branch pushed to git repo; I updated commit sha1. New commits:
215c378  ManifoldSubset.subset_{digraph,poset}: Add plots in documentation, remove # not tested

84896c4  ManifoldSubsetFiniteFamily: Use full error message in doctest

3364468  Merge #31680

6c8374e  ManifoldSubset.open_covers: Add option supersets; use it to fix is_empty

28650bc  Fix doctests

26401dd  ManifoldSubset.declare_empty: Add plot

comment:11 Changed 20 months ago by
Commit:  26401dd40fb6f24ac1a7a3b5945e3c312c0e002d → ba512023a38e6aa972d1f796bb27a1d9bd9512bf 

comment:12 Changed 20 months ago by
Commit:  ba512023a38e6aa972d1f796bb27a1d9bd9512bf → 4cf4a52e5e6b063489e18317b9dbfcfbe3b7c4bc 

Branch pushed to git repo; I updated commit sha1. New commits:
9ca80d2  ManifoldSubset.{equal_subsets,supersets,superset_family}: New

55d2aa8  ManifoldSubset.{subset,superset}_digraph: New option quotient; use it for {subset,superset}_poset

4cf4a52  ManifoldSubset.declare_equal: New; use it for 1arg ManifoldSubset.declare_union

comment:13 Changed 20 months ago by
Commit:  4cf4a52e5e6b063489e18317b9dbfcfbe3b7c4bc → 55a28ce3b93c44619614c85d3cb1c324d0e68a7b 

Branch pushed to git repo; I updated commit sha1. New commits:
0f037ff  ManifoldSubset.intersection: Handle arbitrary intersections

9c75d18  intersection: Refactor

8d63c32  ManifoldSubset.intersection: Only pass name, latex_name to the final intersection

0867b0c  ManifoldSubset.intersection: Go through ManifoldSubsetFiniteFamily to make the order of operations canonical

de5f928  ManifoldSubset._union_subset: Factor out from ManifoldSubset.union

4698da1  ManifoldSubset.union: Handle arbitrary unions

51a89d0  ManifoldSubset.union: Add example and plots

55a28ce  ManifoldSubset.declare_union: Handle arbitrary unions

comment:14 Changed 20 months ago by
Work issues:  → rebase on #31732, #31727 

comment:15 Changed 20 months ago by
Work issues:  rebase on #31732, #31727 → rebase on #31732, #31727, #31736 

comment:16 Changed 19 months ago by
Authors:  Matthias Koeppe 

Branch:  u/mkoeppe/declare_union_yields_wrong_results 
Commit:  55a28ce3b93c44619614c85d3cb1c324d0e68a7b 
Dependencies:  #31680, #31718 → #31764 
Work issues:  rebase on #31732, #31727, #31736 
comment:17 Changed 19 months ago by
Description:  modified (diff) 

comment:18 Changed 19 months ago by
Description:  modified (diff) 

comment:19 Changed 19 months ago by
Branch:  → u/mkoeppe/declare_union_yields_wrong_results 

comment:20 Changed 19 months ago by
Authors:  → Matthias Koeppe 

Commit:  → 743f11446a96c32cde3873ebe0a907cdbd0c305b 
Description:  modified (diff) 
Last 10 new commits:
0032bf9  ManifoldSubset.intersection: Go through ManifoldSubsetFiniteFamily to make the order of operations canonical

282010b  ManifoldSubset._union_subset: Factor out from ManifoldSubset.union

6772570  ManifoldSubset.union: Handle arbitrary unions

edfea33  ManifoldSubset.union: Add example and plots

fdd0aba  ManifoldSubset.declare_union: Handle arbitrary unions

c2f484c  src/sage/manifolds/subset.py: import itertools

a083569  ManifoldSubset._intersection_subset, _union_subset: Use declare_subset, declare_superset; fix doctest

5d41b46  Merge #31764

aceb0e8  ManifoldSubset._union_subset: Do cache store the union here

743f114  ManifoldSubset._union_subset: Update open covers

comment:21 Changed 17 months ago by
Milestone:  sage9.4 → sage9.5 

comment:22 Changed 12 months ago by
Milestone:  sage9.5 → sage9.6 

comment:23 Changed 9 months ago by
Milestone:  sage9.6 → sage9.7 

comment:24 Changed 3 months ago by
Milestone:  sage9.7 → sage9.8 

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review.