{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Labyrinthes\n",
    "\n",
    "Marc Lorenzi - 7 juin 2018"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans ce notebook nous allons répondre à deux questions :\n",
    "\n",
    "- Comment créer un labyrinthe \"aléatoire\" ?\n",
    "- Comment trouver son chemin dans un labyrinthe ?\n",
    "\n",
    "Nous allons voir que les réponses à ces deux questions sont identiques."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Créer un labyrinthe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Le rectangle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soient $M$ et $N$ deux entiers non nuls. Considérons l'ensemble des points à coordonnées entières du rectangle $[0,M[\\times [0, N[$. Nous noterons $S$ ce rectangle. Chaque point du rectangle (nous dirons __sommet__) possède en général 4 voisins, les sommets au-dessus, au-dessous, à gauche et à droite du point en question. Bien entendu, les points au bord du rectangle n'ont que 3 voisins, et les coins du rectangle n'en ont que deux. Nous appellerons __arête__ tout couple $(p,q)$ tel que $p$ et $q$ soient voisins. Nous noterons $A$ l'ensemble des arêtes. Le couple $G=(S,A)$ est ce que l'on appelle un __graphe__."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `voisins` renvoie la liste des voisins d'un sommet. Elle calcule les 4 voisins de celui-ci et renvoie ceux qui sont admissibles, c'est à dire dont les coordonnées sont respectivement dans $[0,M[$ et $[0,N[$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def voisins(p, M, N):\n",
    "    s = [gauche(p), droit(p), bas(p), haut(p)]\n",
    "    return [v for v in s if admissible(v, M, N)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gauche(p):\n",
    "    x, y = p\n",
    "    return (x - 1, y)\n",
    "\n",
    "def droit(p):\n",
    "    x, y = p\n",
    "    return (x + 1, y)\n",
    "\n",
    "def bas(p):\n",
    "    x, y = p\n",
    "    return (x, y - 1)\n",
    "\n",
    "def haut(p):\n",
    "    x, y = p\n",
    "    return (x, y + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def admissible(v, M, N):\n",
    "    x, y = v\n",
    "    return x >= 0 and x < M and y >= 0 and y < N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "voisins((3, 2), 10, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "voisins((9, 2), 10, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "voisins((0, 0), 10, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 C'est quoi un labyrinthe ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un chemin dans un graphe $G$ d'un sommet $p$ à un sommet $q$ est une liste d'arêtes reliant $p$ à $q$. Évidemment, dans le cas de notre rectangle, il existe des tas de chemins reliant un sommet à un autre. Des questions rigolotes se posent (du genre \"combien de chemins ?\") mais ce n'est pas à l'ordre du jour.\n",
    "\n",
    "Qu'appellerons-nous un \"labyrinthe\" ? Je vais choisir une définition qui, bien que restrictive, est intéressante.\n",
    "\n",
    "__Définition__ : Un sous-graphe de $G=(S,A)$ est un graphe $G'=(S, A')$ où $S$ est l'ensemble des sommets de $G$ et $A'\\subset A$ est une partie de l'ensemble des arêtes de $G$.\n",
    "\n",
    "Remarquons que $G$ et $G'$ ont les mêmes sommets. Notre définition de sous-graphe n'est pas la \"vraie\" définition, il y en a de plus générales, mais elle nous conviendra ici.\n",
    "\n",
    "__Définition__ : un labyrinthe est un sous-graphe $L$ de $G$ tel que pour tous sommets $p$ et $q$ il existe un __unique__ chemin de $p$ à $q$ dans $L$.\n",
    "\n",
    "Dit autrement, un labyrinthe est un graphe dans lequel il est difficile de trouver son chemin : il n'y en a qu'un seul !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En fait :\n",
    "\n",
    "- L'existence d'un chemin entre tout couple de sommets est la notion de __connexité__.\n",
    "- L'unicité du chemin est la notion d'__acyclicité__.\n",
    "\n",
    "En résumé, un labyrinthe est un graphe connexe sans cycles. Un tel graphe porte un nom : cela s'appelle un __arbre__.\n",
    "\n",
    "__Un labyrinthe est un sous-graphe du rectangle qui est un arbre.__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 Création"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alors, comment créer un labyrinthe ? On part d'un point $p_0$ du rectangle et on explore le rectangle à partir de ce point. Comment ? En visitant les voisins de $p_0$ et en explorant le rectangle à partir de ces voisins. Bref,  \"de proche en proche\". Voici la définition de la fonction `creer_labyrinthe`. Je l'expliquerai après. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def creer_labyrinthe(p0, M, N):\n",
    "    visites = set([p0])\n",
    "    s = [p0]\n",
    "    peres = {}\n",
    "    while s != []:\n",
    "        p = s.pop()\n",
    "        vs = voisins(p, M, N)\n",
    "        melanger(vs)\n",
    "        for v in vs:\n",
    "            if v not in visites:\n",
    "                visites.add(v)\n",
    "                s.append(v)\n",
    "                peres[v] = p\n",
    "    return peres"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On crée\n",
    "\n",
    "- Un ensemble `visites`. Chaque fois que l'on recontre un nouveau sommet lors de l'exploration, on l'ajoute à cet ensemble.\n",
    "- Une liste $s$ qui contient initialement le sommet $p_0$. Chaque fois que l'on visite un sommet on l'ajoute à $s$. La liste $s$ est la liste des sommets à  partir desquels une exploration doit être lancée.\n",
    "- Un dictionnaire `peres`. À chaque fois que l'on découvre un voisin $v$ d'un sommet $p$, on décrète que $p$ est le père de $v$.\n",
    "\n",
    "Que fait la boucle `while` ? À chaque itération,\n",
    "\n",
    "- On extrait un sommet de la liste $s$.\n",
    "- On récupère la liste de ses voisins et on la mélange (un peu de hasard, ça brise la monotonie)\n",
    "- On fait des trucs aux voisins qui n'ont pas encore été visités. Quels trucs ?\n",
    "\n",
    "    - On les ajoute aux sommets visités\n",
    "    - On les ajoute à la liste du boulot à faire (la liste $s$)\n",
    "    - On leur donne un père\n",
    "    \n",
    "\n",
    "Enfin, la fonction renvoie le dictionnaire `peres`. Chaque sommet du rectangle possède un et un seul père, sauf le sommet $p_0$ dont on est parti, qui n'en a pas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `melanger` est intéressante en soi, mais je ne détaillerai pas son code. On utilise l'algorithme de Fisher-Yates, qui garantit un mélange uniforme sur toutes les permutations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def melanger(s):\n",
    "    n = len(s)\n",
    "    for k in range(n):\n",
    "        j = random.randint(k, n - 1)\n",
    "        s[j], s[k] = s[k], s[j]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testons sur un petit rectangle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = creer_labyrinthe((0, 0), 5, 5)\n",
    "print(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Théorème__ : dans un arbre, le nombre d'arêtes est égal au nombre de sommets - 1.\n",
    "\n",
    "Il devrait donc y avoir 24 éléments dans le dictionnaire des pères."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4 Dessiner l'arbre"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il n'y a qu'à tracer les arêtes de chaque sommet vers son père."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_arbre(t):\n",
    "    for (a, b) in t:\n",
    "        c, d = t[(a, b)]\n",
    "        plt.plot((a, c), (b, d), 'k')\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.rcParams['figure.figsize'] = (10, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_arbre(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.5 Dessiner le labyrinthe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `plot_laby` prend un dictionnaire de pères et deux dimensions $M$ et $N$ en paramètres. Que fait-elle ?\n",
    "\n",
    "- Elle dessine les droites d'équations $x=i+\\frac 1 2$ et $y=j+\\frac 1 2$ pour $-1\\le i<M$ et $-1\\le j < N$. Bref, elle enferme les sommets du rectangle dans des petits carrés.\n",
    "- S'il y a une arête d'un sommet vers un autre sommet (dictionnaire des pères !) elle efface le \"mur\" qui sépare ces deux sommets.\n",
    "\n",
    "Le paramètre optionnel `lab` permet de tracer aussi l'arbre (en rouge).\n",
    "\n",
    "__Mea Culpa__ : je m'excuse à l'avance pour la lenteur du tracé. `matplotlib` n'aime pas dessiner des milliers de petits segments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_labyrinthe(t, M, N, lab=False):\n",
    "    d = 0.5\n",
    "    plt.axis([-1, M, -1, N])\n",
    "    for x in range(M + 1):\n",
    "        plt.plot((x - d, x - d), (-d, N - d), 'k')\n",
    "    for y in range(N + 1):\n",
    "        plt.plot((-d, M - d), (y - d, y - d), 'k')\n",
    "    for (x, y) in t:\n",
    "        (a, b) = t[(x, y)]\n",
    "        if a == x + 1: plt.plot((x+d,x+d),(y-d,y+d),'w')\n",
    "        elif a == x - 1: plt.plot((x-d,x-d),(y-d,y+d),'w')\n",
    "        elif b == y + 1: plt.plot((x-d,x+d),(y+d,y+d),'w')\n",
    "        elif y == b + 1: plt.plot((x-d,x+d),(y-d,y-d),'w')\n",
    "        if lab: plt.plot((x,a), (y,b), 'r')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 30\n",
    "t = creer_labyrinthe((N // 2,N // 2), N, N)\n",
    "plot_labyrinthe(t, N, N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 30\n",
    "t = creer_labyrinthe((N // 2,N // 2), N, N)\n",
    "plot_labyrinthe(t, N, N, lab=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Retrouver son chemin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 La structure de données \"graphe\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jusqu'à maintenant, le dictionnaire des pères convenait parfaitement à nos besoins. Le problème c'est que dans la suite il nous faudra une structure \"inverse\" : nous devrons, pour chaque sommet du rectangle, accéder à ses éventuels fils dans le labyrinthe. Pour cela, nous allons représenter un graphe par un dictionnaire $G$. Pour chaque sommet $p$, $G[p]$ est la liste des voisins de $p$ dans le graphe. $G$ est ce que l'on appelle la représentation du graphe par des __listes d'adjacence__."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `peres_vers_graphe` fait le travail. Partant d'un dictionnaire $G$ vide, elle ajoute progressivement des arêtes en parcourant le dictionnaire des pères."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def peres_vers_graphe(peres):\n",
    "    G = {}\n",
    "    for x in peres:\n",
    "        if x in G: G[x].append(peres[x])\n",
    "        else: G[x] = [peres[x]]\n",
    "        if peres[x] in G: G[peres[x]].append(x)\n",
    "        else: G[peres[x]] = [x]\n",
    "    return G"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = creer_labyrinthe((2,2), 5, 5)\n",
    "G = peres_vers_graphe(t)\n",
    "print(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nombre_sommets(G): return len(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nombre_sommets(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nombre_aretes(G):\n",
    "    s = 0\n",
    "    for p in G: s = s + len(G[p])\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nombre_aretes(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mais pourquoi 48 ? Cela ne devrait-il pas être 24 ? Eh non. Car si $p$ et $q$ sont voisins dans $G$, $q$ apparaît dans la liste $G[p]$ ET $p$ apparaît dans la liste $G[q]$. Donc, tout va bien puisque $2\\times 24 = 48$. Je rappelle que dans un arbre, nombre d'arêtes $=$ nombre de sommets $-1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Explorer un graphe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comment explorer un graphe $G$ à partir d'un sommet $p_0$ ? Il suffit de faire un copier-coller de la fonction qui crée un labyrinthe ! Techniquement, cette fonction va faire un parcours __en profondeur__ du graphe (il existe d'autres types de parcours, je n'en parlerai pas ici)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def explorer(G, p0):\n",
    "    visites = set([p0])\n",
    "    s = [p0]\n",
    "    peres = {}\n",
    "    while s != []:\n",
    "        p = s.pop()\n",
    "        vs = G[p]\n",
    "        for v in vs:\n",
    "            if v not in visites:\n",
    "                visites.add(v)\n",
    "                s.append(v)\n",
    "                peres[v] = p\n",
    "    return peres"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = creer_labyrinthe((2,2), 5, 5)\n",
    "peres = explorer(peres_vers_graphe(t), (4,3))\n",
    "print(peres)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 Trouver l'unique chemin entre deux sommets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soient $p$ et $q$ deux sommets d'un graphe connexe $G$. Comment trouver un chemin de $p$ vers $q$ ?\n",
    "\n",
    "- On explore $G$ à partir du sommet $p$, ce qui nous donne un dictionnaire `peres`.\n",
    "- Le chemin cherché est $q$, le père de $q$, le père du père de $q$, ... jusqu'à $p$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def chemin(G, p, q):\n",
    "    if p == q: return [p]\n",
    "    else:\n",
    "        peres = explorer(G, p)\n",
    "        c = [q]\n",
    "        while peres[q] != p:\n",
    "            c.append(peres[q])\n",
    "            q = peres[q]\n",
    "        c.append(p)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = peres_vers_graphe(creer_labyrinthe((2,2), 10, 10))\n",
    "print(chemin(G, (5,5), (1,5)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4 Afficher le chemin dans le labyrinthe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Euh, eh bien on affiche le labyrinthe et puis on affiche le chemin."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def afficher_chemin(peres, M, N, chemin):\n",
    "    plot_labyrinthe(peres, M, N)\n",
    "    for k in range(len(chemin) - 1):\n",
    "        (x, y) = chemin[k]\n",
    "        (a, b) = chemin[k + 1]\n",
    "        plt.plot((x, a), (y, b), 'r')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = creer_labyrinthe((2,2), 10, 10)\n",
    "G = peres_vers_graphe(t)\n",
    "c = chemin(G, (0,0), (9,9))\n",
    "afficher_chemin(t, 10, 10, c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Allons, un dernier test, sur une grille de 2500 points. Encore une fois, l'affichage est TRÈS lent. Si vous commentez la ligne `afficher_chemin`, c'est instantané : nos algorithmes de création et de parcours s'exécutent donc en zéro seconde, ce qui est un temps acceptable :-)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = 50\n",
    "N = 50\n",
    "t = creer_labyrinthe((M // 2, N // 2), M, N)\n",
    "G = peres_vers_graphe(t)\n",
    "\n",
    "p = (0, 0)\n",
    "q = (M - 1, N - 1)\n",
    "c = chemin(G, p, q)\n",
    "afficher_chemin(t, M, N, c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}