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]:
%3 I0 0 0 I0->0 F0 F3 0->F0 1 1 0->1 ⟨6⟩a 3 3 1->3 b 3->F3 3->1 ⟨6⟩a

This automaton has two strongly connected components:

  • Component 0: $\{0\}$
  • Component 1: $\{1, 3\}$
In [3]:
c = a.scc()
c
Out[3]:
%3 I0 0 0.0 I0->0 F0 F3 0->F0 1 1.1 0->1 ⟨6⟩a 3 1.3 1->3 b 3->F3 3->1 ⟨6⟩a
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]:
%3 I0 0 0.0 I0->0 F0 0->F0
In [6]:
c.component(1)
Out[6]:
%3 F3 1 1.1 3 1.3 1->3 b 3->F3 3->1 ⟨6⟩a

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]:
%3 I0 0 0.0 I0->0 F0 F1 0->F0 1 1.1, 1.3 0->1 ⟨6⟩a 1->F1

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]:
%3 I0 0 0 I0->0 F0 F4 F8 0->F0 1 1 0->1 a 5 5 0->5 a 3 3 1->3 b 4 4 3->4 c 4->F4 4->1 a 4->5 a 7 7 5->7 b 8 8 7->8 c 8->F8 8->5 a

Using the recursive implementation of the Tarjan algorithm:

In [10]:
c = a.scc("tarjan_recursive")
c
Out[10]:
%3 I0 0 0.0 I0->0 F0 F4 F8 0->F0 1 1.1 0->1 a 5 2.5 0->5 a 3 1.3 1->3 b 4 1.4 3->4 c 4->F4 4->1 a 4->5 a 7 2.7 5->7 b 8 2.8 7->8 c 8->F8 8->5 a
In [11]:
c.is_isomorphic(a)
Out[11]:
True
In [12]:
c.component(1)
Out[12]:
%3 F4 1 1.1 3 1.3 1->3 b 4 1.4 3->4 c 4->F4 4->1 a
In [13]:
c.condense()
Out[13]:
%3 I0 0 0.0 I0->0 F0 F1 F2 0->F0 1 1.1, 1.3, 1.4 0->1 a 2 2.5, 2.7, 2.8 0->2 a 1->F1 1->2 a 2->F2
In [14]:
c.num_components()
Out[14]:
3