Opened 3 months ago
Last modified 6 weeks ago
#30238 needs_work enhancement
Make RecursivelyEnumeratedSet_forest a subclass of RecursivelyEnumeratedSet_generic
Reported by:  slabbe  Owned by:  

Priority:  major  Milestone:  sage9.3 
Component:  combinatorics  Keywords:  
Cc:  tscrim  Merged in:  
Authors:  Sébastien Labbé  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/slabbe/30238 (Commits)  Commit:  7b65a9580ad87a79308c18d49023189decc5aa1d 
Dependencies:  Stopgaps: 
Description
As a follow up of #16351, we integrate the class RecursivelyEnumeratedSet_forest
as a subclass of RecursivelyEnumeratedSet_generic
implementing the following change:
class RecursivelyEnumeratedSet_forest(Parent): +class RecursivelyEnumeratedSet_forest(RecursivelyEnumeratedSet_generic):
and consequential changes.
I was hoping this to be enough to activate few methods like to_digraph
from the generic class that I like to use but are currently not available for the forest type. But unfortunately, the implementation of breadth first search for forest type does not yet take into account the max_depth
argument. That will be dealt in another ticket.
Change History (16)
comment:1 Changed 3 months ago by
 Branch set to u/slabbe/30238
 Commit set to d180dc502b2ba3edb9d4077fc24dacc0c18208b7
 Status changed from new to needs_review
comment:2 Changed 3 months ago by
Note: I am changing the ordering of the input of the init method of RecursivelyEnumeratedSet_forest
to match the one of RecursivelyEnumeratedSet_generic
. This might break code using RecursivelyEnumeratedSet_forest
if such code exists. One option is to make this ticket less intrusive by preserving the previous ordering for the init of RecursivelyEnumeratedSet_forest
.
This is transparent for the code based on the function RecursivelyEnumeratedSet
. The problem was only if people were using directly RecursivelyEnumeratedSet_forest
.
comment:3 Changed 3 months ago by
 Status changed from needs_review to needs_work
patchbot indicates doctest failures
comment:4 Changed 3 months ago by
ok, I will work on that.
comment:5 Changed 3 months ago by
 Commit changed from d180dc502b2ba3edb9d4077fc24dacc0c18208b7 to cc0b7ae3d7d32bb13334bc06617ae64888f3d29d
comment:6 Changed 3 months ago by
 Status changed from needs_work to needs_review
I am changing the status to needs review just to see what the patchbot says. Locally, I still have at least the following issues, but I did not tested the whole library.
 sage t randomseed=0 combinat/subsets_pairwise.py # 1 doctest failed sage t randomseed=0 combinat/posets/hasse_diagram.py # 2 doctests failed 
comment:7 Changed 3 months ago by
 Cc tscrim added
I will need help to fix the above issue. Here is how to reproduce the error:
sage: from sage.combinat.subsets_pairwise import PairwiseCompatibleSubsets sage: def predicate(x,y): return gcd(x,y) == 1 sage: P = PairwiseCompatibleSubsets( [4,5,6,8,9], predicate); P An enumerated set with a forest structure sage: import __main__; __main__.predicate = predicate sage: TestSuite(P).run() Failure in _test_pickling: ... Traceback (most recent call last): ... TypeError: classname(=PairwiseCompatibleSubsets_with_category) does not start with RecursivelyEnumeratedSet but isinstance(self, RecursivelyEnumeratedSet_generic) returns True  The following tests failed: _test_pickling
This is due to the fact that a __reduce__
method exists in the class RecursivelyEnumeratedSet_generic
which is now used by RecursivelyEnumeratedSet_forest
. But the current __reduce__
method is not able to detect properly that self is an instance of RecursivelyEnumeratedSet_forest
when the class is a class derivated from RecursivelyEnumeratedSet_forest
. Testing classname.startswith('RecursivelyEnumeratedSet_forest')
just does not work if the class name is PairwiseCompatibleSubsets_with_category
for instance.
Replacing the code based on the name of the class by hasattr(self, 'map_reduce')
or more naturally by isinstance(self, RecursivelyEnumeratedSet_forest)
does not work because it gives a maximum recursion depth exceeded
error:

src/sage/sets/recursively_enumerated_set.pyx
diff git a/src/sage/sets/recursively_enumerated_set.pyx b/src/sage/sets/recursively_enumerated_set.pyx index 2ca2dde..b2f5455 100644
a b cdef class RecursivelyEnumeratedSet_generic(Parent): 539 539 struct = 'forest' 540 540 elif classname.startswith('RecursivelyEnumeratedSet_generic'): 541 541 struct = None 542 # this creates the following error 543 # RecursionError: maximum recursion depth exceeded while calling a Python object 544 #elif hasattr(self, 'map_reduce'): 545 # struct = 'forest' 546 # this creates the following error 547 # RecursionError: maximum recursion depth exceeded while calling a Python object 548 #elif isinstance(self, RecursivelyEnumeratedSet_forest): 549 # struct = 'forest' 542 550 else: 543 551 A = isinstance(self, RecursivelyEnumeratedSet_generic) 544 552 raise TypeError("classname(={}) does not start with"
I guess that code is based on classname
to avoid that RecursionError
. But I don't understand where the RecursionError
comes from. Travis do you know?
comment:8 Changed 3 months ago by
 Commit changed from cc0b7ae3d7d32bb13334bc06617ae64888f3d29d to df88874609fc3337cd178796616c90f9dcd29114
Branch pushed to git repo; I updated commit sha1. New commits:
df88874  30238:using isinstance in __reduce__

comment:9 Changed 3 months ago by
I updated __reduce__
to use isinstance
instead which is more robust.
The next step is to fix the following Recursion error which I still do not understand:
sage: from sage.combinat.subsets_pairwise import PairwiseCompatibleSubsets sage: def predicate(x,y): return gcd(x,y) == 1 sage: P = PairwiseCompatibleSubsets( [4,5,6,8,9], predicate); P An enumerated set with a forest structure sage: dumps(P) Traceback (most recent call last): ... RecursionError: maximum recursion depth exceeded while calling a Python object
comment:10 Changed 3 months ago by
It appears that the error comes from the reduction of the .post_process
. When the latter is a method then there is a recursive call. A minimal example is
sage: class A: ....: def a(self): pass ....: def __reduce__(self): ....: return (A, (self.a,)) sage: import pickle sage: pickle.dumps(A())  RecursionError Traceback (most recent call last) <ipythoninput4c96af998f575> in <module> > 1 pickle.dumps(A()) RecursionError: maximum recursion depth exceeded
comment:11 Changed 3 months ago by
 Commit changed from df88874609fc3337cd178796616c90f9dcd29114 to 3192a9e4b80285c2255b8ddc8a0f7b0698b55f91
Branch pushed to git repo; I updated commit sha1. New commits:
3192a9e  30238:fixing the RecursionError

comment:12 followup: ↓ 15 Changed 3 months ago by
Thank you Vincent. So, I managed to fix the Recursion error. Now, the same doctests fail for a different reason. I will work on that later.
One feature of RecursivelyEnumeratedSet_forest
is that you can inherit from this class, define your own children and post_process method and it will work (even if you don't provide them in the init). The fact that RecursivelyEnumeratedSet_generic
provides a __reduce__
method, I think it forces the classes inheriting from RecursivelyEnumeratedSet_forest
to also overwrite the __reduce__
method. Why does RecursivelyEnumeratedSet_generic
need a __reduce__
method in the first place?
comment:13 Changed 3 months ago by
 Status changed from needs_review to needs_work
comment:14 Changed 3 months ago by
 Commit changed from 3192a9e4b80285c2255b8ddc8a0f7b0698b55f91 to 7b65a9580ad87a79308c18d49023189decc5aa1d
Branch pushed to git repo; I updated commit sha1. New commits:
7b65a95  30238:fixing one doctest

comment:15 in reply to: ↑ 12 Changed 3 months ago by
Replying to slabbe:
One feature of
RecursivelyEnumeratedSet_forest
is that you can inherit from this class, define your own children and post_process method and it will work (even if you don't provide them in the init). The fact thatRecursivelyEnumeratedSet_generic
provides a__reduce__
method, I think it forces the classes inheriting fromRecursivelyEnumeratedSet_forest
to also overwrite the__reduce__
method. Why doesRecursivelyEnumeratedSet_generic
need a__reduce__
method in the first place?
My guess is so that it pickles well when used to build other objects; e.g., as the basis for a CombinatorialFreeModule
.
comment:16 Changed 6 weeks ago by
 Milestone changed from sage9.2 to sage9.3
New commits:
first change
30238:Make RecursivelyEnumeratedSet_forest a subclass of RecursivelyEnumeratedSet_generic