Metadata-Version: 2.4
Name: polytope_graph
Version: 0.0.2
Summary: Polytope graphs in Sagemath
Home-page: https://gitlab.com/davidsiukaev/polytopegraphs-in-sagemath
Author: Paul Mercat and David Siukaev
Author-email: paul.mercat@univ-amu.fr
License: GPL-3.0-or-later
Keywords: Polytope graphs in SageMath
Description-Content-Type: text/markdown
Requires-Dist: badic>=0.1.3
Dynamic: author
Dynamic: author-email
Dynamic: description
Dynamic: description-content-type
Dynamic: home-page
Dynamic: keywords
Dynamic: license
Dynamic: requires-dist
Dynamic: summary

# PolytopeGraphs in SageMath

This package allows to represent multi-dimensional continued fraction algorithms as polytopes graphs.
It implements the Coulbois's and Fougeron's criterion to determine if there exists a unique ergodic invariant measure absolutely continuous with respect to Lebesgue.

## Installation

You will need to install first [Sagemath](https://www.sagemath.org/).
For plots you also need to install the dot command from [Graphviz](https://graphviz.org/).
Then, you can install the polytope_graph package:
```
$ sage -pip install git+https://gitlab.com/davidsiukaev/polytopegraphs-in-sagemath.git
```

It can take a long time to compile since this package need first to install the [badic package](https://gitlab.com/mercatp/badic).
It should be installed automatically with the previous command line.

## Examples

### Ergodic example

Define and plot a polytope graph:

```
sage: from polytope_graph import *
sage: m1 = matrix([[1,0,1],[0,1,1],[0,0,1]]).transpose()
sage: m2 = matrix([[1,0,0],[0,1,0],[0,0,1]]).transpose()
sage: m3 = matrix([[1,0,0],[0,1,0],[1,0,1]]).transpose()
sage: m4 = matrix([[1,0,1],[0,1,0],[0,1,1]]).transpose()
sage: m5 = matrix([[0,0,1],[1,0,0],[0,1,0]]).transpose()
sage: m6 = matrix([[1,1,0],[0,1,0],[0,1,1]]).transpose()
sage: s1_mat = matrix([[1,0,0],[0,1,0],[0,0,1]])
sage: s2_mat = matrix([[1,0,0,1],[0,1,1,0],[0,0,1,1]])
sage: b = PolytopeGraph([s1_mat, s2_mat, s1_mat], [(0,0,m1),(0,1,m2),(1,0,m3),(1,2,m4),(2,1,m5),(2,2,m6)])
sage: b.plot()
```

![Plot of an example of ergodic PolytopeGraph](https://www.i2m.univ-amu.fr/perso/paul.mercat/ergodic_polytope_graph.png)

Compute a degenerate subgraph for a face with only one vertex:

```
sage: state = 2    # choose a state
sage: lf = b.faces(state)   # compute list of faces of the polytope of this state
sage: face = lf[4]           # choose one face
sage: b2 = b.degenerate_subgraph(state, face) # compute the degenerate subgraph for this face of this state
sage: b2.plot() # plot it
```

![Plot of a degenerate subgraph](https://www.i2m.univ-amu.fr/perso/paul.mercat/ergodic_degenerate_subgraph_polytope_graph.png)

Compute another degenerate subgraph for a face of projective dimension 1:
```
sage: state = 2
sage: lf = b.faces(state)
sage: face = lf[2]
sage: b2 = b.degenerate_subgraph(state, face)
sage: b2.plot()
```

![Plot of a degenerate subgraph](https://www.i2m.univ-amu.fr/perso/paul.mercat/ergodic_degenerate_subgraph2_polytope_graph.png)

Check the Coulbois-Fougeron's criterion:
```
sage: b.Fougeron_Coulbois_criterion()
True
```

### Non-ergodic example

```
sage: from polytope_graph import *
sage: m1 = matrix([[1,0,1],[0,1,0],[0,1,1]])
sage: m2 = matrix([[1,0,0],[0,1,1],[0,0,1]])
sage: m3 = matrix([[1,0,0],[0,1,0],[1,1,1]])
sage: m4 = matrix([[1,0,0],[0,1,0],[0,0,1]])
sage: s1 = matrix([[1,0,0,1],[0,1,1,0],[0,0,1,1]])
sage: s2 = matrix([[1,0,0],[0,1,0],[0,0,1]])
sage: a = PolytopeGraph([s1, s2], [(0,1,m1),(0,1,m2),(1,1,m3),(1,0,m4)])
sage: a.plot()
```

![Plot of a non-ergodic PolytopeGraphe](https://www.i2m.univ-amu.fr/perso/paul.mercat/non-ergodic_polytope_graph.png)

Check the Coulbois-Fougeron's criterion:
```
sage: a.Fougeron_Coulbois_criterion(verb = 1)
The criterion fails for the state 0 and the face:
[1]
[0]
[0]
False
```

```
sage: state = 0
sage: lf = a.faces(state)
sage: face = lf[6]
sage: face
[1]
[0]
[0]
sage: a2 = a.degenerate_subgraph(state, face)
sage: a2.plot()
```

![Plot of a degenerate subgraph](https://www.i2m.univ-amu.fr/perso/paul.mercat/non-ergodic_degenerate_subgraph2_polytope_graph.png)

```
sage: a2.Fougeron_Coulbois_criterion_for_subgraph(verb=2)
[0, 1]
several outgoing edges from state 0
check inequality An inequality (0, -1, 1) x + 0 >= 0
check inequality An inequality (1, 0, 0) x + 0 >= 0
check inequality An inequality (0, 0, 1) x + 0 >= 0
check inequality An inequality (0, 1, -1) x + 0 >= 0
State 0 does not satisfies the criterion

False
```

### Another ergodic example, with non non-negative matrices

```
sage: from polytope_graph import *
sage: s2 = matrix([[1,0,0],[0,1,0],[-1,1,1],[0,0,1]]).transpose()
sage: s1 = identity_matrix(3)
sage: m1 = matrix([[1,0,1],[0,1,1],[0,0,1]]).transpose()
sage: m2 = matrix([[1,0,0],[0,1,0],[1,0,1]]).transpose()
sage: m3 = matrix([[0,1,0],[-1,1,1],[0,0,1]]).transpose()
sage: a = PolytopeGraph([s1, s2], [(0,0,m1), (0,1,m2), (1,0,s1), (1,0,m3)])
sage: a.plot(colors='Set2')
```

![Plot of an example of ergodic PolytopeGraph](https://www.i2m.univ-amu.fr/perso/paul.mercat/ergodic_polytope_graph2.png)

Iterations of the partition on each state:

```
sage: a.plot_state_partition2(1, 12)
```

![Plot of iterated partition for state 1](https://www.i2m.univ-amu.fr/perso/paul.mercat/state_partition1.png)

```
sage: a.plot_state_partition2(0, 12)
```

![Plot of iterated partition for state 0](https://www.i2m.univ-amu.fr/perso/paul.mercat/state_partition0.png)

```
sage: s1 = identity_matrix(3)
sage: s2 = matrix([[1,0,0],[0,1,0],[0,1,1],[1,0,1]]).transpose()
sage: m1 = matrix([[0,0,1],[1,0,1],[0,1,1]]).transpose()
sage: m2 = matrix([[1,0,0],[1,1,0],[1,0,1]]).transpose()
sage: m3 = matrix([[1,1,0],[0,1,0],[0,1,1]]).transpose()
sage: m4 = matrix([[1,1,0],[0,1,1],[1,0,1]]).transpose()
sage: a = PolytopeGraph([s1, s2], [(0,0,m1), (0,1,s1), (1,0,m2), (1,0,m3), (1,0,m4)])
sage: a.plot_state_partition2(0, 13)
```

![Plot of iterated partition with order 13](https://www.i2m.univ-amu.fr/perso/paul.mercat/state_partition_13.png)

### Change color, dark mode

```
sage: from polytope_graph import *
sage: set_dark_mode(2) # transparent mode (set to 1 for dark mode, 0 for light mode)
sage: m1 = matrix([[1,0,1],[0,1,1],[0,0,1]]).transpose()
sage: m2 = matrix([[1,0,0],[0,1,0],[0,0,1]]).transpose()
sage: m3 = matrix([[1,0,0],[0,1,0],[1,0,1]]).transpose()
sage: m4 = matrix([[1,0,1],[0,1,0],[0,1,1]]).transpose()
sage: m5 = matrix([[0,0,1],[1,0,0],[0,1,0]]).transpose()
sage: m6 = matrix([[1,1,0],[0,1,0],[0,1,1]]).transpose()
sage: s1_mat = matrix([[1,0,0],[0,1,0],[0,0,1]])
sage: s2_mat = matrix([[1,0,0,1],[0,1,1,0],[0,0,1,1]])
sage: b = PolytopeGraph([s1_mat, s2_mat, s1_mat], [(0,0,m1),(0,1,m2),(1,0,m3),(1,2,m4),(2,1,m5),(2,2,m6)])
sage: b.plot(colors='Set2') # choose a color map
```

![Plot of a PolytopeGraph with custom colors](https://www.i2m.univ-amu.fr/perso/paul.mercat/ergodic_polytope_graph_colors.png)

### Convert win-lose or matrices graphs to PolytopeGraph

```
sage: from polytope_graph import *
sage: a = PolytopeGraph(dag.CassaigneWinLose())
sage: a.plot()
```

![Plot of the Cassaigne algorithme as a PolytopeGraph](https://www.i2m.univ-amu.fr/perso/paul.mercat/Cassaigne_PolytopeGraph.png)

### Compute the dual algorithm

```
sage: ad = a.dual()
sage: ad.plot()
```

![Plot of the dual of Cassaigne algorithm](https://www.i2m.univ-amu.fr/perso/paul.mercat/dual_Cassaigne_PolytopeGraph.png)

### Convert a general algo to PolytopeGraph

```
sage: from polytope_graph import *
sage: a = dag.JacobiPerron()
sage: a = PolytopeGraph(a)
sage: a.plot()
```

![Plot of the Jacobi-Perron PolytopeGraph](https://www.i2m.univ-amu.fr/perso/paul.mercat/JacobiPerron_PolytopeGraph.png)

The graph is not strongly connected, so we need to restrict to a strongly connected component:

```
sage: c = a.strongly_connected_components()[0]    # choose the main strongly connected component
sage: a = a.subgraph(c)   # take the subgraph
sage: a.plot()
```

![Plot of the Jacobi-Perron reduced PolytopeGraph](https://www.i2m.univ-amu.fr/perso/paul.mercat/JacobiPerron_reduced_PolytopeGraph.png)

