automaton.scc.ipynb

Kernel: Python 3

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

import vcsn
z = vcsn.context('lal_char(abc), z')

a = z.expression('(<2>a<3>b)*').standard()
a

This automaton has two strongly connected components:

• Component 0: $\{0\}$

• Component 1: $\{1, 3\}$

c = a.scc()
c

c.is_isomorphic(a)

True

scc.component(num)

To select a specific component, use component:

c.component(0)

c.component(1)

scc.condense()

Or view the condensation (each strongly-connected component is reduced as a single state) of the automaton.

c.condense()

scc.num_components()

View number of strongly connected components:

c.num_components()

2

The following automaton has 3 components.

a = z.expression("(abc)*{2}").standard()
a

Using the recursive implementation of the Tarjan algorithm:

c = a.scc("tarjan_recursive")
c

c.is_isomorphic(a)

True

c.component(1)

c.condense()

c.num_components()

3