#6637: standardize the interface to TransitiveIdeal and friends
-------------------------------------+-------------------------------------
Reporter: nthiery | Owner: mhansen
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.3
Component: combinatorics | Resolution:
Keywords: backtrack, | Merged in:
enumerated set, transitive | Reviewers:
closure, days57 | Work issues:
Authors: | Commit:
Report Upstream: N/A | 42262457c67606ba2861e9ba7b5cb6f20450f09d
Branch: u/slabbe/6637 | Stopgaps:
Dependencies: #14052 |
-------------------------------------+-------------------------------------
Old description:
> 1. Implement a single entry point for recursively enumerated sets:
>
> {{{
> RecursivelyEnumeratedSet(seeds, successors, structure=...,
> enumeration=...)
> }}}
>
> 2. Deprecate `TransitiveIdeal`, `TransitiveIdealGraded` and
> `SearchForest` as entry point.
>
> Remarks:
>
> A. For now the code of `SearchForest` is still in
> `sage/combinat/backtrack.py`. It should be moved in
> `sage/sets/recursively_enumerated_set.pyx` in a later ticket.
>
> B. Note that there are some issues with `TransitiveIdeal` and
> `TransitiveIdealGraded`, namely:
>
> - Enumeration of `TransitiveIdeal` is claimed to be depth first search
> in the top level file `backtrack.py`, but in fact, it is neither breadth
> first neither depth first.
> - Enumeration of `TransitiveIdealGraded` is indeed breadth first as
> claimed but it does not make use of the graded hypothesis at all because
> it remembers every generated elements.
>
> See [http://www.liafa.univ-paris-diderot.fr/~labbe/blogue/2014/04/my-
> status-report-at-sage-days-57-recursivelyenumeratedset/ my status report
> at SageDays57] for more info.
New description:
1. Implement a single entry point for recursively enumerated sets:
{{{
RecursivelyEnumeratedSet(seeds, successors, structure=...,
enumeration=...)
}}}
where `structure` takes values in the set `[None, 'forest', 'graded',
'symmetric']` and `enumeration` takes values in the set `[None, 'depth',
'breadth', 'naive']`.
2. Deprecate `TransitiveIdeal`, `TransitiveIdealGraded` and `SearchForest`
as entry point.
Remarks:
A. For now the code of `SearchForest` is still in
`sage/combinat/backtrack.py`. It should be moved in
`sage/sets/recursively_enumerated_set.pyx` in a later ticket.
B. Note that there are some issues with `TransitiveIdeal` and
`TransitiveIdealGraded`, namely:
- Enumeration of `TransitiveIdeal` is claimed to be depth first search in
the top level file `backtrack.py`, but in fact, it is neither breadth
first neither depth first.
- Enumeration of `TransitiveIdealGraded` is indeed breadth first as
claimed but it does not make use of the graded hypothesis at all because
it remembers every generated elements.
See [http://www.liafa.univ-paris-diderot.fr/~labbe/blogue/2014/04/my-
status-report-at-sage-days-57-recursivelyenumeratedset/ my status report
at SageDays57] for more info.
--
Comment (by slabbe):
I keep the status of the ticket to needs work because I realized that some
doctest were broken in the sage library. I am working on it.
--
Ticket URL: <http://trac.sagemath.org/ticket/6637#comment:34>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
