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: sage-9.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 slabbe

  • Branch set to u/slabbe/30238
  • Commit set to d180dc502b2ba3edb9d4077fc24dacc0c18208b7
  • Status changed from new to needs_review

New commits:

2b310e8first change
d180dc530238:Make RecursivelyEnumeratedSet_forest a subclass of RecursivelyEnumeratedSet_generic

comment:2 Changed 3 months ago by slabbe

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 mkoeppe

  • Status changed from needs_review to needs_work

patchbot indicates doctest failures

comment:4 Changed 3 months ago by slabbe

ok, I will work on that.

comment:5 Changed 3 months ago by git

  • Commit changed from d180dc502b2ba3edb9d4077fc24dacc0c18208b7 to cc0b7ae3d7d32bb13334bc06617ae64888f3d29d

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

41aaa0a30238: fix pycodestyle in map_reduce.py
cc0b7ae30238: adapt sage library code with the algorithm->enumeration change

comment:6 Changed 3 months ago by slabbe

  • 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 --random-seed=0 combinat/subsets_pairwise.py  # 1 doctest failed
sage -t --random-seed=0 combinat/posets/hasse_diagram.py  # 2 doctests failed
----------------------------------------------------------------------   
Last edited 3 months ago by slabbe (previous) (diff)

comment:7 Changed 3 months ago by slabbe

  • 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): 
    539539            struct = 'forest'
    540540        elif classname.startswith('RecursivelyEnumeratedSet_generic'):
    541541            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'
    542550        else:
    543551            A = isinstance(self, RecursivelyEnumeratedSet_generic)
    544552            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 git

  • Commit changed from cc0b7ae3d7d32bb13334bc06617ae64888f3d29d to df88874609fc3337cd178796616c90f9dcd29114

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

df8887430238:using isinstance in __reduce__

comment:9 Changed 3 months ago by slabbe

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 vdelecroix

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

comment:11 Changed 3 months ago by git

  • Commit changed from df88874609fc3337cd178796616c90f9dcd29114 to 3192a9e4b80285c2255b8ddc8a0f7b0698b55f91

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

3192a9e30238:fixing the RecursionError

comment:12 follow-up: Changed 3 months ago by slabbe

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 slabbe

  • Status changed from needs_review to needs_work

comment:14 Changed 3 months ago by git

  • Commit changed from 3192a9e4b80285c2255b8ddc8a0f7b0698b55f91 to 7b65a9580ad87a79308c18d49023189decc5aa1d

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

7b65a9530238:fixing one doctest

comment:15 in reply to: ↑ 12 Changed 3 months ago by tscrim

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 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?

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 mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3
Note: See TracTickets for help on using tickets.