Load the badic package:

In [1]:
from badic import *

Example of dimension 1¶

In [5]:
a = dag.MatricesGraph([matrix([[1,0],[1,2]]), matrix([[1, 1],[1,0]])])
print(a.is_complete())
a.alphabet

True
Out[5]:
[
[1 0]  [1 1]
[1 2], [1 0]
]
In [6]:
d = a.invariant_density()
print(a.is_invariant_density(d))
d

True
Out[6]:
[1/((2*x0 + x1)*(x0 + x1))]
In [7]:
a.domains_polyhedra()
Out[7]:
[[
[2 1]
[1 1]
]]

Cassaigne algorithm as a win-lose graph¶

In [2]:
a = DetAutomaton([(0,1,1),(0,2,2),(1,0,0),(1,2,2),(2,0,0),(2,1,1)])
a.plot()
Out[2]:

Display 10 steps of the algorithm from state 1:

In [3]:
a.plot_algo(1,10)
Out[3]:

Compute an exact invariant density:

In [4]:
a.invariant_density()
Out[4]:
[1/((x0 + x1 + x2)*(x0 + x1)*(x0 + x2)),
 1/((x0 + x1 + x2)*(x0 + x1)*(x1 + x2)),
 1/((x0 + x1 + x2)*(x0 + x2)*(x1 + x2))]

Plot domains:

In [5]:
a.plot_domains()
Out[5]:

Display corresponding matrices:

In [6]:
a.domains_polyhedra()
Out[6]:
[[
[1 1 1]
[1 0 1]
[0 1 1]
],
 [
[1 1 0]
[1 1 1]
[0 1 1]
],
 [
[1 1 0]
[0 1 1]
[1 1 1]
]]

Convert the win-lose graph to a matrices graph:

In [7]:
a.winlose_to_matrices().plot()
Out[7]:

Make an extension of the win-lose graph of the Cassaigne algorithm:¶

In [8]:
# compute the flip-flop for some set of edges
AS = [[(2,0,0),(0,1,1)],[(2,1,1)]]
a2 = a.flip_flop(AS)
a2.plot()
Out[8]:

Plot domains of the extension:

In [9]:
a2.plot_domains()
Out[9]:

Display corresponding matrices:

In [10]:
ls = a2.domains_polyhedra()
ls
Out[10]:
[[
[2 2 1]
[1 2 1]
[1 1 1]
],
 [
[1 1 0]  [2 2 1]
[1 2 1]  [1 2 1]
[2 2 1], [2 3 2]
],
 [
[1 2 2]  [1 2 1]
[1 1 2]  [0 1 1]
[0 1 1], [1 1 1]
],
 [
[1 1 0]
[1 2 1]
[1 1 1]
],
 [
[1 2 1]  [1 1 1]  [1 2 2]
[0 1 1]  [1 1 2]  [1 1 2]
[1 2 2], [1 2 2], [1 2 3]
],
 [
[1 1 1]
[1 1 2]
[0 1 1]
]]

Compute an exact invariant density:

In [11]:
ld = a2.invariant_density()
ld
Out[11]:
[1/((2*x0 + 2*x1 + x2)*(2*x0 + x1 + x2)*(x0 + x1 + x2)),
 1/((2*x0 + 2*x1 + 3*x2)*(2*x0 + x1 + 2*x2)*(x0 + x1 + 2*x2)) + 1/((x0 + 2*x1 + 2*x2)*(x0 + x1 + 2*x2)*(x1 + x2)),
 1/((2*x0 + 2*x1 + x2)*(2*x0 + x1 + x2)*(x0 + x1)) + 1/((2*x0 + x1 + x2)*(x0 + x1 + x2)*(x0 + x2)),
 1/((x0 + 2*x1 + x2)*(x0 + x1 + x2)*(x1 + x2)),
 1/((2*x0 + 2*x1 + 3*x2)*(2*x0 + x1 + 2*x2)*(x0 + x1 + x2)) + 1/((x0 + 2*x1 + 2*x2)*(x0 + x1 + 2*x2)*(x0 + x1 + x2)) + 1/((2*x0 + x1 + 2*x2)*(x0 + x1 + 2*x2)*(x0 + x2)),
 1/((x0 + 2*x1 + x2)*(x0 + x1 + x2)*(x0 + x1))]

Check that it is indeed an invariant density:

In [12]:
a2.is_invariant_density(ld)
Out[12]:
True

Make another extension of the Cassaigne winlose graph:¶

In [13]:
# compute the flip-flop for another set of edges
AS = [[(2,0,0),(0,1,1)],[(0,1,1),(2,1,1)]]
a2 = a.flip_flop(AS)
print(a2.strongly_connected_components())
a2 = a2.sub_automaton([0,1,2,3,4])
a2.plot()

dict_values([[0, 1, 2, 3, 4], [5]])
Out[13]:

Show domains:

In [14]:
a2.plot_domains()