Opened 10 months ago

Last modified 13 days ago

#30263 new defect

declare_union yields wrong results

Reported by: gh-mjungmath Owned by:
Priority: major Milestone: sage-9.4
Component: manifolds Keywords: sets, union
Cc: egourgoulhon, tscrim 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:

Status badges

Description (last modified by mkoeppe)

(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)
<ipython-input-3-c7f527dcc1ea> 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 3-dimensional 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))
3-dimensional 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 (20)

comment:1 Changed 7 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:2 Changed 5 weeks ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

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

comment:3 Changed 4 weeks ago by mkoeppe

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 3 weeks ago by mkoeppe

  • Dependencies set to #31680
  • Description modified (diff)

comment:5 Changed 3 weeks ago by mkoeppe

  • 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 3 weeks ago by mkoeppe

  • Description modified (diff)

comment:7 Changed 3 weeks ago by mkoeppe

  • Dependencies changed from #31680 to #31680, #31718

comment:8 Changed 3 weeks ago by mkoeppe

  • Branch set to u/mkoeppe/declare_union_yields_wrong_results

comment:9 Changed 3 weeks ago by mkoeppe

  • Authors set to Matthias Koeppe
  • Commit set to fca7e8988f5fb5175750252e9b71efea0cf9e483

Last 10 new commits:

f095988FiniteManifoldObjectFamily.__bool__: Remove, inherited from superclass after #31717
5d87ceeManifold{Object,Subset}FiniteFamily: Rename from FiniteManifold{Object,Subset}Family
2f2ace2src/doc/en/reference/manifolds/manifold.rst: Add sage.manifolds.family
1aff58aFix up docstring markup
b922066ManifoldSubsetFiniteFamily: If all subsets are open, include 'open' in repr
30271afFixup doctest
adac07aMerge #31680
78cc27aManifoldSubset.open_covers: Change to generator, add optional arg 'trivial'; update uses
e026e7aManifoldSubset.subset_digraph: Use open_covers method
fca7e89ManifoldSubset.declare_empty etc.

comment:10 Changed 3 weeks ago by git

  • Commit changed from fca7e8988f5fb5175750252e9b71efea0cf9e483 to 26401dd40fb6f24ac1a7a3b5945e3c312c0e002d

Branch pushed to git repo; I updated commit sha1. New commits:

215c378ManifoldSubset.subset_{digraph,poset}: Add plots in documentation, remove # not tested
84896c4ManifoldSubsetFiniteFamily: Use full error message in doctest
3364468Merge #31680
6c8374eManifoldSubset.open_covers: Add option supersets; use it to fix is_empty
28650bcFix doctests
26401ddManifoldSubset.declare_empty: Add plot

comment:11 Changed 3 weeks ago by git

  • Commit changed from 26401dd40fb6f24ac1a7a3b5945e3c312c0e002d to ba512023a38e6aa972d1f796bb27a1d9bd9512bf

Branch pushed to git repo; I updated commit sha1. New commits:

fee8b99ManifoldSubsetFiniteFamily.from_subsets_or_families: New constructor
ba51202ManifoldSubset.declare_union: Add option 'disjoint'

comment:12 Changed 3 weeks ago by git

  • Commit changed from ba512023a38e6aa972d1f796bb27a1d9bd9512bf to 4cf4a52e5e6b063489e18317b9dbfcfbe3b7c4bc

Branch pushed to git repo; I updated commit sha1. New commits:

9ca80d2ManifoldSubset.{equal_subsets,supersets,superset_family}: New
55d2aa8ManifoldSubset.{subset,superset}_digraph: New option quotient; use it for {subset,superset}_poset
4cf4a52ManifoldSubset.declare_equal: New; use it for 1-arg ManifoldSubset.declare_union

comment:13 Changed 3 weeks ago by git

  • Commit changed from 4cf4a52e5e6b063489e18317b9dbfcfbe3b7c4bc to 55a28ce3b93c44619614c85d3cb1c324d0e68a7b

Branch pushed to git repo; I updated commit sha1. New commits:

0f037ffManifoldSubset.intersection: Handle arbitrary intersections
9c75d18intersection: Refactor
8d63c32ManifoldSubset.intersection: Only pass name, latex_name to the final intersection
0867b0cManifoldSubset.intersection: Go through ManifoldSubsetFiniteFamily to make the order of operations canonical
de5f928ManifoldSubset._union_subset: Factor out from ManifoldSubset.union
4698da1ManifoldSubset.union: Handle arbitrary unions
51a89d0ManifoldSubset.union: Add example and plots
55a28ceManifoldSubset.declare_union: Handle arbitrary unions

comment:14 Changed 3 weeks ago by mkoeppe

  • Work issues set to rebase on #31732, #31727

comment:15 Changed 3 weeks ago by mkoeppe

  • Work issues changed from rebase on #31732, #31727 to rebase on #31732, #31727, #31736

comment:16 Changed 13 days ago by mkoeppe

  • Authors Matthias Koeppe deleted
  • Branch u/mkoeppe/declare_union_yields_wrong_results deleted
  • Commit 55a28ce3b93c44619614c85d3cb1c324d0e68a7b deleted
  • Dependencies changed from #31680, #31718 to #31764
  • Work issues rebase on #31732, #31727, #31736 deleted

comment:17 Changed 13 days ago by mkoeppe

  • Description modified (diff)

comment:18 Changed 13 days ago by mkoeppe

  • Description modified (diff)

comment:19 Changed 13 days ago by mkoeppe

  • Branch set to u/mkoeppe/declare_union_yields_wrong_results

comment:20 Changed 13 days ago by mkoeppe

  • Authors set to Matthias Koeppe
  • Commit set to 743f11446a96c32cde3873ebe0a907cdbd0c305b
  • Description modified (diff)

Last 10 new commits:

0032bf9ManifoldSubset.intersection: Go through ManifoldSubsetFiniteFamily to make the order of operations canonical
282010bManifoldSubset._union_subset: Factor out from ManifoldSubset.union
6772570ManifoldSubset.union: Handle arbitrary unions
edfea33ManifoldSubset.union: Add example and plots
fdd0abaManifoldSubset.declare_union: Handle arbitrary unions
c2f484csrc/sage/manifolds/subset.py: import itertools
a083569ManifoldSubset._intersection_subset, _union_subset: Use declare_subset, declare_superset; fix doctest
5d41b46Merge #31764
aceb0e8ManifoldSubset._union_subset: Do cache store the union here
743f114ManifoldSubset._union_subset: Update open covers
Note: See TracTickets for help on using tickets.