TP1 v1-avecGrapgh.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "   # TP Graphes : modéliser un labyrinthe\n",
    "   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Considérons le problème suivant :\n",
    "\n",
    "Comment rechercher le chemin le plus long entre deux stations dans le métro? Indépendamment de l'aspect ludique, c'est en fait un problème difficile qu'on aurait bien du mal à résoudre de façon raisonnable sur un gros graphe comme celui du métro. \n",
    "Pour simplifier, nous allons donc considérer des labyrinthes.\n",
    "\n",
    "## Les labyrinthes\n",
    "\n",
    "Voici l'image d'un labyrinthe :\n",
    "\n",
    "<img src=\"https://www.di.ens.fr/~mauborgn/td-99/programmation/petitlab.gif\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ce labyrinthe peut etre représenté par le graphe suivant :\n",
    "\n",
    "<img src=\"https://www.di.ens.fr/~mauborgn/td-99/programmation/petit.gif\">\n",
    "\n",
    "Les 2 figures ci-dessus sont issues d'un TP publié sur : https://www.di.ens.fr/~mauborgn/td-99/programmation/tp8.html\n",
    "\n",
    "\n",
    "**- Chaque somment du graphe correspond à une case du labyrinthe**\n",
    "\n",
    "**- une arête relie 2 cases voisines quand le passage est possible.**\n",
    "\n",
    "**- Si une paroie empêche de passer on ne met pas l'arête.**\n",
    "\n",
    "Par exemple il n'y a pas d'arête entre les sommets (1,1) et (1,2) mais il y en a une entre (1,1) et (2,1).\n",
    "\n",
    "Implémentez ce labyrinthe avec un graphe.\n",
    "Vous utiliserez l'implémentation de graphe fournie ci-dessous, vous nommerez les sommets (1,1) (1,2) .. etc \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class graph() :\n",
    "    def __init__(self) :\n",
    "        self.lstAdj={}\n",
    "    def __str__(self):\n",
    "        return str(self.lstAdj)\n",
    "    def addSommet(self,sommet):\n",
    "        self.lstAdj[sommet]=[]\n",
    "    def addArete(self,sa,sb) :\n",
    "        self.lstAdj[sa].append(sb)\n",
    "        self.lstAdj[sb].append(sa)\n",
    "\n",
    "# 1) créez un graphe labyrinthe\n",
    "# 2) ajoutez les sommets (1,1) et (1,2 puis l'arête (1,1)--(1,2)\n",
    "labyrinthe=graph()\n",
    "labyrinthe.addSommet((1,1))\n",
    "labyrinthe.addSommet((1,2))\n",
    "labyrinthe.addArete((1,1),(1,2))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert labyrinthe.lstAdj[(1,1)] == [(1,2)],\"vous avez fait une erreur...\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ajoutons tous les sommets dans le graphe représentant ce labyrinthe\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Entrez tous les sommets. Vous ne devez pas les entrer un par un, utilisez deux boucles imbriquées...\n",
    "for i in range(1,5):\n",
    "    for j in range(1,9):\n",
    "        labyrinthe.addSommet( (i,j) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ajoutons les arêtes.\n",
    "C'est un peu fastidieux, alors nous vous fournissons une version avec la plupart des arêtes déjà ajoutées, mais il en manque quelques unes...."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "labyrinthe.addArete((1,1),(2,1))\n",
    "labyrinthe.addArete((2,1),(2,2))\n",
    "labyrinthe.addArete((2,2),(2,3))\n",
    "labyrinthe.addArete((2,2),(3,2))\n",
    "labyrinthe.addArete((2,3),(1,3))\n",
    "labyrinthe.addArete((1,3),(1,4))\n",
    "labyrinthe.addArete((1,4),(1,5))\n",
    "labyrinthe.addArete((1,4),(2,4))\n",
    "labyrinthe.addArete((1,5),(2,5))\n",
    "labyrinthe.addArete((2,7),(3,7))\n",
    "labyrinthe.addArete((1,6),(1,7))\n",
    "labyrinthe.addArete((2,4),(3,4))\n",
    "labyrinthe.addArete((1,7),(1,8))\n",
    "labyrinthe.addArete((1,8),(2,8))\n",
    "labyrinthe.addArete((3,2),(4,2))\n",
    "labyrinthe.addArete((4,2),(4,3))\n",
    "labyrinthe.addArete((4,3),(4,4))\n",
    "labyrinthe.addArete((3,4),(3,5))\n",
    "labyrinthe.addArete((3,5),(3,6))\n",
    "labyrinthe.addArete((3,6),(4,6))\n",
    "labyrinthe.addArete((3,6),(3,7))\n",
    "labyrinthe.addArete((4,6),(4,5))\n",
    "labyrinthe.addArete((3,7),(4,7))\n",
    "labyrinthe.addArete((4,7),(4,8))\n",
    "labyrinthe.addArete((4,8),(3,8))\n",
    "labyrinthe.addArete((2,8),(3,8))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# dessin de votre labyrinthe\n",
    "En creant votre graphe vous avez creer votre labyrinthe.\n",
    "Pour visualiser le labyrinthe vous allez avoir besoin des fonctions ci-dessous.\n",
    "Vpus n'avez pas besoin de les regarder, la seule chose dont vous avez besoin c'est de dessiner ce labyrinthe en executant dans la cellule suivante la commande showLabyrinthe(cote,nli,ncol) ou :\n",
    "cote est un entier qui code la longuer des coté des cases (ici on va prendre 50)\n",
    "nli et ncol sont les nombres de lignes et de colones de votre labyrinthe, donc ici 4 et 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from mobilechelonian import Turtle\n",
    "\n",
    "def showLabyrinthe(labyrinthe,cote,nli,ncol):\n",
    "  t = Turtle()\n",
    "  t.speed(10)\n",
    "  cadre(t,nli,ncol,40)\n",
    "  paroiesVerticales(t,nli,ncol,40)\n",
    "  paroiesHorizontales(t,nli,ncol,40)\n",
    "  #t.home()\n",
    "\n",
    "\n",
    "def cadre(t,nli,ncol,cote):\n",
    "    goto(t,-180,180)\n",
    "    t.pendown()\n",
    "    #dessin parois extérieures\n",
    "    for _ in range(2):\n",
    "        for i in range(ncol):\n",
    "            t.forward(cote)\n",
    "        t.right(90)\n",
    "        for i in range(nli):\n",
    "            t.forward(cote)\n",
    "        t.right(90)\n",
    "\n",
    "\n",
    "    \n",
    "def paroiesVerticales(t,nli,ncol,dist):\n",
    "    # dessin des parois internes verticales\n",
    "    \n",
    "    for i in range(1,nli+1):\n",
    "        for j in range(1,ncol) :\n",
    "            dess=(i,j+1) not in labyrinthe.lstAdj[(i,j)]\n",
    "            if dess :\n",
    "                t.penup()\n",
    "                t.forward(dist)\n",
    "                t.pendown()\n",
    "                t.right(90)\n",
    "                t.forward(dist)\n",
    "                t.backward(dist)\n",
    "                t.left(90)\n",
    "            else :\n",
    "                t.penup()\n",
    "                t.forward(dist)\n",
    "        if i<4 :\n",
    "            nextLine(t,dist)\n",
    "        \n",
    "def nextLine(t,dist):\n",
    "        t.penup()\n",
    "        t.backward(7*dist)\n",
    "        t.right(90)\n",
    "        t.forward(dist)\n",
    "        t.left(90)\n",
    "        #goto(t,-200,180-i*dist)\n",
    "\n",
    "def goto(t,x,y):\n",
    "    t.home()\n",
    "    t.penup()\n",
    "    if x>0 :\n",
    "        t.backward(x)\n",
    "    else:\n",
    "        t.forward(x)\n",
    "    if y>0 :\n",
    "        t.right(90)\n",
    "        t.backward(y)\n",
    "        t.left(90)\n",
    "    else:\n",
    "        t.right(90)\n",
    "        t.backward(y)\n",
    "        t.left(90)\n",
    "        \n",
    "def paroiesHorizontales(t,nli,ncol,cote):\n",
    "\n",
    "    # dessin des parois internes horizontales\n",
    "    t.penup()\n",
    "    goto(t,-180,180-cote)\n",
    "    for i in range(1,nli):\n",
    "\n",
    "        for j in range(1,ncol) :\n",
    "            dess=(i+1,j) not in labyrinthe.lstAdj[(i,j)]\n",
    "            if dess :\n",
    "                t.pendown()\n",
    "                t.forward(cote)\n",
    "                t.penup()\n",
    "            else :\n",
    "                t.penup()\n",
    "                t.forward(cote)\n",
    "        t.penup()\n",
    "        nextLine(t,cote)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "971be8a3c5f6404ba9dfff174b0b6460",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Turtle()"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#exécutez le dessin :\n",
    "showLabyrinthe(labyrinthe,50,4,8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maintenant comme pour comme pour le labyrinthe, vous allez pouvoir visualiser le graphe avec le code ci-dessous.\n",
    "Vous pourrez l'exécuter  la cellule suivante."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "from mobilechelonian import Turtle\n",
    "\n",
    "def drawGraph() :\n",
    "    t2 = Turtle()\n",
    "    t2.speed(10)\n",
    "    t2.penup()\n",
    "    goto(t2,-180,180)\n",
    "    for i in range(1,5) :\n",
    "        for j in range(1,9) :\n",
    "            t2.forward(15)\n",
    "            circle(t2,6)\n",
    "            if (i+1,j) in labyrinthe.lstAdj[(i,j)] :\n",
    "                drawArreteVert(t2)\n",
    "            if (i,j+1) in labyrinthe.lstAdj[(i,j)] :\n",
    "                drawArreteHor(t2)\n",
    "            t2.forward(30)\n",
    "        t2.right(90)\n",
    "        t2.forward(30)\n",
    "        t2.left(90)\n",
    "        t2.backward(45*8)\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "def goto(t,x,y):\n",
    "    t.home()\n",
    "    t.penup()\n",
    "    if x>0 :\n",
    "        t.backward(x)\n",
    "    else:\n",
    "        t.forward(x)\n",
    "    if y>0 :\n",
    "        t.right(90)\n",
    "        t.backward(y)\n",
    "        t.left(90)\n",
    "    else:\n",
    "        t.right(90)\n",
    "        t.backward(y)\n",
    "        t.left(90)\n",
    "        \n",
    "def circle(t,l) :\n",
    "    t.pendown()\n",
    "    for i in range (0,9):\n",
    "        t.right(40)\n",
    "        t.forward(l) \n",
    "    t.penup()\n",
    "\n",
    "def drawArreteHor(t):\n",
    "    t.penup()\n",
    "    t.pencolor(\"red\")\n",
    "    t.forward(8)\n",
    "    t.right(90)\n",
    "    t.forward(8)\n",
    "    t.left(90)\n",
    "    t.pendown()\n",
    "    t.forward(25)\n",
    "    t.penup()\n",
    "    t.backward(33)\n",
    "    t.left(90)\n",
    "    t.forward(8)\n",
    "    t.right(90)\n",
    "    t.pencolor(\"black\")\n",
    "\n",
    "    \n",
    "def drawArreteVert(t):\n",
    "        t.pencolor(\"red\")\n",
    "        t.backward(2)\n",
    "        t.right(90)\n",
    "        t.forward(18)\n",
    "        t.pendown()\n",
    "        t.forward(12)\n",
    "        t.penup()\n",
    "        t.backward(30)\n",
    "        t.left(90)\n",
    "        t.forward(2)\n",
    "        t.pencolor(\"black\")\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "91717ae45ea9493d9510acbaebee9780",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Turtle()"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "drawGraph()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comme vous pouvez le constater, toutes les arêtes issues de (2,6) ont été oubliées....\n",
    "A vous de les ajouter, puis de redessinner le labyrinthe et le graphe pour vérifier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "labyrinthe.addArete((2,5),(2,6))\n",
    "labyrinthe.addArete((2,6),(1,6))\n",
    "labyrinthe.addArete((2,6),(3,6))\n",
    "labyrinthe.addArete((2,6),(2,7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#réexécutez le dessin du labyrinthe:\n",
    "showLabyrinthe(labyrinthe,50,4,8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#réexécutez le dessin du graphe:\n",
    "drawGraph()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center><font color=\"red\" size=\"12\">questions</font></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b>1) Faites afficher les case ou je peux me rendre si je suis en (3,4)</b>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(labyrinthe.lstAdj[(3,4)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b>2) Ecrire une fonction passage(case1,case2) qui renvoie True si on peut passer de case1 à case2 et False sinon\n",
    "</b>\n",
    "La fonction doit vérifier que les 2 cases sont contiguës et qu'il n'y a pas de paroie empêchant le passage"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def passage(case1,case2) :\n",
    "    voisinH = case1[0]==case2[0] and abs(case1[1]-case2[1])==1\n",
    "\n",
    "    voisinV = case1[1]==case2[1] and abs(case1[0]-case2[0])==1\n",
    "\n",
    "    paroie = case2 in labyrinthe.lstAdj[case1]\n",
    "    if (voisinH or voisinV) and not  paroie :\n",
    "        return True\n",
    "    else :\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#tests :\n",
    "ok=True\n",
    "assert passage( (1,2),(2,2))==True ,\"erreur\"\n",
    "assert passage( (2,2),(2,3))==False ,\"erreur\"\n",
    "assert passage( (2,2),(3,3))==False ,\"erreur\"\n",
    "assert passage( (2,2),(2,2))==False ,\"erreur\"\n",
    "assert passage( (2,3),(2,5))==False ,\"erreur\"\n",
    "print('test ok',ok)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Auteurs Jean-Louis THIROT\n",
    "Avec la collaboration de V. Musseaux et de Mireille COILHAC\n",
    "<img width=\"200\" src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/c/ce/Cc-by-nc-sa_euro_icon.svg/800px-Cc-by-nc-sa_euro_icon.svg.png\" alt=\"Licence : CC by NC-SA\">"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Edit 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.7.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}