#16352: TransitiveIdeal -> RecursivelyEnumeratedSet in the sage library
-------------------------+-------------------------------------------------
Reporter: | Owner:
slabbe | Status: needs_review
Type: | Milestone: sage-6.6
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers: Vincent Delecroix
combinatorics | Work issues:
Keywords: sd66 | Commit:
Authors: | cecda3246fdbbf96cfb8461ee426dc9d079910ec
Sébastien Labbé | Stopgaps:
Report Upstream: N/A |
Branch: |
u/slabbe/16352 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by slabbe):
Ok, I agree, let's have this discussion. I first tried to replace every
occurences of `TransitiveIdealGraded` by `RecursivelyEnumeratedSet(...,
structure='graded')`, but then I got infinite loops.
The reason is that if a structure is graded, the enumeration currently
done in `RecursivelyEnumeratedSet` saves in memory only two grades (the
current one and the precedent one). If the structure is not graded and we
use the graded argument for `RecursivelyEnumeratedSet`, then we may get
infinite loops and elements that are genereated twice or infinitely often.
I won't have access to my machine until Tuesday for redoing those tests
and tell you exactly where were the infinite loops happening...
Meanwhile, I would like to know for each occurences of
`TransitiveIdealGraded` in the sage library weather the structure was
really graded. I recall that `TransitiveIdealGraded` was not using the
graded hypothesis at all since it was saving *all* of the generated
elements.
A) There were three files where `TransitiveIdealGraded` was used:
File `src/sage/categories/crystals.py`
{{{
#!python
class Crystals(Category_singleton):
class ParentMethods:
def __iter__(self, index_set=None, max_depth=float('inf')):
from sage.combinat.backtrack import TransitiveIdealGraded
from sage.combinat.backtrack import TransitiveIdeal
# was using both ???
def subcrystal(self, index_set=None, generators=None,
max_depth=float("inf"),
from sage.combinat.backtrack import TransitiveIdealGraded
}}}
File `src/sage/categories/highest_weight_crystals.py`
{{{
#!python
class HighestWeightCrystals(Category_singleton):
class ParentMethods:
def __iter__(self, index_set=None, max_depth = float("inf")):
from sage.combinat.backtrack import TransitiveIdealGraded
}}}
File `src/sage/combinat/root_system/root_lattice_realizations.py`
{{{
#!python
from sage.combinat.backtrack import TransitiveIdeal, TransitiveIdealGraded
class RootLatticeRealizations(Category_over_base_ring):
class ParentMethods:
@cached_method
def positive_roots(self, index_set=None):
return TransitiveIdealGraded(attrcall('pred',
index_set=index_set),
[self.simple_root(i) for i in
index_set])
def positive_real_roots(self):
if self.cartan_type().is_finite():
return tuple(TransitiveIdealGraded(attrcall('pred'),
self.simple_roots()))
@cached_method
def positive_roots_parabolic(self, index_set = None):
return TransitiveIdealGraded(parabolic_covers, generators)
class ElementMethods:
def orbit(self):
return [x for x in
TransitiveIdealGraded(attrcall('simple_reflections'), [self])]
def greater(self):
return [x for x in TransitiveIdeal(attrcall('succ'), [self])]
def smaller(self):
return [x for x in TransitiveIdeal(attrcall('pred'), [self])]
}}}
B) For reference, below are the files where only `TransitiveIdeal` was
used.
File `src/sage/groups/conjugacy_classes.py`
{{{
#!python
class ConjugacyClass(Parent):
@cached_method
def set(self):
from sage.combinat.backtrack import TransitiveIdeal
}}}
File `src/sage/combinat/rigged_configurations/kr_tableaux.py`
{{{
#!python
class KirillovReshetikhinTableaux(CrystalOfWords):
def __iter__(self):
from sage.combinat.backtrack import TransitiveIdeal
}}}
File `src/sage/combinat/rigged_configurations/rigged_configurations.py`
{{{
#!python
class RiggedConfigurations(Parent, UniqueRepresentation):
def __iter__(self):
from sage.combinat.backtrack import TransitiveIdeal
}}}
File
`src/sage/combinat/rigged_configurations/tensor_product_kr_tableaux.py`
{{{
#!python
class
TensorProductOfKirillovReshetikhinTableaux(FullTensorProductOfRegularCrystals):
def __iter__(self):
from sage.combinat.backtrack import TransitiveIdeal
}}}
File `src/sage/combinat/root_system/pieri_factors.py`
{{{
#!python
from sage.combinat.backtrack import TransitiveIdeal
class PieriFactors(UniqueRepresentation, Parent):
@cached_method
def elements(self):
return TransitiveIdeal(attrcall('bruhat_lower_covers'),
self.maximal_elements())
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/16352#comment:21>
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.
