Make RecursivelyEnumeratedSet_forest a subclass of RecursivelyEnumeratedSet_generic
Opened this issue · 22 comments
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.
CC: @tscrim
Component: combinatorics
Author: Sébastien Labbé
Branch/Commit: u/slabbe/30238 @ 7b65a95
Issue created by migration from https://trac.sagemath.org/ticket/30238
Branch: u/slabbe/30238
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.
patchbot indicates doctest failures
ok, I will work on that.
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 --random-seed=0 combinat/subsets_pairwise.py # 1 doctest failed
sage -t --random-seed=0 combinat/posets/hasse_diagram.py # 2 doctests failed
----------------------------------------------------------------------
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:
diff --git a/src/sage/sets/recursively_enumerated_set.pyx b/src/sage/sets/recursively_enumerated_set.pyx
index 2ca2dde..b2f5455 100644
--- a/src/sage/sets/recursively_enumerated_set.pyx
+++ b/src/sage/sets/recursively_enumerated_set.pyx
@@ -539,6 +539,14 @@ cdef class RecursivelyEnumeratedSet_generic(Parent):
struct = 'forest'
elif classname.startswith('RecursivelyEnumeratedSet_generic'):
struct = None
+ # this creates the following error
+ # RecursionError: maximum recursion depth exceeded while calling a Python object
+ #elif hasattr(self, 'map_reduce'):
+ # struct = 'forest'
+ # this creates the following error
+ # RecursionError: maximum recursion depth exceeded while calling a Python object
+ #elif isinstance(self, RecursivelyEnumeratedSet_forest):
+ # struct = 'forest'
else:
A = isinstance(self, RecursivelyEnumeratedSet_generic)
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?
Branch pushed to git repo; I updated commit sha1. New commits:
df88874 | 30238:using isinstance in __reduce__ |
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
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)
<ipython-input-4-c96af998f575> in <module>
----> 1 pickle.dumps(A())
RecursionError: maximum recursion depth exceeded
Branch pushed to git repo; I updated commit sha1. New commits:
3192a9e | 30238:fixing the RecursionError |
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?
Branch pushed to git repo; I updated commit sha1. New commits:
7b65a95 | 30238:fixing one doctest |
Replying to @seblabbe:
One feature of
RecursivelyEnumeratedSet_forestis 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_genericprovides a__reduce__method, I think it forces the classes inheriting fromRecursivelyEnumeratedSet_forestto also overwrite the__reduce__method. Why doesRecursivelyEnumeratedSet_genericneed 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.
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
Setting a new milestone for this ticket based on a cursory review.