#6637: standardize the interface to TransitiveIdeal and friends
-------------------------------------+-------------------------------------
Reporter: nthiery | Owner: mhansen
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.3
Component: combinatorics | Resolution:
Keywords: backtrack, | Merged in:
enumerated set, transitive | Reviewers: Travis Scrimshaw
closure, days57 | Work issues:
Authors: Sébastien Labbé | Commit:
Report Upstream: N/A | d8b942bf45c05f4df5fe093b0b63ac63e7127db6
Branch: | Stopgaps:
public/ticket/6637 |
Dependencies: #14052 |
-------------------------------------+-------------------------------------
Description changed by slabbe:
Old 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.
>
> 3. `TransitiveIdeal(succ, seeds)` keeps the same behavior as before and
> is now the same as `RecursivelyEnumeratedSet(seeds, succ, structure=None,
> enumeration='naive')`.
>
> 4. `TransitiveIdealGraded(succ, seeds, max_depth)` keeps the same
> behavior as before and is now the same as
> `RecursivelyEnumeratedSet(seeds, succ, structure=None,
> enumeration='breadth', max_depth=max_depth)`.
>
> 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 were 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. It is what I call a naive search.
> - 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.
3. `TransitiveIdeal(succ, seeds)` keeps the same behavior as before and is
now the same as `RecursivelyEnumeratedSet(seeds, succ, structure=None,
enumeration='naive')`.
4. `TransitiveIdealGraded(succ, seeds, max_depth)` keeps the same behavior
as before and is now the same as `RecursivelyEnumeratedSet(seeds, succ,
structure=None, enumeration='breadth', max_depth=max_depth)`.
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. `TransitiveIdeal` and `TransitiveIealGraded` are used in the code of
`sage/combinat`, `sage/categories` and `sage/groups` at least. These
should be updated to use `RecursivelyEnumeratedSet in a later ticket for
speed improvements and also to avoid issues explained in C below.
C. Note that there were 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. It is what I call a naive search.
- 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.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/6637#comment:38>
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.
