automaton.lightest_automaton(num=1, algo="auto")

Return an automaton containing only the transitions and states from the lightest path in automaton.

Arguments:

  • num the number of paths in the resulting automaton (there might be fewer).
  • algo the algorithm name.

The algorithm can be:

  • "auto": uses "dijkstra" implementation if the weightset cannot have lightening weights (for example $\mathbb{N}_{\text{min}}$), "bellman-ford" otherwise.
  • "a-star"
  • "bellman-ford"
  • "dijkstra"
  • "yen" : the only algorithm that can be used when trying to retrieve multiple paths, the algorithm does not count loops as possible paths.

Preconditions:

  • "dijkstra": automaton must be tropical.

See also:

Examples

In [1]:
import vcsn
In [2]:
%%automaton --strip aut
context = "lal_char, nmin"
$ -> 0
0 -> 1 <6>a
0 -> 2 <1>a
2 -> 3 <1>b
3 -> 3 <2>b
3 -> 4 <1>c
4 -> 1 <1>d
0 -> 5 <2>a
5 -> 1 <3>b
1 -> $
%3 I0 0 0 I0->0 ⟨0⟩ F1 1 1 0->1 ⟨6⟩a 2 2 0->2 ⟨1⟩a 5 5 0->5 ⟨2⟩a 1->F1 ⟨0⟩ 3 3 2->3 ⟨1⟩b 3->3 ⟨2⟩b 4 4 3->4 ⟨1⟩c 4->1 ⟨1⟩d 5->1 ⟨3⟩b
In [3]:
aut.lightest_automaton()
Out[3]:
%3 I4 4 4 I4->4 ⟨0⟩ F0 0 0 0->F0 ⟨0⟩ 1 1 1->0 ⟨1⟩d 2 2 2->1 ⟨1⟩c 3 3 3->2 ⟨1⟩b 4->3 ⟨1⟩a
In [4]:
aut.lightest_automaton(1, "bellman-ford")
Out[4]:
%3 I4 4 4 I4->4 ⟨0⟩ F0 0 0 0->F0 ⟨0⟩ 1 1 1->0 ⟨1⟩d 2 2 2->1 ⟨1⟩c 3 3 3->2 ⟨1⟩b 4->3 ⟨1⟩a