MemoryError raised by WordMorphism.fixed_points method

[slabbe]

The following bug was reported to me by Timo Jolivet last July 2012. It is still there is sage-5.3:

sage: s = WordMorphism({1:[1,2],2:[2,3],3:[4],4:[5],5:[6],6:[7],7:[8],8:[9],9:[10],10:[1]})
sage: (s^7).fixed_points()
[word: 122..., word: 2,3,4,...]
sage: (s^7).reversal().fixed_points()
MemoryError [...]

Also reported by Timo Jolivet in October 2012 the following hangs forever:

sage: s = WordMorphism("1->321331332133133,2->133321331332133133,3->2133133133321331332133133")
sage: (s^2).fixed_points()

[slabbe]

Also reported by Timo Jolivet in October 2012 the following hangs forever:

sage: s = WordMorphism("1->321331332133133,2->133321331332133133,3->2133133133321331332133133")
sage: (s^2).fixed_points()

It might be related to the bug in the description of this ticket... I will wait until a solution is found for the first before creating a new ticket for the second as the solution might fix both.

[slabbe]

Tested on sage-5.2

[slabbe]

In fact, this bugs comes from the _fixed_point_iterator method which expand a possibly long word as a list :

sage: s = WordMorphism({1:[1,2],2:[2,3],3:[4],4:[5],5:[6],6:[7],7:[8],8:[9],9:[10],10:[1]})
sage: s7 = s^7
sage: s7r = s7.reversal()
sage: M = matrix(s7r)^10             
sage: max(flatten(map(list, M)))
274861440
sage: s7r10 = s7r^10
sage: it = s7r10._fixed_point_iterator(1)
sage: it.next()
Traceback (most recent call last):
...
in _fixed_point_iterator(self, letter)
   1561             ('a', 1)
   1562         """
-> 1563         w = list(self.image(letter))
   1564         while True:
   1565             for a in self.image(w.pop(0)):

MemoryError:

[slabbe]

It might be related to the bug in the description of this ticket... I will wait until a solution is found for the first before creating a new ticket for the second as the solution might fix both.

Indeed, the solution (which make use of iterators instead of lists) fixes both problems. I just attached a patch. Needs review!

[slabbe]

Moreover, I am getting some timing improvements due to the change of the code of fixed_points method which do not depend anymore on the periodic_points method :

BEFORE:

   sage: f = WordMorphism('a->ab,b->cab,c->bcc')     
   sage: %timeit f.fixed_points()           
   125 loops, best of 3: 2.1 ms per loop        

AFTER:

   sage: f = WordMorphism('a->ab,b->cab,c->bcc')
   sage: %timeit f.fixed_points()               
   625 loops, best of 3: 340 µs per loop   

[tjolivet]

I don't have any problematic examples anymore and the patch changes are simple and effective, so positive review.

[tjolivet]

Note that this patch also fixes the following problem, thanks to better implementation:

sage: s = WordMorphism({1:[1,2],2:[2,3],3:[4],4:[5],5:[6],6:[7],7:[8],8:[9],9:[10],10:[1]})
sage: (s.reversal()^7).fixed_points()
MemoryError
[...]