lightest: incorrect result
It seems that we are not mature on lightest...
There is probably smaller automata to demonstrate the problem, but at least this one does. We should find something simpler asap.
> c = vcsn.context('lan, q')
> e = c.expression('[ab]*a(<2>[ab])*')
> a = e.automaton()
> b = a | a
> b.shortest(10)
a|a⊕⟨3⟩a|aa⊕⟨2⟩a|ab⊕a|ba⊕⟨3⟩aa|a⊕⟨9⟩aa|aa⊕⟨6⟩aa|ab⊕⟨3⟩aa|ba⊕⟨2⟩ab|a⊕⟨6⟩ab|aa
> b.lightest(10)
a|a⊕a|aa⊕a|ba⊕aa|a⊕aa|aa⊕aa|ba⊕ba|a⊕ba|aa⊕ba|ba⊕a|aaa
This is obviously wrong (a|aa
has weight 3, not 1), even though we use here bread-first. And Yen is not better. Only Eppstein is decent enough to report that it cannot work on this automaton.
@spiat If you have comments about this, I would be happy to hear about them.