{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Présentation de la boîte à outils Julia MaxPlus.jl pour l'algèbre (max,+)\n",
    "\n",
    "## Algèbre (max,+)\n",
    "\n",
    "L'algèbre (max,+) (se prononce max-plus) redéfinit les opérateurs addition et multiplication de l'algèbre classique par respectivement les opérateurs maximum noté $\\oplus$ et addition noté $\\otimes$ dans le domaine des nombres réels $\\mathbb{R}$ augmenté du nombre moins l'infini ($\\varepsilon = -\\infty$) que l'on nomme $\\mathbb{R}_{\\varepsilon} = \\mathbb{R} \\cup \\{ -\\infty \\}$. Sa structure algébrique est celle d'un dioïde selectif-inversible selon la classification de Gondran-Minoux (cette structure est appelée plus fréquemment semi-corps idempotent) $(\\mathbb{R}_{\\varepsilon}, \\oplus, \\otimes)$.\n",
    "\n",
    "$$\\forall a,b \\in \\mathbb{R}_{\\varepsilon}: a \\oplus b \\triangleq \\max(a,b)$$\n",
    "$$\\forall a,b \\in \\mathbb{R}_{\\varepsilon}: a \\otimes b \\triangleq a + b$$\n",
    "\n",
    "L'intérêt du calcul matriciel dans cette algèbre est enseigné dès les années 60 par J. Kuntzman dans sa théorie des réseaux. Elle est utilisée dans de nombreux\n",
    "domaines Recherche opérationnelle (théorie des réseaux), Physique (Quantification), Probabilité (transformée de Cramer), Automatique (systèmes à événements discrets), Informatique (théorie des automates, Réseaux de Pétri), Mathématiques (géométrie algébrique).\n",
    "\n",
    "Dans un précédent tuotriel, nous vous avons présenté comment installer notre boîte à outils Max-Plus pour le langage Julia dont le but essentiel est de faciliter les calculs matriciels dans cette algèbre. Ce document présente uniquement les fonctions de base de la boîte à outils tout en introduisant les bases de l'algèbre (max,+). L'algèbre (min,+) fera l'objet d'un autre tutoriel.\n",
    "\n",
    "Pour ceux qui désirent comparer cette boîte à outils avec Sicoslab, on rappelle que sous Sicoslab:\n",
    "- un nombre Max-Plus Sicoslab est créé par la fonction maxplus abrégée par la fonction `#()`, que les éléments neutres sont notés `%0` et `%1`,\n",
    "- qu'un nombre Max-Plus est absorbant par rapport à un nombre, car l'on suppose travailler uniquement dans cet algèbre.\n",
    "- et qu'enfin une documentation et une démonstration sont accessibles depuis les menus de ScicosLab. On pourra consulter la [bibliographie](../docs/src/bibliography.md) pour obtenir la démonstration de certains résultats et la description des algorithmes utilisés sous forme de PDF. Par exemple, le documen [suivant](https://jpquadrat.github.io/TPALGLIN.pdf) décrit les fonctionnalités de la bôite à outils ScicosLab d'une façon similaire à ce présent tutoriel.\n",
    "\n",
    "Dans ce présent document, le terme boîte à outils (Scilab toolbox) est équivalent à paquet (Julia package)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Démarrer la boîte à outils Julia Max-Plus.jl"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Depuis le REPL de Julia, lancez Jupyter notebook :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# using IJulia\n",
    "# notebook()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans un document Jupyter nouvellement créé, chargez la boîte à outil Max-Plus depuis le dossier MaxPlus.jl:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "push!(LOAD_PATH, pwd())\n",
    "using MaxPlus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour le moment, dans un soucis pédagogique, on active un mode d'affichage particulier des nombres Max-Plus affichant explicitement $-\\infty$ et les $0.0$. Des modes d'affichage plus agréables seront expliqués par la suite."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I will show -Inf, +Inf and 0.0"
     ]
    }
   ],
   "source": [
    "set_tropical_display(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette boîte à outils permet de générer du code $\\LaTeX$ via la fonction `Base.show`. Dans Jupyter ce mode semble être celui utilisé par défault, mais ici, on préfère garder l'affichage en texte plein. Pour cela on doit d'abord taper:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "Base.show(io::IO, ::MIME\"text/latex\", x::MP) = show(io, MIME\"text/plain\", x)\n",
    "Base.show(io::IO, ::MIME\"text/latex\", A::MPAbstractVecOrMat) = show(io, MIME\"text/plain\", A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scalaires Max-Plus\n",
    "\n",
    "Avant de présenter l'algèbre (max,+), tapons quelques lignes purement Julia pour apprendre à créer des scalaires Max-Plus grâce au constructeur `MP()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) 5.0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = MP(1.0);  b = MP(3.5);  c = MP(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans Scilab on aurait écrit `#(1.0)`. Dans cette boîte à outils Julia, les nombres Max-Plus sont codés en interne par des `Float64` (via le champ `λ` qui est accessible directement) car les nombres de cette algèbre sont définis dans l'espace $\\mathbb{R}_{\\varepsilon}$. Pour plus de souplesse le constructeur `MP()` accepte des entiers (`Integer`) mais ils seront convertis en interne en `Float64`. Notons qu'il existe d'autres paquets Julia sur les nombres sur Max-Plus qui offrent de changer le type interne en entier mais ce n'est pas le cas de cette boîte à outils (ni ne le sera).\n",
    "\n",
    "Pour repasser dans l'algébre classique (à savoir `(+,*)`) il existe différente manière d'y parvenir. La première façon consiste à accéder au champ `λ` des objets Julia (scalaire) soit via la fonction `plustimes` le fait aussi (son nom vient de Scilab en référence aux opérateurs + * de l'algèbre classique) ou bien des méthodes avec des noms plus dans l'esprit de Julia sont aussi possibles `Float64` et `float`. Ces fonctions accépte également des matrices creuses et pleines ainsi que les vecteurs creux et pleins."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1.0, 1.0, MP, Float64, 1.0, 1.0, 1.0)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a,   a.λ,   typeof(a),   typeof(a.λ),   plustimes(a),   Float64(a),   float(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(MP, Float64, Float64, Float64, Float64)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "typeof(a), typeof(a.λ), typeof(plustimes(a)), typeof(Float64(a)), typeof(float(a))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les nombres Max-Plus contaminent les autres nombres (entiers, réels) : ils convertissent un nombre non Max-Plus en nombre Max-Plus via les opérateurs arithmétiques où les opérateurs de promotion implicites. On effet, d'une part on considère que l'on travaille uniquement dans cette algébre et d'autre part cela simplifie l'écriture du code (ainsi que sa lecture) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Float64, MP, MP, Float64, 5.0)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = 1.0\n",
    "typeof(d),   typeof(c),   typeof(c + d),   typeof((c + d).λ),   c + d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous voyons que l'addition Max-Plus a converti `d` de type `Float64` en type `MP`. Même comportement pour les nombres entiers où `f` de type `Int64` est converti en en type `MP` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Int64, MP, MP, Float64, 5.0)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = 1\n",
    "typeof(f), typeof(c), typeof(c + f), typeof((c + f).λ),   c + f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Les constantes Max-Plus\n",
    "\n",
    "Les éléments neutres pour les opérateurs $\\oplus$ et $\\otimes$ sont donnés sous forme de constantes Julia :\n",
    "- Elément neutre $\\varepsilon$ (parfois noté $\\mathbb{0}$ dans certains documents et sur Scilab `%0`) pour l'opérateur $\\oplus$ : les constantes Julia sont `mp0` ou bien `ε` (obtenu en tapant `\\varepsilon`) valant $-\\infty$ (soit `MP(-Inf)`). Cet élément est absorbant pour la multiplication\n",
    "$\\varepsilon\\otimes a=a\\otimes \\varepsilon=\\varepsilon$.\n",
    "- Elément neutre $e$ (parfois noté $\\mathbb{1}$ dans certains documents et sur Scilab `%1`) pour l'opérateur $\\otimes$ : les constants Julia sont\n",
    "`mp1` ou bien `mpe` valant 0.\n",
    "- Bien que cette boîte à outil est dédiée à l'alègbre Max-Plus elle utilise la constante `mptop` valant $+\\infty$ lorsqu'elle fait des calculs dans l'algèbre duale Min-Plus. Cette constante correspond au `%top` de ScicosLab.\n",
    "\n",
    "Ces nombres sont de type `MP` (et l'on pourra éventuellement les convertir en nombre de l'algèbre classique soit via le champ `λ` soit la fonction `plustimes`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-Inf, -Inf, -Inf, 0.0, 0.0, 0.0, Inf, -Inf, 0.0, Inf, Inf)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mp0, ε, MP(-Inf), mp1, mpe, MP(0), mptop, zero(MP), one(MP), mptop, MP(Inf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Contrôle de l'affichage des nombres Max-Plus\n",
    "\n",
    "Nous voyons que jusqu'à présent, Julia affiche dans ses résultats `-Inf` et `0.0` pour `ε` et `0` ce qui n'est pas très compact. En Max-Plus on manipule souvent de grosses matrices et un affichage bon peut être important : l'affichage doit être compact.\n",
    "\n",
    "Souvenez-vous, qu'en début de document, nous avons écrit `set_tropical_display(0)` pour forcer cet mode d'affichage (dit `style 0`) dans un soucis pédagogique afin que le lecteur ne confonde pas les zéros Max-Plus des zéros de l'algèbre classique. Il existe quatre styles possibles d'affichage des nombres Max-Plus que l'on peut commuter quand on le désire, avec la fonction `set_tropical_display` qui accepte un nombre entre `0` et `4`. Le mode `1` étant celui défini par défaut qui suit l'affichage dans ScicosLab: il permet d'afficher les matrices de façon compact.\n",
    "\n",
    "- `Style 0` : est l'affichage classique de Julia: les nombres $-\\infty$ sont affichés `-Inf` et les nombres sous forme de réels comme `0.0`.\n",
    "- `Style 1 ou 2` : les nombres $-\\infty$ sont affiché sous la forme d'un point `.`.\n",
    "- `Style 3 ou 4` : les nombres $-\\infty$ sont affichés sous la forme `ε`.\n",
    "- `Style 1 ou 3` : les nombres réels qui peuvent être écrits comme des entiers (donc sans chiffres apès la virgule) seront affichés comme des entiers. Par exemple `0.0` s'affiche `0`.\n",
    "- `Style 2 ou 4` : les zéros sont affichés `e`.\n",
    "\n",
    "Le style activé impacte les fonctions, que l'on verra un peu plus tard dans ce document, `Base.show` et impacte également la fonction `LaTeX` pour la génération de code $\\LaTeX$ pour les matrices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I will show -Inf, +Inf and 0.0"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  -Inf    0.0\n",
       "   0.0   -Inf\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Affichage classique façon Julia\n",
    "set_tropical_display(0)\n",
    "\n",
    "J = MP([-Inf 0; 0 -Inf])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I will show (max,+) -Inf and (min,+) +Inf as . and 0.0 as e"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  .   e\n",
       "  e   .\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Affichage des 0 sous la forme de e\n",
    "set_tropical_display(2)\n",
    "\n",
    "J"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I will show (max,+) -Inf and (min,+) +Inf as ε"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  ε   0\n",
       "  0   ε\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Affichage des -Inf sous la forme de ε\n",
    "set_tropical_display(3)\n",
    "\n",
    "J"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I will show (max,+) -Inf and (min,+) +Inf as ε and 0.0 as e"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  ε   e\n",
       "  e   ε\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Affichage des -Inf sous la forme de ε et les 0 sous la forme de e\n",
    "set_tropical_display(4)\n",
    "\n",
    "J"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et finalement, le mode par défaut :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I will show (max,+) -Inf and (min,+) +Inf as ."
     ]
    },
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  .   0\n",
       "  0   .\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Affichage des -Inf sous la forme d'un .\n",
    "set_tropical_display(1)\n",
    "\n",
    "J"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Opérateur Max-Plus $\\oplus$\n",
    "\n",
    "L'opérateur addition est redéfini par l'opérateur `max` de l'algèbre classique. Son symbole, pour le différencier de l'addition dans l'algèbre classique, est $\\oplus$. Mais en Julia on gardera le symbole `+`. Cet opérateur est associatif, commutatif, a un élément neutre (noté $\\varepsilon$) et est idempotent. $\\forall a,b,c \\in \\mathbb{R}_{\\varepsilon}:$\n",
    "\n",
    "$$a \\oplus b \\triangleq \\max(a,b)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 3, 5)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = MP(1); b = MP(3); c = MP(5);\n",
    "(a, b, c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) 3"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a + b   # ≜ max(a, b) ==> max(1, 3) = 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  $\\oplus$ n'est pas inversible ni simplifiable\n",
    "\n",
    "L'égalité suivante $a \\oplus b = a \\oplus c$ n'entraine pas $b = c$. Par contre on aura $a \\oplus b = a$ si $a \\geq b$ ou plus généralement $a \\oplus b = a$ ou $b$. Selon la terminologie de Gondran-Minoux $\\oplus$ est sélectif."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Commutativité de $\\oplus$\n",
    "\n",
    "$$a \\oplus b = b \\oplus a$$\n",
    "$$\\triangleq$$\n",
    "$$\\max(a,b) = \\max(b,a)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a + b == b + a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Associativité de $\\oplus$\n",
    "\n",
    "$$a \\oplus b \\oplus c = (a \\oplus b) \\oplus c = a \\oplus (b \\oplus c)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a + b + c == (a + b) + c == a + (b + c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) 5"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a + b + c # ≜ max(a, b, c) ==> max(1, 3, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Elément neutre $\\varepsilon$ pour $\\oplus$\n",
    "\n",
    "$$a \\oplus \\varepsilon = \\varepsilon \\oplus a = a$$\n",
    "$$\\triangleq$$\n",
    "$$\\max(a,-\\infty) = \\max(-\\infty,a) = a$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a + ε == ε + a == a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Equivallent à :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a + mp0 == mp0 + a == a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((1, ., .), (1, 1), (1, 1))"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(a, mp0, ε), (a + mp0, a + ε), (mp0 + a, ε + a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notons que `0` est neutre pour les nombres positifs :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a + 0 == 0 + a == a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 0, 1)"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a, 0, a + 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### $\\oplus$ est idempotent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) 1"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a + a    # ≜ max(a, a) ==> max(1, 1) == 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Opérateur Max-Plus $\\otimes$\n",
    "\n",
    "L'opérateur multiplication est redéfini par l'opérateur addition qui est associatif, commutatif, a l'élément neutre $e$, l'élément absorbant $\\varepsilon$ et est distributif sur $\\oplus$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) 4"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a * b    # ≜ a + b ==> 1 + 3 == 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Commutativité de $\\otimes$\n",
    "\n",
    "$$a \\otimes b = b \\otimes a$$\n",
    "$$\\triangleq$$\n",
    "$$a + b = b + a$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a * b == b * a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Associativité de $\\otimes$\n",
    "\n",
    "$$a \\otimes b \\otimes c = (a \\otimes b) \\otimes c = a \\otimes (b \\otimes c)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a * b * c == (a * b) * c == a * (b * c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) 9"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a * b * c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Elément neutre $e$ pour $\\otimes$\n",
    "\n",
    "$$a \\otimes e = e \\otimes a = a$$\n",
    "$$\\triangleq$$\n",
    "$$a + 0 = 0 + a = a$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a * mpe == mpe * a == a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Equivalent à :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a * mp1 == mp1 * a == a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Elément absorbant $\\varepsilon$ pour $\\otimes$\n",
    "\n",
    "$$a \\otimes \\varepsilon = \\varepsilon \\otimes a = \\varepsilon$$\n",
    "$$\\triangleq$$\n",
    "$$a -\\infty = -\\infty + a = -\\infty$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a * ε == ε * a == ε"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Equivalent à :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a * mp0 == mp0 * a == mp0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Par convention:\n",
    "\n",
    "$$+\\infty \\otimes \\varepsilon = \\varepsilon \\otimes +\\infty = \\varepsilon$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) ."
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mptop * mp0 # FIXME shall return mp0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### $\\otimes$ n'est pas idempotent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) 2"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a * a    # ≜ a + a == 1 + 1 == 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Distributivité de $\\otimes$ sur $\\oplus$\n",
    "\n",
    "$$a \\otimes (b \\oplus c) = (a \\otimes b) \\oplus (a \\otimes c)$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(a + b) * c == (a * c) + (b * c)     # ==> max(a, b) + c ==> max(a + c, b + c) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) 8"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(a * c) + (b * c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Opérateur puissance\n",
    "\n",
    "En algèbre Max-Plus l'opérateur puissance se comporte comme une multiplication dans l'algèbre classique :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) 10"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MP(2)^5   # ==> 2 * 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) 0"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MP(2)^0   # ==> 2 * 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) -2"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MP(2)^-1   # ==> 2 * -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Au lieu de `^-1` on peut aussi appeler la fonction `inv()` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) -2"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inv(MP(2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vecteur colonnes Max-Plus, matrices Max-Plus (dense et creux)\n",
    "\n",
    "Ce que l'on vient de voir pour les sclaires est également applicable aux vecteurs, matrices qu'ils soient denses (pleines) ou creuses. Notons que cette boîte à outils utilise en interne `using SparseArrays` pour les matrices et vecteurs creux.\n",
    "\n",
    "### Construction de vecteurs colonnes denses Max-Plus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5-element (max,+) vector:\n",
       "  1\n",
       "  2\n",
       "  3\n",
       "  4\n",
       "  5\n"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MP(1:5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5-element (max,+) vector:\n",
       "    1\n",
       "  1.5\n",
       "    2\n",
       "  2.5\n",
       "    3\n"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MP(1:0.5:3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element (max,+) vector:\n",
       "  1\n",
       "  2\n",
       "  3\n"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MP([1, 2, 3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Construction de matrices denses Max-Plus\n",
    "\n",
    "Comme pour les sclaires, la contamination des nombres Max-Plus sur les éléments Int64 et Float64 du vecteur/matrice dense/creux s'applique également :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "    1   2\n",
       "  3.5   4\n"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[MP(1) 2; 3.5 4.0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`MP(1)` de type `MP` a contaminé les éléments entiers/réels de l'algébre classique `2`, `3.0` et `4` en élément de type `MP`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici une autre façon plus élégante de écrire le code précédent :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  1   2\n",
       "  3   4\n"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MP([1 2; 3 4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Autre exemple de contamination des nombres Max-Plus:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  3   1\n",
       "  6   1\n"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = 3; a = MP(1)\n",
    "[f       a\n",
    " f + f   a + a]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le résultat de `f + f` étant de type `Int64`, l'addition classique a été faite avant la promotion en nombre `MP`. Par contre, `a + a` étant de type `MP` c'est l'addition (max, +) qui a été utilisée. Finallement tous les éléments de la matrices sont de type `MP`.\n",
    "\n",
    "Dans l'exemple suivant $\\varepsilon$ a rendu la matrice suivante implicitement Max-Plus: nous n'avons pas eu besoin d'utiliser `MP()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "    .   2\n",
       "  3.5   4\n"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[ε 2; 3.5 4]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Construction de matrices creuses Max-Plus\n",
    "\n",
    "La contamination fonctionne également sur les matrices creuses.\n",
    "\n",
    "Une matrice creuse est une matrice contenant beaucoup de zéros. Sa structure interne est conçue pour ne pas garder en mémoire ces zéros (sauf en Julia s'ils sont explicitement donnés). En algèbre classique les zéros vallent 0 (pour les entiers) ou 0.0 (pour les réels) mais en Max-Plus ils ont pour valeur $-\\infty$ et par conséquent une matrice creuse Max-Plus ne stocke pas les $\\varepsilon$. Rappellons que Julia est basé sur les fonctions `zero()` et `one()` pour redéfinir ces éléments et que les matrices creuses ne stockent pas les éléments `zero()` (faites attention il reste quelques bugs dans l'API `SparseArrays.sparse` où `0` a été utilisé au lieu de `zero()`).\n",
    "\n",
    "Les matrices creuses sont essentielles pour les applications qui necessitent souvent des matrices de grandes tailles. Par exemple dans le calcul du chemin le plus long dans\n",
    "un reseau routier, la taille de la matrice sera le nombre de noeuds, le nombre d'éléments\n",
    "non nuls (le nombre de routes joignant 2 noeuds) va croitre linéairement avec cette taille, alors que le nombre de coefficients de la matrice croit comme le carré de la taille.\n",
    "\n",
    "Pour créer une matrice creuse Max-Plus, plusieurs choix:\n",
    "- soit à partir d'une matrice creuse initialement vide, comme la fonction `mpzeros` que l'on verra plus tard.\n",
    "- soit à partir d'une matrice pleine avec la fonction `SparseArrays.sparse` couplée avec le constructeur `MP`. \n",
    "- soit à partir de trois vecteurs et la fonction `MP` : un vecteur des données à stocker et deux vecteurs indiquant les index de ces données dans la matrice."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans tous les cas il est important d'importer le bon module `using SparseArrays`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I will show (max,+) -Inf and (min,+) +Inf as ."
     ]
    }
   ],
   "source": [
    "using SparseArrays;\n",
    "set_tropical_display(1);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### A partir d'une matrice pleine"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) sparse matrix with 3 stored entries:\n",
       "  [1, 1]  =  1\n",
       "  [1, 2]  =  2\n",
       "  [2, 2]  =  4"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = MP(sparse([1 2; 0 4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ici le zéro de l'algèbre classique (valant 0) a été supprimé par `SparseArrays.sparse` mais dans l'exemple suivant c'est le zéro de l'algébre Max-Plus ($\\varepsilon$ vallant $-\\infty$) qui a sera supprimé."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) sparse matrix with 3 stored entries:\n",
       "  [1, 1]  =  1\n",
       "  [1, 2]  =  2\n",
       "  [2, 2]  =  4"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = sparse(MP([1 2; -Inf 4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le lecteur attentif aura compris que l'affichage est celui de Julia 1.5 même si Julia >= 1.6 est utilisé. En effet, avec Julia 1.6 l'affichage d'une matrice creuse se fait de la même manière qu'une matrice dense ce qui n'a pas de sens. Cette boîte à outils force l'ancien affichage pour les matrices creuses Max-Plus.\n",
    "\n",
    "Pour rappel, la fonction `SparseArrays.findnz` retourne les éléments stockés `D` ainsi que leur indices `I` et `J` sous forme d'un triplet de vecteurs lignes ce qui devient rapidement illisible dès que la matrice grandit un peu :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([1, 1, 2], [1, 2, 2], MP[1, 2, 4])"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i,j,d = findnz(S)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Construction explicite creuse\n",
    "\n",
    "Tout comme `SparseArrays.findnz` retournant un triplet de vecteur colonnes `I`, `J` et `D`, la `SparseArrays.sparse` accepte ses mêmes paramètres. **Mais les zéros explicites seront stockés** :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 (max,+) sparse matrix with 3 stored entries:\n",
       "  [1, 1]  =  42\n",
       "  [2, 2]  =  0\n",
       "  [3, 3]  =  5"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = MP(sparse([1; 2; 3], [1; 2; 3], [42; 0; 5]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ici le zéro de l'algèbre classique (vallant 0) n'a pas été supprimé par `SparseArrays.sparse`. Dans l'exemple suivant c'est le zéro de l'algébre Max-Plus ($\\varepsilon$ vallant $-\\infty$) qui n'a pas été supprimé."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 (max,+) sparse matrix with 3 stored entries:\n",
       "  [1, 1]  =  42\n",
       "  [2, 2]  =  .\n",
       "  [3, 3]  =  5"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = sparse([1; 2; 3], [1; 2; 3], MP([42; -Inf; 5]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ceci est un comportement voulu par Julia pour plus de souplesse car vous pouvez appeller `dropzeros` pour les supprimer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 (max,+) sparse matrix with 2 stored entries:\n",
       "  [1, 1]  =  42\n",
       "  [3, 3]  =  5"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dropzeros(S)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour cela, la constructeur `MP(I,J,Tv)` a été ajoouté: il appelle `dropzeros(sparse(I,J,Tv))` afin de supprimer les zéros explicites :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 (max,+) sparse matrix with 2 stored entries:\n",
       "  [1, 1]  =  0\n",
       "  [3, 3]  =  5"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = MP([1; 2; 3], [1; 2; 3], MP([0; -Inf; 5]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conversion de matrices Max-Plus vers algèbre classique\n",
    "\n",
    "Comme vu précédement pour les scalaires, on peut vouloir convertir une matrice Max-Plus en matrice dans l'algèbre classique (+,*). Le nome vient de l'Anglais: plus et times :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Matrix{Float64}:\n",
       " 4.0    0.0\n",
       " 7.0  -Inf"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = MP([4 0; 7 -Inf])\n",
    "plustimes(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fonctionne aussi pour les matrices creuses :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) sparse matrix with 0 stored entries"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Z = spzeros(MP,2,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 SparseMatrixCSC{Float64, Int64} with 4 stored entries:\n",
       " -Inf  -Inf\n",
       " -Inf  -Inf"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "plustimes(Z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut vouloir passer d'une matrice creuse Max-Plus en matrice pleine  dans l'algèbre classique :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Matrix{Float64}:\n",
       " -Inf  -Inf\n",
       " -Inf  -Inf"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Matrix(plustimes(Z))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conversion d'une matrice creuse en matrice pleine :\n",
    "\n",
    "Les trois fonctions produisent le même résultat :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(MP[. .; . .], MP[. .; . .], MP[. .; . .])"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "full(Z),  dense(Z),   Matrix(Z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Construction de vecteurs colonnes creux Max-Plus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tout comme les matrices creuses plusieurs façons de faire. En préservant les `zero()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element SparseVector{MP, Int64} with 2 stored entries:\n",
       "  [1]  =  0\n",
       "  [3]  =  ."
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sparsevec([1, 3], MP([0, -Inf]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element SparseVector{MP, Int64} with 2 stored entries:\n",
       "  [1]  =  0\n",
       "  [3]  =  ."
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MP(sparsevec([1, 3], [0, -Inf]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Où en supprimant les zeros:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element SparseVector{MP, Int64} with 1 stored entry:\n",
       "  [1]  =  0"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MP([1, 3], [0, -Inf])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Construction de matrices Max-Plus usuelles\n",
    "\n",
    "### Matrice dense d'identité\n",
    "\n",
    "Par exemple de taille 2 $\\times$ 2 :\n",
    "\n",
    "$$\\left[\n",
    "\\begin{array}{*{20}c}\n",
    "e & \\varepsilon \\\\\n",
    "\\varepsilon & e \\\\\n",
    "\\end{array}\n",
    "\\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Depuis Julia v1.0, la fonction `eye` n'existe plus et a été remplacée par `LinearAlgebra.I` mais cette boite à outils ajoute leur équivalent `eye(MP,...)` et `mpI` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "UniformScaling{Bool}\n",
       "true*I"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "using LinearAlgebra\n",
    "I"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  0   .\n",
       "  .   0\n"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Matrix{MP}(I, 2, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "UniformScaling{MP}\n",
       "0*I"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mpI"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  0   .\n",
       "  .   0\n"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Matrix(mpI, 2, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(true, true)"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Matrix(mpI, 2, 2) == eye(MP,2,2),   Matrix{MP}(I, 2, 2) == eye(MP,2,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `mpeye` reste plus simple à taper :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  0   .\n",
       "  .   0\n"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "J = eye(MP,2,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  0   .\n",
       "  .   0\n"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "J = eye(MP,2) # Equivalent à eye(MP, 2,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Taille 3 $\\times$ 2 :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×2 (max,+) dense matrix:\n",
       "  0   .\n",
       "  .   0\n",
       "  .   .\n"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "J = eye(MP,3,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Construire une matrice identitée (max,+) à partir des dimensions d'une matrice (max,+) existante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  0   .\n",
       "  .   0\n"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = MP([1.0 -Inf; 0.0 4])\n",
    "J = eye(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Matrices/Vecteur colonne denses remplies uniquement de $e$ :\n",
    "\n",
    "Par exemple matrice de taille 2 $\\times$ 2 :\n",
    "\n",
    "$$\\left[\n",
    "\\begin{array}{*{20}c}\n",
    "e & e \\\\\n",
    "e & e \\\\\n",
    "\\end{array}\n",
    "\\right]$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  0   0\n",
       "  0   0\n"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "O = ones(MP,2,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vecteur colonne de 2 éléments:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element (max,+) vector:\n",
       "  0\n",
       "  0\n"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "O = ones(MP,2) # /!\\ N'est pas équivalent à ones(MP,2,2) /!\\"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Construire une matrice de e (max,+) à partir des dimensions d'une matrice (max,+) existante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  0   0\n",
       "  0   0\n"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = MP([1.0 -Inf; 0.0 4])\n",
    "J = ones(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Matrices creuses remplies de $\\varepsilon$ :\n",
    "\n",
    "$$\\left[\n",
    "\\begin{array}{*{20}c}\n",
    "\\varepsilon & \\varepsilon \\\\\n",
    "\\varepsilon & \\varepsilon \\\\\n",
    "\\end{array}\n",
    "\\right]$$\n",
    "\n",
    "**Attention :** Sous Scilab `zeros` va créer une matrice creuse alors que nativement Julia va créer une matrice pleine, il faudra bien penser à appeller `spzeros` à la place pour avoir le même comportement."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Matrice dense"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  .   .\n",
       "  .   .\n"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Z = zeros(MP,2,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×3 (max,+) dense matrix:\n",
       "  .   .   .\n",
       "  .   .   .\n"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Z = zeros(MP,2,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element (max,+) vector:\n",
       "  .\n",
       "  .\n"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Z = zeros(MP,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Matrice creuse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) sparse matrix with 0 stored entries"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Z = spzeros(MP,2,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×3 (max,+) sparse matrix with 0 stored entries"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Z = spzeros(MP,2,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element SparseVector{MP, Int64} with 0 stored entries"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Z = spzeros(MP,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On remarquera que ces matrices sont vides. En effet, elles correspondent aux 0 éliminés des matrices creuses en algèbre classique. Une matrice creuse Max-Plus ne stocke pas les nombres Max-Plus $-\\infty$ (**note:** enfin jusqu'à Julia > 1.9 car les versions précédentes avaient un bogue elles confondaient 0 et `zero(T)` avec `T` template de type `MP`)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Matrices denses remplies de $\\varepsilon$ :\n",
    "\n",
    "Il faut utiliser la fonction `full` ou bien la fonction synonyme `dense`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  .   .\n",
       "  .   .\n"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Z = full(zeros(MP,2,2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Matrices diagonales\n",
    "\n",
    "Dense:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 (max,+) dense matrix:\n",
       "  1   .   .\n",
       "  .   2   .\n",
       "  .   .   3\n"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "diagm(MP([1,2,3]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Creuse:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 (max,+) sparse matrix with 3 stored entries:\n",
       "  [1, 1]  =  1\n",
       "  [2, 2]  =  2\n",
       "  [3, 3]  =  3"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "spdiagm(MP([1,2,3]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Opérateur éléments par éléments sur les matrices\n",
    "\n",
    "Julia permet d'itérer sur les éléments d'un tableau, matrice, vecteur et appliquer une opération sur chacun d'eux. Par exemple :\n",
    "\n",
    "$$4 \\oplus \\left[\n",
    "\\begin{array}{*{20}c}\n",
    "2 \\\\\n",
    "8\\\\\n",
    "\\end{array}\n",
    "\\right] = \\left[\n",
    "\\begin{array}{*{20}c}\n",
    "4 \\oplus 2 \\\\\n",
    "4 \\oplus 8\\\\\n",
    "\\end{array}\n",
    "\\right] = \\left[\n",
    "\\begin{array}{*{20}c}\n",
    "4 \\\\\n",
    "8\\\\\n",
    "\\end{array}\n",
    "\\right]$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  1   2\n",
       "  3   4\n"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = MP([1.0 2; 3 4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On applique la fonction max(2, ) sur chacun des éléments qui seront contaminés en nombre Max-Plus :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  2   2\n",
       "  3   4\n"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 .+ A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  2   2\n",
       "  3   4\n"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A .+ 2.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On applique la fonction +(2, ) sur chacun des éléments "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  3   4\n",
       "  5   6\n"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 .* A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  3   4\n",
       "  5   6\n"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A .* 2.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Addition et produit matriciel\n",
    "\n",
    "Les matrices peuvent être de type Max-Plus. L'addition et le produit matriciel Max-Plus correspond à l'addition et au produit matriciel avec les opérateurs $+$ et $\\times$ surchargés.\n",
    "\n",
    "### Addition matricielle\n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "1 & 6 \\\\\n",
    "8 & 3\n",
    "\\end{bmatrix} \\oplus \\begin{bmatrix}\n",
    "2 & 5 \\\\\n",
    "3 & 3\n",
    "\\end{bmatrix} = \\begin{bmatrix}\n",
    "1 \\oplus 2 & 6 \\oplus 5 \\\\\n",
    "8 \\oplus 3 & 3 \\oplus 3\n",
    "\\end{bmatrix} = \\begin{bmatrix}\n",
    "2 & 6 \\\\\n",
    "8 & 3\n",
    "\\end{bmatrix}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  2   6\n",
       "  8   3\n"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MP([1 6; 8 3]) + MP([2 5; 3 3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Produit matriciel\n",
    "\n",
    "$$A=\\begin{bmatrix}\n",
    "4 & 3 \\\\\n",
    "7 & -\\infty\n",
    "\\end{bmatrix}\\;,$$\n",
    "\n",
    "$$A \\otimes A = \\begin{bmatrix}\n",
    "4 \\otimes 4 \\oplus 3 \\otimes7 & 4 \\otimes 3 \\oplus 3 \\otimes -\\infty \\\\\n",
    "7 \\otimes 4 \\oplus -\\infty \\otimes 7 & 7 \\otimes 3 \\oplus -\\infty \\otimes -\\infty\n",
    "\\end{bmatrix}\\; = \\begin{bmatrix}\n",
    "10 & 7 \\\\\n",
    "11 & 10\n",
    "\\end{bmatrix}\\; = A^2.$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  10    7\n",
       "  11   10\n"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = MP([4 3; 7 -Inf])\n",
    "A * A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A * A == A^2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fonctionne également sur les matrices creuses :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) sparse matrix with 3 stored entries:\n",
       "  [1, 1]  =  4\n",
       "  [2, 1]  =  7\n",
       "  [1, 2]  =  3"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = MP([4 3; 7 -Inf])\n",
    "sparse(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A * sparse(A) == sparse(A) * A == sparse(A) * sparse(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Puissance d'une matrice Max-Pus :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  24   23\n",
       "  27   24\n"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A^5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "  0   .\n",
       "  .   0\n"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A^0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "S'applique également aux matrices rectangulaires compatibles :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element (max,+) vector:\n",
       "   8\n",
       "  13\n"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MP([2 0; mp0 5]) * MP([2; 8])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1×2 (max,+) dense matrix:\n",
       "  4   13\n"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MP([2 8]) * MP([2 0; mp0 5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vérifions que la matrice identité $I$ est bien neutre :\n",
    "\n",
    "$$ A \\otimes I = I \\otimes A = A$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = MP([4 3; 7 -Inf])\n",
    "A * eye(MP, 2,2) == eye(MP, 2,2) * A == A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vérifions la matrice zéro est bien absorbante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A * zeros(MP, 2,2) == zeros(MP, 2,2) * A == zeros(MP, 2,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A + zeros(MP, 2,2) == zeros(MP, 2,2) + A == A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Affichage des matrices Max-Plus en LaTeX"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A partir d'une matrice Max-Plus, on peut générer le code $\\LaTeX$ grâce à la fonction `LaTeX` ou via la fonction `show` avec l'argument `MIME\"text/latex\"`. La fonction `set_tropical_display` modifie en conséquence les éléments neutres et absorbants du code LaTeX généré."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I will show -Inf, +Inf and 0.0"
     ]
    }
   ],
   "source": [
    "set_tropical_display(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\\left[\n",
      "\\begin{array}{*{20}c}\n",
      "0 & -\\infty \\\\\n",
      "-\\infty & 0 \\\\\n",
      "\\end{array}\n",
      "\\right]\n"
     ]
    }
   ],
   "source": [
    "LaTeX(stdout, eye(MP, 2,2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une fois ce code $\\LaTeX$ compilé, il affichera :\n",
    "\n",
    "$$\\left[\n",
    "\\begin{array}{*{20}c}\n",
    "0 & -\\infty \\\\\n",
    "-\\infty & 0 \\\\\n",
    "\\end{array}\n",
    "\\right]$$\n",
    "\n",
    "Alors que :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I will show (max,+) -Inf and (min,+) +Inf as . and 0.0 as e"
     ]
    }
   ],
   "source": [
    "set_tropical_display(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\\left[\n",
      "\\begin{array}{*{20}c}\n",
      "e & . \\\\\n",
      ". & e \\\\\n",
      "\\end{array}\n",
      "\\right]\n"
     ]
    }
   ],
   "source": [
    "LaTeX(stdout, eye(MP, 2,2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une fois ce code $\\LaTeX$ compilé, il affichera :\n",
    "\n",
    "$$\\left[\n",
    "\\begin{array}{*{20}c}\n",
    "e & . \\\\\n",
    ". & e \\\\\n",
    "\\end{array}\n",
    "\\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fonctionne avec les matrices creuses :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I will show (max,+) -Inf and (min,+) +Inf as ."
     ]
    }
   ],
   "source": [
    "set_tropical_display(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\\left[\n",
      "\\begin{array}{*{20}c}\n",
      ". & . \\\\\n",
      ". & . \\\\\n",
      "\\end{array}\n",
      "\\right]\n"
     ]
    }
   ],
   "source": [
    "LaTeX(stdout, zeros(MP, 2,2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une fois ce code $\\LaTeX$ compilé, il affichera :\n",
    "\n",
    "$$\\left[\n",
    "\\begin{array}{*{20}c}\n",
    ". & . \\\\\n",
    ". & . \\\\\n",
    "\\end{array}\n",
    "\\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Trace d'une matrice Max-Plus\n",
    "\n",
    "Cette boîte à outil utilise `using LinearAlgebra` pour corriger quelques fonctions tels que trace et norme.\n",
    "La trace est la somme Max-Plus des éléments diagonaux."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) 4"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = MP([4 3; 7 -Inf])\n",
    "tr(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tr(A) == A[1,1] + A[2,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 (max,+) dense matrix:\n",
       "   5    .    5\n",
       "   .    6    3\n",
       "  11   12   11\n"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = [5 mp0 5; mp0 6 3; 11 12 11]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) 11"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tr(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tr(A) == A[1,1] + A[2,2] + A[3,3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Norme d'une matrice\n",
    "\n",
    "Elle est définie comme la différence entre le plus grand et le moins grand coéfficient de la matrice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) Inf"
      ]
     },
     "execution_count": 115,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "norm(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) Inf"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "norm(eye(MP, 2,2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Résiduation d'une matrice Max-Plus\n",
    "\n",
    "Elle permet de calculer la plus grande sous solution de $Ax\\leq b$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Valeurs propres d'une matrice Max-Plus $A v = \\lambda v$\n",
    "\n",
    "Le spectre d'une matrice est l'ensemble de ses valeurs propres. Une matrice carrée $A \\in \\mathbb{R}_{\\varepsilon}^{n \\times n}$ a une valeur propre s'il existe un nombre réel $\\lambda \\in \\mathbb{R}^{n}$ et un vecteur $v \\in \\mathbb{R}_{\\varepsilon}^{n}$ si :\n",
    "\n",
    "$$A v = \\lambda v$$\n",
    "\n",
    "$v$ est appelé vecteur propre et $\\lambda$ valeur propre."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(MP[4.5, 4.5], MP[6.5, 4])"
      ]
     },
     "execution_count": 117,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = MP([3.0 7; 2 4])\n",
    "λ,v = mpeigen(S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S * v == λ[1] * v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S * v == λ[2] * v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ces éléments spectraux donnent le comportement asymptotique des systèmes dynamiques linéaires Max-Plus $x_n=A\\otimes x_{n-1}$ qui croissent linéairement à une vitesse donnée par la valeur propre qui est unique dès que le graphe d'adjacence de la matrice est fortement connexe :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element (max,+) vector:\n",
       "  1\n",
       "  0\n"
      ]
     },
     "execution_count": 120,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = MP([1; 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×4 (max,+) dense matrix:\n",
       "  1   7   11   16\n",
       "  0   4    9   13\n"
      ]
     },
     "execution_count": 121,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[x S*x S^2*x S^3*x]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans la boite à outils Max-Plus de Scilab, ils sont obtenus soit par les fonctions `karp` ou `howard`. Dans cette boite à outils Julia seul `howard` est implémenté car son algorithme est plus rapide (linéaire au nombre d'arcs) que l'algorithme de `karp` ($O(mn)$)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  0.005516 seconds (45 allocations: 23.031 KiB, 99.47% compilation time)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "MaxPlus.HowardResult(MP[0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001  …  0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001], MP[0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001  …  0.001, 0.001, 0.001, 0.001, 0.8351598122069036, 0.001, 0.001, 0.001, 0.001, 0.001], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10  …  91, 92, 93, 94, 90, 96, 97, 98, 99, 100], 92, 1)"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# FIXME Matrice 10000x10000 => Max iteration reached\n",
    "S = MP(sprand(100,100,0.0005))+0.001*sparse(eye(MP, 100,100))\n",
    "@time howard(S)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `mpeigen()` se base sur `howard` et ne retourne que les valeurs et vecteurs propres. La fonction `howard` retourne plus d'informations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "MaxPlus.HowardResult(MP[4.5, 4.5], MP[6.5, 4], [2, 1], 1, 2)"
      ]
     },
     "execution_count": 123,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = MP([3.0 7; 2 4])\n",
    "r = howard(sparse(S))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le graphe correspondant la matrice `S` est:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAASsAAACNCAIAAABg9MukAAAAA3NCSVQICAjb4U/gAAAAGXRFWHRTb2Z0d2FyZQBnbm9tZS1zY3JlZW5zaG907wO/PgAAH3pJREFUeJzt3Xs8VOnjB/AjGRqXTMbImEHuQ1ghUklIJUpFd923y3bRZb+727Zlv7p8v21t1rcU2u4JoZpUm3Jt04XRhKimXEpC4zIYjLmd3+vnvNarVxcxM8eZGc/7j17jOOd5HqfXZ871eR4VGIYhAAAwMgSrigEAAAkEAIyBYyAAYAkkEACwBBIIAFgCCQQALIEEAgCWQAIBAEsggQCAJZBAAMASSCAAYAkkEACwBBIIAFgCCQQALIEEAgCWQAIBAEsggQCAJZBAAMASSCCg8Nhs9pIlSyDFJO8JFIvFcXFxs2fPDg0NLSgowLo5gDz69ttvc3NzIcUk7wn86aef2traVqxYUV9f7+3tXVdXh3WLAPly8uRJKpUKKayhkByrra319fX18/ODIGjMmDEmJiYsFmvkyJFYtwuQFywWq6mpyd3d/erVq/3dViQSlZSUPHz4sLq6uqGhQVdX18TExMvLy9bWFlK4BPL5/JSUlMzMzKdPn3K53GHDhlGpVGdn58mTJ7u7u6uqqkpWrGE35LO6urqRkZGrq6tMGgwoAYFAENUtKSmpXxvm5+efPXv20qVLJBJp/PjxJiYmzs7OLS0tTCbz4MGDZDJ5z5493t7e0MCApZaYmEihUKZNm3bs2LGHDx+WlZUVFBSkpKR8//33Tk5OFApl586d7969k6aKjo6OBQsWMBgM6VsLKI19+/axWCwYhi9cuEChUPqySUZGhpeXl5mZ2f79+9+8efPpCiKRKDk5mUqlhoeHwwNC2gRu27bN2to6Pz//Sys8ffo0LCxMT09v8+bN79+/l6AKJpMZEBCgqqpKIBBKSkqkay+gJO7evXvixAnkc18S+OrVq5kzZ1pZWV24cEEgEPS+8vv3711cXPbu3QvLeQL/85//ODs7t7a2fnXN+vr6LVu2kEik48ePi0QiCerKzc0lEokhISEStRRQNpMmTZo7d25wN1dX12HDhgUHB1+6dOnTNUUiUWRkJJFI/O9//9vV1dXH8mtraykUyr1792CUqUg8an1paam3t/eTJ096LtW+qqSkZP369Tgc7ty5cxQKpb81/vzzzzdv3nzy5En/Gwsom/T0dA6Hg3y+f//+hQsXjh07Nnr0aDs7uw9Xq62tXbx4sUAgOHv2rJmZWb+qSEhIiIyMzM/Ph1AlcXYDAwOjo6P7u5VQKNy3b5+BgcH169f7u218fPy8efP6uxWg9BK770R8uvzBgwcUCiUiIkIoFEpQrFgstra2fvDgAYwmCRP4+vVrIpHY0dEh2ebIrjlw4EDvqwkEgqqqqp4fV69e3csFJzBoJX4ugfHx8QYGBjdu3JCm5AMHDnz33XewHCbw8OHDa9askabit2/furq6rly5spfvJxaLhcPh/Pz8Tpw4cfz48ezsbGlqBAaP33//3cTEpLS0VMpymEymra0tLIfXgTNnzgwNDQ0JCZHmBLijo2Pu3Ll4PP7ixYvq6uqfXYfL5VZWVpqYmOjo6EhTFzB47N69+/Lly7du3ZLgXsNHRCIRgUCorq4ePnw4JFdvpT1+/NjNzU3KuvF4PJ1OV1NTmz17dldX12fX0dLSsre3B/ED+igiIuLKlSvZ2dnSxw+CIFVVVVNT09evX0OokSSBPB6vsbFRJn8hDoeLj4/X0tKaP3++QCCQvkBgMDt06NClS5cyMzP19fVlVSaFQnn79i0kVwmsr68nkUhDhsjmrW5VVdX4+HgYhlesWAEm9AUkFh8fHx0dffv2bRKJBMkOHo/v7OyEUCNJijo7O/F4vAwboaamlpSUVFlZuWvXLhkWCwweWVlZ27dvv3HjBplMlm3JampqqJ6dSZJAPp+Pw+Fk2w4NDQ06nZ6UlHTmzBnZlgwovcrKysWLFycmJqLRraGzs3PYsGGQXPWN0NTUbG9vl3lTiETi9evXPT09R48e7eLiIvPyAaXU0dExZ86cn3/+2cvLC43yORwOgUCA5OoYOHz48NbWVhQaA1lbW8fExISEhDQ2NqJRPqB8NmzY4OjouGnTJpTKr6+vJxKJKBUOQZAkzwPFYrGmpiaHw/nSQzwp/fjjj2VlZdeuXVNRUUGjfEBpJCQkREREMBgMTU1NNMoXiUTa2tpNTU0aGhpydAwcMmQIhUJ58+YNhI69e/fW1dXFxsaiVD6gHCorK7ds2ZKQkIBS/CAIevPmjb6+Pnrxk/yJvJmZ2atXryB0qKmpXbhwYffu3SwWC6UqAEUHd78n/K9//eubb75BrxYmk+no6Ihe+ZIn0NHREdVeQtbW1rt37161apVYLEavFkBxnTx5ksvlbt26FdVaCgoK0B4YRcIEjhkzprCwEELTd999JxKJTpw4gWotgCKqra3duXPnn3/+KfEQRH304MED6d++7J2Eb2ZXVFRMnDixpqYGQtPTp0+9vb2Li4vB+GjAh9asWUMgEA4cOAChicvlksnkuro62b5/IrPrQBwO9+zZMwhNo0ePXrFixe7du1GtBVAsFRUVdDp9x44daFeUnZ3t5uaGavykGrHXx8cnMzMTQtmOHTvodDraUQcUyLFjx1asWKGrq4t2RWlpadOnT0e7FsnHibl8+XJMTMzt27chlEVGRt6/fz85ORntigD5JxKJDA0NHz16NGrUKFQrEgqFZDK5oKDAxMRETo+B06ZNy8/Pb2pqglC2du3au3fvovfwA1AgeXl5VCoV7fghp6Dm5uZox0+qMbPxeLyvry+dTl+xYoVMm/SZitauXRsZGRkdHQ0pHbFYXF9f//79ey6X297e3tLS0tbW1tHR0d7e3tzc/OGaOBwOefQ8dOhQbW1tHR0dfDcCgaCtrU0mk7W0tCBlR6fTZ82aNQAVnTlzZtGiRQNQkeRnoRAEXblyJSoqKicnB0JZfX09jUarrKxEb7AAtHG5XBaL9eLFi5cvX9bU1NR2e/fuHZvN1tPTI5FIWlpampqaurq6yAfk84fv5fH5fOSFeIFAwOVyW1paOrpxOJyWlpba2loYhkd209fXNzIyMjExMf+HtrY2pBQsLCxSU1PRfkre2NhoaWlZXl6O6jvZMkigQCCgUql5eXnm5uYQyoKDg6dPn75q1SpIEfB4vKKiIgaD8fTpU1a3pqYmq38YGRmRyeSRI0caGRkZGBgMHSqb2Tva29vrurHZ7JqamqqqqvJuFRUVeDzezMyMRqM5dPvmm29GjBgBKZqXL1/6+Pig9zpkj8OHDxcVFZ09exbtiqRNIARB27dvV1dX379/P4QyOp1++PBhuZ0mTiwWFxUV5efnM7qxWCwbGxtnZ2dHR0dra2srKysqlYrhi+b19fXl5eWlpaXF/9DS0nJwcBgzZoyHh8e4ceMG4Nai9M6fP3/jxo3ExERUaxEKhZaWlklJSWPHjoXkP4Hl5eUeHh5VVVWo9mJEjrdGRkb5+fmmpqaQ3CgrK8vKysrOzs7JyRk5cqSbm5tLN0dHR5Q6jshKVVVVcXExg8HIy8tjMBjGxsYeHh7jx4/39PSUqz38oY0bN5qbm6P9JlpSUtKxY8cG7Lte2gRCEBQUFOTv779mzRoIZStXrnR2dt6wYQOEKS6Xe+vWLTqdnpmZqaGh4d1t8uTJfR+9v+8OHTr0UVfJn376SeYXw0KhsLi4OC8v7/79+9nZ2bq6ulOnTp02bdqkSZPQfh7dL66urlFRUR4eHhBqYBh2dXUNDw8PDAyEFCWBubm5a9euLS0tRfslvUuXLp0/fz4tLQ3CApvNTktLu3Llyt27dz08PIKCgvz8/FC9Lf7s2bMpU6Z4eHggh1MOh1NUVIT2VRAMw0+ePLl9+3Z6enphYaGbm9vMmTPnzJkj8/FX+qurq0tPT4/NZqN6tkWn0//9738XFhYO3CWDTMb99fT0RMY7Q1VTU5OOjg6Px4MHEJfLPXv2rLe3t66u7rx58y5evMjhcAam6jNnzrS1tfX8GBcXt2XLFngAtbW10en05cuX6+npTZgwISoqqrq6GsZIcXEx2sNXi0QiR0dHKQe67y/ZJDAjI8PGxkay+TH6Zdy4cbm5uWjXgszacffu3ZUrVxIIhICAgJSUlM7OThhTU6ZM+fvvvzGpms/n37x5c+XKlUQicfz48SdPnvzwq2FgpKSkBAUFoVrF+fPnx48fDw8s2SQQhuGJEyeePn0aRtnGjRsjIyNRrYLD4Rw6dMjCwsLOzu7gwYPIczbMsdlsCoUi2dSLMsTn869fvz579uwRI0asXr36/v37A1b1vn37fvzxR/TK53K5VCp1IP8iGSewsLDQ0NCwL7N5SuPkyZNLly5FqfCXL19u2rRpxIgRixYtevjwISxP4uLi1q9fD8uNurq63377zdra2s7OLiYmRuJZtPouNDQU1a/4X375JTQ0FB5wMksgDMOLFy/etWsXjKbHjx+PHj1a5sXeu3cvMDCQRCL9/PPPNTU1sPyZMmVKRkYGLH9ycnJmzZpFIpF2795dV1eHXkUTJ05E7wLk1atXRCLx7du3sEIn8M2bN0Qi8cWLFzBqOjs71dXVxWKxrAp8+PDh1KlTR40aFRsbOwBf5JJpaGgwMDD46uznGGKxWOvXr0dOTcvLy9GowsLCgsVioVGyWCyePHny4cOHYSzIMoEwDB89enTcuHF8Ph9GzYgRI9hstvTlFBYWBgQEGBsbx8bGotpg6Z04cWLlypWw3GtoaPj111+JROLatWtlftdUS0sLpWucmJgYd3f3AbiPOBAJFIvFAQEBmzZtglFjZ2dXUlIiTQnV1dULFy6kUChHjx4d4GcbkvHz8xvgW+TSaGxs/Omnn/T09MLCwurr62VSZmtrq6amJoyCiooKfX196ef6lJcEIvcSbWxs/vjjDxgdPj4+d+7ckWzbzs7Offv2EYnE8PDw9vZ2WBE0NDTo6el1dXXBCqWuri4sLIxIJB48eFD6UwwWi2VhYQHLGp/Pd3d3R/vu+kAnELkgHDVqVFxcHBqFz507NyUlRYIN6XS6mZnZ3LlzKysrYcXB4/HevXsHK6aXL1/OmDGDRqNJ/KWJyM3NnTBhAixrP/zwQ0BAgAxvK8hLAmEYLi8vp1Kp58+fl3nJQUFBV65c6dcmDQ0N8+fPt7GxyczMlHl7gK+6du0a8t0n8X3mpKSkkJAQ2e7q1NRUY2NjmdxTkIZsZuH8lJmZ2e3bt3/88UeZz0YmFAr71aGOTqc7ODhQqVQmk+nt7S3bxgB9ERgYWFpaamdnN2bMmISEBAl2Wl1dnWxHrGQwGOvXr7969Sqqs7L0Car5fv78uZmZ2d69e2VY5vTp02/evNmXNTkcTmhoqKWl5b1792TYAEBiDAbD1tZ23rx5DQ0N/dpwz549v/zyi6z2fFVVFYVCodPpsBxA6xiIsLa2zsvLu3z58vr160UikUzK5HK5fZmpo6ioyMXFRVtb+8mTJ+PHj5dJ1YCUnJ2dCwsLqVSqo6Njv4a65Hb/p/P5/OjoaCkHB6uurvbx8dmxY8fMmTMheTAAKW9tbfXz8wsICGhpaZG+NCMjozdv3vS+zunTp/X19RMSEqSvDkBDVlYWmUz+7bffer8LUlFRkZuby2AwQkNDFy5caGxsjMPhpHlwV11dbWFhgd6NegkMRAKR274bN260sbF5/vy5NOV0dHQMGzaslxeUeTze6tWraTRaWVmZNBUBaKuurnZzcwsJCemlm0VVVVXP+Y6BgQEEQVZWVhLXWFJSYmpqiu2zB8wSiLhw4QKJRLp8+bLEJZSWltJotC/9trm52cvLKzg4eOD7zgAS4PF4a9assbOze/369ZfW6Zkcwt3dHRmlVrJdfefOHRKJhMbNeUVKIAzDjx49olKpO3bskOwpbU1NzdmzZz/7q+rqant7+y1btmDehQfol6ioKGNj4y+9lSIQCJycnCAImjRpEjJndX93r1gsPnjwoKGhYV5enhz+10CYdHULDAx0cXGR/kXbngvL0tJSExOT8PBwWTQQGGjx8fEGBgZfSkh+fr6qqqqDgwMycE6/Sn7//r2/v7+bm1tFRQUslzBIIPK1dOTIkU/PCvp1kX3t2rXNmzcj4xeMHDny4sWLKLQUGCA3b94kkUhZWVmf/e2GDRs0NDRwOFy/LmFSUlLIZPKuXbvkuVsJNglEFBUV2draLlmypOdQ9sMPP/TxrWuxWPzNN9/gcLj09HQymXzp0iWUGwugLjc3l0Qi5efnf/qrlpYWCoVCo9GePHnSl6KqqqoCAgLs7Ozk/1EwlglE7m2uW7fO3Nz8wYMHXV1d+vr6Y8aM6cslYlJSEnKBrqWlJYeX14Bkbt++TSaTP3tNmJqa6unp+dUHWu3t7cjL9/v27ZPzTmdykUDE5cuXDQ0NZ8yYgYQqIiKi9/WFQiGNRoMgSFVV1cDAYNKkSVI+5ADkx/nz542NjT97d3Tnzp29bCgQCOLi4oyMjObPn49SL2GlTSByj5RMJiMjjqqpqTGZzF5WPnXqFDKXkI6ODhJaPB6fmJg4gO0FUHTw4EFXV9dPu272PojBvHnzvL29CwoKFOv/Ri4SeOvWLWSSGm1tbRcXFwiCbG1tvzQ6IJ/PNzMz09HR0dDQ+P8JEIcM8fX1vXTpksSvShQXF0dERCA3dfqOyWQeOHAAHqz6u9NEItGxY8dmz569cuVKBoPx1fVDQkLWrVvXryY1NTXBCgj7BDY0NISEhPQczVRUVHx9ffF4/I4dOz67/tGjR6lUqqqqqo6Ozpo1a6R/96WpqWnKlCleXl59XJ/D4cTHxxsaGvZ9E+XT35327bffbt++PSIiwtraeujQoV8diq61tdXa2nowXOFjn0CEUChkMBjh4eHOzs4qKirm5ubW1tafDlDb2dk5ffp0e3v7PXv2cLlcWdW+bt26/sZpxYoVgzmB/dpp+fn5Pc+KWlpaRo4c2ZchJ0tKSk6dOgUrO9nMXCc9VVVV526//vprfX19erfjx487OTl92BOCxWLt3Lnzs30dOjo6amtrTU1NCwsLdXR0bGxsen7V2dlZXFysoqLi4OCAnLsieDxeQUHBpx3Pmpubnzx5QqFQLC0te2kwpPgGZqdpaGgsWLAA+ayjozN+/HgOh/PVto3uhnQeQE6OIGWEbu8kyRgYGCxdujQ+Pv7UqVNisfjDXzk4OHw2funp6VQqdefOnRs2bNi3b5+Dg8O1a9eQX/31119r1qwZOnQo0kk0OzsbWX7v3r2lS5ficLhbt271rIzMD/P777+/ffs2KCho8+bNkPIasJ1mb2//YX7YbLavr29fWlhfX79w4UICgTBixIjQ0FA2mw0pH1gRcLlcJpPZ+5QpEyZM8PX1Rd5+8Pb2njt3LjJekK6ubs84KwcOHCASiY2NjW1tbWQyuaeXk7+/P3JCVVlZOXHiRGRhamoqBEGPHz/+bHWrV69WgrPQAd5pyLNya2vrvgzN2tXVhbyJ1sPJyUkhHvH1izweAz8Ew3B4eLiurq6TkxOBQNi8eTOfz//smhoaGqampsgAFpaWlsi0ezdv3lRVVe2Z2W/BggUNDQ05OTmpqanDhg2jUqnIcmNjY+TDjRs3eDzerm4FBQXr1q3j8XiQ8hrgnSYWi8PCwpKTk/syA9n169eLi4s/XMJkMtPT0yHlIi/XgV8SExMTERGBfIZh+MiRI7q6uj1LvqTnnKempgYZ5hVZQqFQhg4dWldXV11draam9umGLBbLyspqz5490OAzADstKipq69at9vb2fWnPy5cv+7hQocn7MfDPP//8aMmJEyf6vrmlpaVAIHj+/Dnyo0AgEAqFdnZ2BALh9evX7e3tH61PIpGys7M//Ap/9OgRNMigtNNSUlJsbW2RTkbIhKRQr+zs7Pq4UKHJewLfv3//0ZLGxkahUPjpmsgVAvJZIBAgw9LMnDnT1NT09OnTyPLc3Fx3d3dPT09/f/+uri6k96dYLH79+jUy+khAQEBtbe2yZcvq6uoaGhr279//pYYJBIKP7hIpogHbaWlpacXFxUQisbCwkMFgxMbGFhQU9N626dOnfzRhtZeXVx9v4SgSWL4FBwd/1GAPD49PV8vKyho+fLiVlVV+fn5BQYGZmdnw4cORri7Pnj0bN25ceHj4uXPnvv32254bDHFxcZqami4uLgEBATNmzHB1dU1KSkKe+OPxeBUVFUNDw9TU1E/r4vF4V69epVKpeDz+6tWrzc3NsGIasJ32999/f/g8A7mG7EtH6tbW1s2bN5ubm1tYWGzbtk2GT4DlhwzmkUdVeXm5m5sbcocAgiBNTc2cnBzkzbV+aW5uVlNT09LS+nChUChks9mGhoYdHR14PP7D5XV1dWQyecgQeT9HQBWGOw3unqnO2dkZUnbynkAIgmprayMjI0tLSy0sLMLCwszMzLBuEYAufve4XnZ2dmFhYUq/rxUggcCg0tzcPGfOHBiGt2/fHhgYCCk7kEBAjlRWVs6YMeP9+/ccDuf58+cWFhaQslPI65zS0lIul4t1KwAZKygoGDdu3LNnz1pbW1VVVUeNGjUYdrFCJjA6OnrVqlXg/FmZ0Ol0Ly+v+vp6XV1dgUBga2urHO++K2cCIyMjq6qqDh06hHVDANmIi4sLDg7u6OhAumtAEISMQjIYKGQC1dXVU1NT//jjj4yMDKzbAsiAr69vTEzMrFmzcDgc8t4vSKC8o1AoiYmJS5Ys+eqrFYD8MzMzmzdv3qtXr/bv3+/o6IgMUwINDgp5DERMnDjx3LlzgYGBTCYT67YAUoFheNWqVZ6entu3b8/JyXFzcxs8CVT4pxHJyclbt27NysqysrLCui2AhMLCwphMZkZGBg6HgyCopaUFj8d/th+G8pH33klfFRIS0t7e7u3tnZaWhkzxASiW77///sGDB3fu3EHiB0HQ8OHDoUFDgc9Ceyxfvjw6Onrq1Kl//fUX1m0B+mfnzp2ZmZm3bt0aVKlTqrPQHvfu3QsODj506NCSJUuwbgvwdcg0IXfu3MnMzNTT0xu0u0x5EghBUFlZ2YwZM0JCQvbv34+MvADIp87OzmXLltXX11+5cmXEiBHQIKYMZ6E9bG1tGQzG06dPvb293717h3VzgM9rbGz08/NTUVFJT08f5PFTtgRCEKSnp3f9+vUpU6aMHTs2JycH6+YAH2MymWPHjvX19U1MTPyo2+4gBSupjIwMIyOjLVu2tLe3w4qvv/MuyCGxWBwZGUkikcBkjx9StmNgDx8fn6dPn3Z0dNjb2/cMOKu41q1bV15e7uTklJeX5+7urnDjRyFTlyckJNy/fz8kJATr5sgTWNldu3bNyMho06ZNvQ/4K88km3dBfqSmphoZGf3yyy/yPJs0VpT2GNgjMDCwpKSkq6vLxsYmLi4OGQ5MsUg274I8qKqqCgwM3L17d1JS0p49e8AN6k8pfwIhCCIQCLGxsVlZWZcvX7a3t1e4cZclnncBQ0KhMCoqauzYsc7OzoWFhZ+d7QP4f/Agk5ycbGpqGhAQoHCTrfZ33gWsiMXi5ORkGxsbf3//iooKrJsj7wZdApEpQWJjYykUiq+v76NHj2DFIRKJZs2aVVxcDMurO3fuuLi42NvbgxuefTQYE4jg8XjR0dFUKjUgICA7OxtWBIcPH87JyYHlUlZW1qRJk2g0WkpKilgsxro5CmPwJhDB4/FiYmJoNJqjo+PJkye/NHm9PEhOTr5161bPj3IyVjefz4+Pjx8zZgyNRjtz5oxQKMS6RQpGqd4LlRhy+vS///2voKBg9erVq1atkrdxgdPS0goKCmbNmoW0trCw0MzMbMqUKRg2icPhnDhx4siRI1ZWVtu2bZs+fbqyTnOLLqy/AuQLi8UKCwvT19f39PQ8efJkS0sLLAcknncBDSKRKD09fdGiRbq6uqGhoUwmE5NmKA1wDPwMgUBw8+bNs2fPZmdnz5gxY+HChT4+PuAlxhcvXpzrZmhouGzZskWLFhEIBJQPEMoPJLA3jY2NCQkJKSkpRUVFfn5+QUFB/v7+g60v6ePHj69evUqn09ls9uLFi5cvX658k/hhCCSwT9hsdlpa2pUrV+7evTtu3Dg/Pz8fHx8HBwdlvfLp7Oy8f//+tWvX6HQ6DoebPXv2rFmz3N3dB/lkUmgACewfLpd7+/btjIyMzMxMDofj7e3t4+MzefJkc3NzSMHx+fz8/PysrKzs7GwGg+Ho6Ojv7x8UFDR4hi3DBEig5KqrqzO75ebm8ni8sWPHurm5je2mKBdIVVVVyKS2yCSeNjY2k7tNmDDho2kDAZSABMrGu3fv8vPzHz169PDhw8LCQgMDg9GjR9NoNORfGo0mDzdyWlpaWN3KysoeP37MYDDU1dWdnZ1dunl4eAy2S1x5ABIoeyKR6OXLl6WlpWVlZci/r169IpPJo0aNMulm2s3ExMTAwEBdXV3mDWhpaampqXn3j4qKChaL9fz58/b2dqtuNBrNycnJxcXF0NBQ5rUD/QISOBCEQmFFRUVlZeWbN29ed6vqxmazcTicnp6evr4+kUjU09MjEAh4PH7YsGEaGhp4PF5dXV1TUxMZSLO5ufnDMrlcbmu3tra2lpYWDofT2tra3Nz89u1bVVVVCoViaGhoZGSEJB8JnpGR0YD8uUA/gARirK2traGhgc1mNzY2NjQ0NDc3d3bj8XgdHR1dXV3t7e3IZCYfXVtqaWlpa2vr6Ohoa2vr6uoOHz5cW1ubQCBQqVRNTU3s/iCgf0ACAQBL4PEOAGAJJBAAsAQSCABYAgkEACyBBAIAlkACAQBLIIEAgCWQQADAEkggAGAJJBAAsAQSCABYAgkEAAhD/wdLj+HwYUYeUwAAAABJRU5ErkJggg=="
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "using IJulia\n",
    "IJulia.display(\"image/png\", read(\"graph.png\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La dimension de la matrice `S` est $2 \\times 2$ car deux noeuds. Les arcs $i \\rightarrow j$ sont décrits par les élements de `S[j,i]`. L'ordre est inversé afin de garder le produit matriciel `S . x` avec `x` un vecteur colonne. \n",
    "\n",
    "On notera que les packages Julia GraphPlot.jl ne n'affiche pas correctement ce genre de matrice est que SimpleWeightedGraphs.jl ne prend pas une matrice (max,+). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Arc $2 \\rightarrow 1$ avec la valeur MP(7):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) 7"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S[1,2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Valeurs propres:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element (max,+) vector:\n",
       "  4.5\n",
       "  4.5\n"
      ]
     },
     "execution_count": 126,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r.eigenvalues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vecteur propre:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element (max,+) vector:\n",
       "  6.5\n",
       "    4\n"
      ]
     },
     "execution_count": 127,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r.eigenvectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nombre de composants connectés trouvés (un seul ne sera retourné):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 128,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r.components"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La liste des noeuds issue de la politique de saturation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element Vector{Int64}:\n",
       " 2\n",
       " 1"
      ]
     },
     "execution_count": 129,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r.policy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Résolution d'équations linéaires Max-Plus $A \\otimes x = b$\n",
    "\n",
    "Soit $A \\in \\mathbb{R}_{\\varepsilon}^{n \\times n}$ une matrice Max-plus carrée et $b \\in \\mathbb{R}_{\\varepsilon}^{n}$ un vecteur colonne. La solution de $A \\otimes x = b$ est donnée par :\n",
    "$$x = A^{-1} \\otimes b$$\n",
    "\n",
    "L'inverse de $A$ peut être donné par les fonctions Julia `inv` ou `^-1` et si la matrice n'est pas inversible alors une erreur Julia est levée :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 (max,+) dense matrix:\n",
       "  .   1   .\n",
       "  2   .   .\n",
       "  .   .   3\n"
      ]
     },
     "execution_count": 130,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = [mp0 1 mp0; 2 mp0 mp0; mp0 mp0 3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 (max,+) dense matrix:\n",
       "   .   -2    .\n",
       "  -1    .    .\n",
       "   .    .   -3\n"
      ]
     },
     "execution_count": 131,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inv(A)   # Ou bien A^-1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vérifions que leur produit donne bien la matrice identité :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 (max,+) dense matrix:\n",
       "  0   .   .\n",
       "  .   0   .\n",
       "  .   .   0\n"
      ]
     },
     "execution_count": 132,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A * inv(A)   # Ou bien inv(A) * A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculons $x = A^{-1} \\otimes b$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 (max,+) dense matrix:\n",
       "  3   .   .\n",
       "  .   .   4\n",
       "  .   5   .\n"
      ]
     },
     "execution_count": 133,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "B = [3 mp0 mp0; mp0 mp0 4; mp0 5 mp0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 (max,+) dense matrix:\n",
       "  .   .   2\n",
       "  2   .   .\n",
       "  .   2   .\n"
      ]
     },
     "execution_count": 134,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = A \\ B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 135,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A * x == B"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Résolution d'équations linéaires Max-Plus $x = Ax \\oplus b$\n",
    "\n",
    "Soit $A \\in \\mathbb{R}_{\\varepsilon}^{n \\times n}$ une matrice Max-plus carrée et $b \\in \\mathbb{R}_{\\varepsilon}^{n}$ un vecteur colonne. La solution de $x = Ax \\oplus b$ est donnée par :\n",
    "$$x = A^* b$$\n",
    "\n",
    "Où :\n",
    "\n",
    "$$A^+ \\triangleq A^1 \\oplus A^2 \\oplus A^3 \\oplus\\;...$$\n",
    "$$A^* \\triangleq A^0 \\oplus A^+$$\n",
    "\n",
    "$A^0$ n'est d'autre que la matrice identité Max-Plus. $A^+$ est calculé par la fonction `plus` et $A^*$ est calculé par la fonction `star`. La solution de l'équation est donnée par la fonction `astarb`. Une solution existe dès que le plus grand circuit dans le graphe\n",
    "d'adjacence de la matrice a un poids negatif ou nul. Le poids d'un circuit étant donné par la\n",
    "somme des poids des arcs (coefficients de la matrice) le constituant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) Inf"
      ]
     },
     "execution_count": 136,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "star(MP(2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(max,+) 0"
      ]
     },
     "execution_count": 137,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "star(MP(-2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "   0   -2\n",
       "  -1    0\n"
      ]
     },
     "execution_count": 138,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = MP([-3 -2; -1 0])\n",
    "plus(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 (max,+) dense matrix:\n",
       "   0   -2\n",
       "  -1    0\n"
      ]
     },
     "execution_count": 139,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "star(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 140,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "plus(A) == A * star(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 141,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "star(zeros(MP, 2,2)) == star(full(zeros(MP, 2,2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element (max,+) vector:\n",
       "  .\n",
       "  0\n"
      ]
     },
     "execution_count": 142,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b = MP([mp0; mp1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element (max,+) vector:\n",
       "  -2\n",
       "   0\n"
      ]
     },
     "execution_count": 143,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = astarb(A, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 144,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x == A * x + b"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.8.1",
   "language": "julia",
   "name": "julia-1.8"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.8.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}