automaton.scc(algo = "auto")
Compute the strongly-connected components and decorate the input automaton with them.
The algorithm can be:
"auto"
: same as"tarjan"
."dijkstra"
: Dijkstra's algorithm."tarjan"
: Tarjan's algorithm implemented without recursion. Fast and robust to deep automata."tarjan,recursive"
: Tarjan's algorithm implemented with recursion. Faster than"tarjan"
, but might explode on very deep automata."kosaraju"
: Kosaraju's algorithm. Slower.
Examples
This automaton has two strongly connected components:
Component 0:
Component 1:
scc
.component
(num
)
To select a specific component, use component
:
scc
.condense
()
Or view the condensation (each strongly-connected component is reduced as a single state) of the automaton.
scc
.num_components
()
View number of strongly connected components:
The following automaton has 3 components.
Using the recursive implementation of the Tarjan algorithm: