id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
6637 standardize the interface to TransitiveIdeal and friends nthiery mhansen "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`. See #16351.
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` for speed improvements and also to avoid issues explained in C below. See #16352.
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." enhancement closed major sage-6.3 combinatorics fixed backtrack, enumerated set, transitive closure, days57 sage-combinat hivert Sébastien Labbé Travis Scrimshaw N/A 3191690431cfe1614444004863b15a331941ad00 #14052