TP2 corrige version binder.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "   # TP Graphes : modéliser un labyrinthe\n",
    "   adaptation d'un TP publié sur : https://www.di.ens.fr/~mauborgn/td-99/programmation/tp8.html\n",
    "   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Considérons le problème suivant :\n",
    "\n",
    "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",
    "<img src=\"https://www.di.ens.fr/~mauborgn/td-99/programmation/petitlab.gif\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ce labyrinthe correspond au graphe suivant :\n",
    "<img src=\"https://www.di.ens.fr/~mauborgn/td-99/programmation/petit.gif\">\n",
    "\n",
    "Dans un premier TP vous avez déjà implémentez ce labyrinthe avec un graphe.\n",
    "Nous redonnons ici l'implémentation de ce graphe là ou nous en étions arrivés."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(2, 1)]\n"
     ]
    }
   ],
   "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 addArrete(self,sa,sb) :\n",
    "        self.lstAdj[sa].append(sb)\n",
    "        self.lstAdj[sb].append(sa)\n",
    "        \n",
    "labyrinthe=graph()\n",
    "for i in range(1,5):\n",
    "    for j in range(1,9):\n",
    "        labyrinthe.addSommet( (i,j) )\n",
    "labyrinthe.addArrete((1,1),(2,1))\n",
    "labyrinthe.addArrete((2,1),(2,2))\n",
    "labyrinthe.addArrete((2,2),(2,3))\n",
    "labyrinthe.addArrete((2,2),(3,2))\n",
    "labyrinthe.addArrete((2,3),(1,3))\n",
    "labyrinthe.addArrete((1,3),(1,4))\n",
    "labyrinthe.addArrete((1,4),(1,5))\n",
    "labyrinthe.addArrete((1,4),(2,4))\n",
    "labyrinthe.addArrete((1,5),(2,5))\n",
    "labyrinthe.addArrete((2,4),(3,4))\n",
    "labyrinthe.addArrete((2,5),(2,6))\n",
    "labyrinthe.addArrete((2,6),(1,6))\n",
    "labyrinthe.addArrete((2,6),(3,6))\n",
    "labyrinthe.addArrete((2,7),(3,7))\n",
    "labyrinthe.addArrete((1,6),(1,7))\n",
    "labyrinthe.addArrete((2,6),(2,7))\n",
    "labyrinthe.addArrete((1,7),(1,8))\n",
    "labyrinthe.addArrete((1,8),(2,8))\n",
    "labyrinthe.addArrete((3,2),(4,2))\n",
    "labyrinthe.addArrete((4,2),(4,3))\n",
    "labyrinthe.addArrete((4,3),(4,4))\n",
    "labyrinthe.addArrete((3,4),(3,5))\n",
    "labyrinthe.addArrete((3,5),(3,6))\n",
    "labyrinthe.addArrete((3,6),(4,6))\n",
    "labyrinthe.addArrete((3,6),(3,7))\n",
    "labyrinthe.addArrete((4,6),(4,5))\n",
    "labyrinthe.addArrete((3,7),(4,7))\n",
    "labyrinthe.addArrete((4,7),(4,8))\n",
    "labyrinthe.addArrete((4,8),(3,8))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#print(str(labyrinthe))\n",
    "print(labyrinthe.lstAdj[(1,1)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# dessin de votre labyrinthe\n",
    "Pour voir le labyrinthe que vous avez créé, vous allez avoir besoin des fonction ci-dessous.\n",
    "Vous n'avez pas besoin de les regarder, la seule chose donc vous avez besoin c'est de dessiner avec showLabyrinthe(cote,nli,ncol) ou :\n",
    "cote est un entier qui code la longuer des coté des case (mettez 50)\n",
    "nli et ncol sont les nombres de lignes et colones de votre labyrinthe, donc ici 4 et 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "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",
    "    \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",
    "                \n",
    "def dot(t):\n",
    "    t.pencolor('red')\n",
    "    t.pendown()\n",
    "    t.backward(7)\n",
    "    t.forward(14)\n",
    "    t.backward(7)\n",
    "    t.left(90)\n",
    "    t.backward(7)\n",
    "    t.forward(14)\n",
    "    t.backward(7)\n",
    "    t.right(90)\n",
    "    t.penup()\n",
    "    t.pencolor('black')\n",
    "    \n",
    "def showParcours(labyrinthe,vus,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.pencolor('red')\n",
    "    for s in vus:\n",
    "        t.penup()\n",
    "        t.home()\n",
    "        goto(t,-180,180)\n",
    "        t.forward((s[1]-1)*40+20)\n",
    "        t.right(90)\n",
    "        t.forward((s[0]-1)*40+20)\n",
    "        t.left(90)\n",
    "        t.pendown()\n",
    "        dot(t)\n",
    "    t.pencolor('black')\n",
    "    \n",
    "def showChemin(labyrinthe,chemin,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",
    "    for line in chemin :\n",
    "        s=line[0]\n",
    "        t.penup()\n",
    "        t.home()\n",
    "        goto(t,-180,180)\n",
    "        t.forward((s[1]-1)*40+20)\n",
    "        t.right(90)\n",
    "        t.forward((s[0]-1)*40+20)\n",
    "        t.left(90)\n",
    "        t.pendown()\n",
    "        \n",
    "        s1=line[1]\n",
    "        t.pendown()\n",
    "        t.forward(40*(s1[1]-s[1]))\n",
    "        t.right(90)\n",
    "        t.forward(40*(s1[0]-s[0]))\n",
    "        t.penup()\n",
    "        dot(t)\n",
    "        \n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "056e621ee56541c58d79550f72bb2861",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Turtle()"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "showLabyrinthe(labyrinthe,50,4,8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "<center><font color=\"red\" size=\"12\">DEUXIEME PARTIE : </font><br><br>\n",
    "<b>PROMENADE DANS LE LABYRINTHE</b></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b>1) commencez par implémenter les deux parcours BFS et DFS, en partant de la case (1,1)</b>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(2, 1)]\n",
      "[(1, 1), (2, 1), (2, 2), (2, 3), (3, 2), (1, 3), (4, 2), (1, 4), (4, 3), (1, 5), (2, 4), (4, 4), (2, 5), (3, 4), (2, 6), (3, 5), (1, 6), (3, 6), (2, 7), (1, 7), (4, 6), (3, 7), (1, 8), (4, 5), (4, 7), (2, 8), (4, 8), (3, 8)]\n"
     ]
    }
   ],
   "source": [
    "# BFS\n",
    "sommet=(1,1)\n",
    "vus=[sommet]\n",
    "aVoir=labyrinthe.lstAdj[(1,1)][:]\n",
    "print(aVoir)\n",
    "while aVoir != [] :\n",
    "    sommet=aVoir.pop(0)\n",
    "    vus.append(sommet)\n",
    "    voisins=labyrinthe.lstAdj[sommet]\n",
    "    for s in voisins :\n",
    "        if s not in vus and s not in aVoir :\n",
    "            aVoir.append(s)\n",
    "print(vus)\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction ci-dessous va vous permettre de visualiser les sommets visités :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "1b2006d091d5406f92a5db00e77b8987",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Turtle()"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# affichage des sommets visités\n",
    "showParcours(labyrinthe,vus,50,4,8)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(2, 1)]\n",
      "[(1, 1), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4), (2, 3), (1, 3), (1, 4), (2, 4), (3, 4), (3, 5), (3, 6), (3, 7), (4, 7), (4, 8), (3, 8), (2, 7), (4, 6), (4, 5), (2, 6), (1, 6), (1, 7), (1, 8), (2, 8), (2, 5), (1, 5)]\n"
     ]
    }
   ],
   "source": [
    "# DFS\n",
    "sommet=(1,1)\n",
    "vus=[sommet]\n",
    "aVoir=labyrinthe.lstAdj[(1,1)][:]\n",
    "print(aVoir)\n",
    "while aVoir != [] :\n",
    "    sommet=aVoir.pop()\n",
    "    vus.append(sommet)\n",
    "    voisins=labyrinthe.lstAdj[sommet]\n",
    "    for s in voisins :\n",
    "        if s not in vus and s not in aVoir :\n",
    "            aVoir.append(s)\n",
    "print(vus)\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "29ee425958824727a7b0c6f3135f52cc",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Turtle()"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# affichage des sommets visités\n",
    "showParcours(labyrinthe,vus,50,4,8)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b>2) On souhaite tracer les chemins, et non plus seulement les sommets visités</b>\n",
    "\n",
    "Il va donc maintenant garder en mémoire, pour chaque sommet, le parent associé (d'ou l'on venait)\n",
    "\n",
    "Pour cela recopiez la fonction DFS faites précédement et modifiez là comme suit :\n",
    "\n",
    "1) avant la boucle créez une liste vide chemin et un dictionnaire vide parent\n",
    "2) toujours avant la boucle, pour chaque sommet s dans aVoir, définir son parent égal à (1,1) : parent[s] = (1,1)\n",
    "3) A chaue fois qu'on ajoute un sommet dans aVoir, il faut définir son parent dans le dictionnaire parent\n",
    "3) A chaque fois qu'on ajoute un sommet dans vus on doit ajouter dans chemin un tuple (parent[sommet],sommet)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[((1, 1), (2, 1)), ((2, 1), (2, 2)), ((2, 2), (3, 2)), ((3, 2), (4, 2)), ((4, 2), (4, 3)), ((4, 3), (4, 4)), ((2, 2), (2, 3)), ((2, 3), (1, 3)), ((1, 3), (1, 4)), ((1, 4), (2, 4)), ((2, 4), (3, 4)), ((3, 4), (3, 5)), ((3, 5), (3, 6)), ((3, 6), (3, 7)), ((3, 7), (4, 7)), ((4, 7), (4, 8)), ((4, 8), (3, 8)), ((3, 7), (2, 7)), ((3, 6), (4, 6)), ((4, 6), (4, 5)), ((3, 6), (2, 6)), ((2, 6), (1, 6)), ((1, 6), (1, 7)), ((1, 7), (1, 8)), ((1, 8), (2, 8)), ((2, 6), (2, 5)), ((1, 4), (1, 5))]\n"
     ]
    }
   ],
   "source": [
    "# DFS\n",
    "sommet=(1,1)\n",
    "vus= [sommet]\n",
    "aVoir=labyrinthe.lstAdj[(1,1)][:]\n",
    "chemin=[]\n",
    "parent={}\n",
    "for s in aVoir :\n",
    "    parent[s]=sommet\n",
    "while aVoir != [] :\n",
    "    sommet=aVoir.pop()\n",
    "    vus.append(sommet)\n",
    "    chemin.append((parent[sommet],sommet))\n",
    "    voisins=labyrinthe.lstAdj[sommet]\n",
    "    #print(voisins)\n",
    "    for s in voisins :\n",
    "        if s not in vus and s not in aVoir :\n",
    "            aVoir.append(s)\n",
    "            parent[s]=sommet\n",
    "print(chemin)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "ccc5116f347c4f9cb69b6ece4ba1a293",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Turtle()"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# affichage des sommets visités\n",
    "showChemin(labyrinthe,chemin,50,4,8)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[((1, 1), (2, 1)), ((2, 1), (2, 2)), ((2, 2), (3, 2)), ((3, 2), (4, 2)), ((4, 2), (4, 3)), ((4, 3), (4, 4)), ((2, 2), (2, 3)), ((2, 3), (1, 3)), ((1, 3), (1, 4)), ((1, 4), (2, 4)), ((2, 4), (3, 4)), ((3, 4), (3, 5)), ((3, 5), (3, 6)), ((3, 6), (3, 7)), ((3, 7), (4, 7)), ((4, 7), (4, 8))]\n"
     ]
    }
   ],
   "source": [
    "# DFS\n",
    "sommet=(1,1)\n",
    "vus= [sommet]\n",
    "aVoir=labyrinthe.lstAdj[(1,1)][:]\n",
    "chemin=[]\n",
    "parent={}\n",
    "sortie=(4,8)\n",
    "for s in aVoir :\n",
    "    parent[s]=sommet\n",
    "while aVoir != [] :\n",
    "    sommet=aVoir.pop()\n",
    "    vus.append(sommet)\n",
    "    chemin.append((parent[sommet],sommet))\n",
    "    if sommet==sortie:\n",
    "        break;\n",
    "    voisins=labyrinthe.lstAdj[sommet]\n",
    "    #print(voisins)\n",
    "    for s in voisins :\n",
    "        if s not in vus and s not in aVoir :\n",
    "            aVoir.append(s)\n",
    "            parent[s]=sommet\n",
    "print(chemin)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "b4aff1cb12ab47e5830891898a6655e2",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Turtle()"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# affichage des sommets visités\n",
    "showChemin(labyrinthe,chemin,50,4,8)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[((1, 1), (2, 1)),\n",
       " ((2, 1), (2, 2)),\n",
       " ((2, 2), (3, 2)),\n",
       " ((3, 2), (4, 2)),\n",
       " ((4, 2), (4, 3)),\n",
       " ((4, 3), (4, 4)),\n",
       " ((2, 2), (2, 3)),\n",
       " ((2, 3), (1, 3)),\n",
       " ((1, 3), (1, 4)),\n",
       " ((1, 4), (2, 4)),\n",
       " ((2, 4), (3, 4)),\n",
       " ((3, 4), (3, 5)),\n",
       " ((3, 5), (3, 6)),\n",
       " ((3, 6), (3, 7)),\n",
       " ((3, 7), (4, 7)),\n",
       " ((4, 7), (4, 8))]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chemin\n"
   ]
  },
  {
   "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.7.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}