⁵⁰⁵⁷⁸ views

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

In [1]:

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

In [2]:

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

Out[2]:

This automaton has two strongly connected components:

In [3]:

c = a.scc()
c

Out[3]:

In [4]:

c.is_isomorphic(a)

Out[4]:

True

To select a specific component, use component:

In [5]:

c.component(0)

Out[5]:

In [6]:

c.component(1)

Out[6]:

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

In [7]:

c.condense()

Out[7]:

View number of strongly connected components:

In [8]:

c.num_components()

Out[8]:

2

The following automaton has 3 components.

In [9]:

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

Out[9]:

Using the recursive implementation of the Tarjan algorithm:

In [10]:

c = a.scc("tarjan_recursive")
c

Out[10]:

In [11]:

c.is_isomorphic(a)

Out[11]:

True

In [12]:

c.component(1)

Out[12]:

In [13]:

c.condense()

Out[13]:

In [14]:

c.num_components()

Out[14]:

3