# 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:

• Component 0: $\{0\}$
• Component 1: $\{1, 3\}$
In [3]:
c = a.scc()
c

Out[3]:
In [4]:
c.is_isomorphic(a)

Out[4]:
True

### scc.component(num)¶

To select a specific component, use component:

In [5]:
c.component(0)

Out[5]:
In [6]:
c.component(1)

Out[6]:

### scc.condense()¶

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

In [7]:
c.condense()

Out[7]:

### scc.num_components()¶

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