{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithmes sur les graphes\n",
    "> Cours NSI Terminale - Thème 5.\n",
    "- toc: true \n",
    "- badges: true\n",
    "- comments: false\n",
    "- categories: [python, NSI, Terminale, graphes, Algorithmique, POO, TP]\n",
    "- image: images/nsi5.png"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "fefed06257bacfa894078de359a0201d",
     "grade": false,
     "grade_id": "cell-1c6afcaabfa77ca5",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## TP sur les graphes\n",
    "\n",
    "Nous comencerons par introduire la classe Graphe que nous allons compléter au fur à mesure de ce TP.\n",
    "\n",
    "Elle reprend un certain nombre de notions vues lors de la découverte des graphes dans la partie *Structures de données*.\n",
    "\n",
    "Un graphe y est représenté en interne par un dictionnaire d'adjacence : \n",
    "- chaque clé est un noeud \n",
    "- chaque valeur est la liste des noeuds connectés représenté par un tuple (noeud, pondération)\n",
    "\n",
    "Les données sont stockées dans la propriété privée `__noeud` de type dictionnaire. On y accède pas directement. L'accès se fait par les méthodes (*accesseurs*) comme `sommets()` ou `voisins()`\n",
    "\n",
    "La méthode `show()` permet de visualiser graphiquement le graphe à l'aide du module **graphviz**. On ne cherchera pas à entrer dans les détails de cette méthode mais vous pouvez tenter de l'analyser, son fonctionnement est assez basique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "6fa7c09db1515fa2cf0d9d3e64e641cd",
     "grade": false,
     "grade_id": "cell-3c90a4ff67490a3d",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "from graphviz import Digraph\n",
    "\n",
    "class Graphe():\n",
    "    \"\"\"Graphe implémenté à l'aide d'un dictionnaire\n",
    "    Exemple : \n",
    "    {'A': [('M', 65), ('R', 90), ('T', 80)],\n",
    "     'G': [('L', 70)],\n",
    "     'L': [('G', 70), ('P', 230), ('T', 260)],\n",
    "     'M': [('A', 65), ('P', 95), ('R', 90), ('T', 55)],\n",
    "     'P': [('L', 230), ('M', 95), ('T', 130)],\n",
    "     'R': [('A', 90), ('M', 90)],\n",
    "     'T': [('A', 80), ('L', 260), ('M', 55), ('P', 130)]}\n",
    "    \"\"\"\n",
    "    def __init__(self, noeuds = None):\n",
    "        \"\"\"Initialisation avec un graphe vide\n",
    "        __noeuds est un dictionnaire\n",
    "        - clé = Valeur du noeud (chaine, entier)\n",
    "        - valeur = liste d'aretes (clé, poids)\"\"\"\n",
    "        if noeuds is None:\n",
    "            self.__noeuds = dict()\n",
    "        else:\n",
    "            self.__noeuds = noeuds\n",
    "    \n",
    "    def importe_matrice(self, matrice, noms):\n",
    "        \"\"\"Importe une matrice d'adjacence\"\"\"\n",
    "        longueur = len(matrice)\n",
    "        for i in range(longueur):\n",
    "            self.__noeuds[noms[i]] = []\n",
    "            for j in range(longueur):\n",
    "                if matrice[i][j] != 0:\n",
    "                    self.__noeuds[noms[i]].append((noms[j], matrice[i][j]))\n",
    "    \n",
    "    def ajouter_noeud(self, nd):\n",
    "        \"\"\"Ajoute un nouveau noeud au graphe\"\"\"\n",
    "        if not nd in self.__noeuds:\n",
    "            self.__noeuds[nd] = []\n",
    "    \n",
    "    def ajouter_arete(self, nd1, nd2, poids=1):\n",
    "        \"\"\"Ajoute une arête au graphe\n",
    "        si poids n'est pas renseigné, il prendra la valeur 1\"\"\"\n",
    "        # On s'assure que les arètes existent\n",
    "        self.ajouter_noeud(nd1)\n",
    "        self.ajouter_noeud(nd2)\n",
    "        # On crée la connexion nd1 -> nd2\n",
    "        self.__noeuds[nd1].append((nd2, poids))\n",
    "    \n",
    "    def liste_noeuds(self):\n",
    "        \"\"\"Renvoie la liste des noeuds\"\"\"\n",
    "        nds = list(self.__noeuds.keys())\n",
    "        nds.sort()\n",
    "        return nds\n",
    "    \n",
    "    def voisins(self, nd):\n",
    "        \"\"\"Renvoie la liste des noeuds voisins de nd\"\"\"\n",
    "        if nd in self.liste_noeuds():\n",
    "            return [a[0] for a in self.__noeuds[nd]]\n",
    "        else:\n",
    "            return []\n",
    "    \n",
    "    def arete(self,nd1, nd2):\n",
    "        \"\"\"Renvoie le poids de l'arete nd1->nd2 ou 0 si pas d'arête\"\"\"\n",
    "        if nd2 not in self.voisins(nd1):\n",
    "            return 0\n",
    "        for a in self.__noeuds[nd1]:\n",
    "            if a[0] == nd2:\n",
    "                return a[1]\n",
    "    \n",
    "    def show(self):\n",
    "        \"\"\"Représentation graphique avec graphviz\"\"\"\n",
    "        dot = Digraph(comment=\"Graphe\", format='svg')\n",
    "        for nd in self.liste_noeuds():\n",
    "            dot.node(nd,nd)\n",
    "            for a in self.__noeuds[nd]:\n",
    "                # Teste si l'arête est orientée\n",
    "                if self.arete(a[0], nd) == self.arete(nd, a[0]) :\n",
    "                    # dessin d'une arête non orientée\n",
    "                    if a[0]< nd:\n",
    "                        # On ne dessine qu'une seule arête sur les 2\n",
    "                        if a[1] != 1:\n",
    "                            dot.edge(nd, a[0],label=str(a[1]), dir=\"none\")\n",
    "                        else:\n",
    "                            dot.edge(nd, a[0], dir=\"none\")\n",
    "                else:\n",
    "                    # dessin d'une arête orientée\n",
    "                    if a[1] != 1:\n",
    "                        dot.edge(nd, a[0],label=str(a[1]))\n",
    "                    else:\n",
    "                        dot.edge(nd, a[0])\n",
    "        return dot\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "689a061bf2c2bff1624f42ca4efd1f41",
     "grade": false,
     "grade_id": "cell-e236fd765269a4ad",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "En utilisant la commande `help()` vous aurez un résumé des méthodes à votre disposition\n",
    "dans cette classe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "3a2d740f6e476d798a90e2bdc7f02315",
     "grade": false,
     "grade_id": "cell-dbffa4cf06fd0e7f",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "help(Graphe)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "8af7fb48049c7761e3d19000d0701bb1",
     "grade": false,
     "grade_id": "cell-b206efca42cfb86d",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exemples de graphes\n",
    "\n",
    "Pour commencer, voici quelques exemples de graphes. N'hésitez pas à  essayer sur ces exemples les méthodes offertes par la classe **Graphe** afin de bien vous en imprégner."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Premier exemple\n",
    "\n",
    "gr1=Graphe()\n",
    "gr1.ajouter_arete(\"A\", \"B\")\n",
    "gr1.ajouter_arete(\"C\", \"A\")\n",
    "gr1.ajouter_arete(\"C\", \"B\")\n",
    "gr1.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# testez ici les méthodes sur gr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "31b04ebac4060d753d17352a9256d1ae",
     "grade": false,
     "grade_id": "cell-8d7f0d907e6d62be",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Deuxième exemple : le graphe du cours\n",
    "matrice = [[0,1,1,0,0,0,0,0],\n",
    "          [1,0,0,1,1,0,0,0],\n",
    "          [1,0,0,1,0,0,0,0],\n",
    "          [0,1,1,0,1,0,0,0],\n",
    "          [0,1,0,1,0,1,1,0],\n",
    "          [0,0,0,0,1,0,1,0],\n",
    "          [0,0,0,0,1,1,0,1],\n",
    "          [0,0,0,0,0,0,1,0]]\n",
    "gr2 = Graphe()\n",
    "gr2.importe_matrice(matrice, [\"A\", \"B\", \"C\", \"D\", \"E\", \"F\", \"G\", \"H\"])\n",
    "gr2.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Testez ici quelques méthodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "090c9af4c7cb931a8daf9ad728f67a3f",
     "grade": false,
     "grade_id": "cell-bdc4b76513fbb391",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Parcours en profondeur\n",
    "\n",
    "Complétez la classe Graphe afin d'ajouter la méthode `parcours_profondeur`. Celle-ci est déjà un peu ébauchée, vous devrez compléter le coeur de l'algorithme récursif dans la fonction `dfs`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "7b3d49674a4e71c60506927ebfa87578",
     "grade": false,
     "grade_id": "cell-8b53f5cd59b018bd",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "class Graphe():\n",
    "    \"\"\"Graphe implémenté à l'aide d'un dictionnaire\n",
    "    Exemple : \n",
    "    {'A': [('M', 65), ('R', 90), ('T', 80)],\n",
    "     'G': [('L', 70)],\n",
    "     'L': [('G', 70), ('P', 230), ('T', 260)],\n",
    "     'M': [('A', 65), ('P', 95), ('R', 90), ('T', 55)],\n",
    "     'P': [('L', 230), ('M', 95), ('T', 130)],\n",
    "     'R': [('A', 90), ('M', 90)],\n",
    "     'T': [('A', 80), ('L', 260), ('M', 55), ('P', 130)]}\n",
    "    \"\"\"\n",
    "    def __init__(self, noeuds = None):\n",
    "        \"\"\"Initialisation avec un graphe vide\n",
    "        __noeuds est un dictionnaire\n",
    "        - clé = Valeur du noeud (chaine, entier)\n",
    "        - valeur = liste d'aretes (clé, poids)\"\"\"\n",
    "        if noeuds is None:\n",
    "            self.__noeuds = dict()\n",
    "        else:\n",
    "            self.__noeuds = noeuds\n",
    "    \n",
    "    def importe_matrice(self, matrice, noms):\n",
    "        \"\"\"Importe une matrice d'adjacence\"\"\"\n",
    "        longueur = len(matrice)\n",
    "        for i in range(longueur):\n",
    "            self.__noeuds[noms[i]] = []\n",
    "            for j in range(longueur):\n",
    "                if matrice[i][j] != 0:\n",
    "                    self.__noeuds[noms[i]].append((noms[j], matrice[i][j]))\n",
    "    \n",
    "    def ajouter_noeud(self, nd):\n",
    "        \"\"\"Ajoute un nouveau noeud au graphe\"\"\"\n",
    "        if not nd in self.__noeuds:\n",
    "            self.__noeuds[nd] = []\n",
    "    \n",
    "    def ajouter_arete(self, nd1, nd2, poids=1):\n",
    "        \"\"\"Ajoute une arête au graphe\n",
    "        si poids n'est pas renseigné, il prendra la valeur 1\"\"\"\n",
    "        # On s'assure que les arètes existent\n",
    "        self.ajouter_noeud(nd1)\n",
    "        self.ajouter_noeud(nd2)\n",
    "        # On crée la connexion nd1 -> nd2\n",
    "        self.__noeuds[nd1].append((nd2, poids))\n",
    "    \n",
    "    def liste_noeuds(self):\n",
    "        \"\"\"Renvoie la liste des noeuds\"\"\"\n",
    "        nds = list(self.__noeuds.keys())\n",
    "        nds.sort()\n",
    "        return nds\n",
    "    \n",
    "    def voisins(self, nd):\n",
    "        \"\"\"Renvoie la liste des noeuds voisins de nd\"\"\"\n",
    "        if nd in self.liste_noeuds():\n",
    "            return [a[0] for a in self.__noeuds[nd]]\n",
    "        else:\n",
    "            return []\n",
    "    \n",
    "    def arete(self,nd1, nd2):\n",
    "        \"\"\"Renvoie le poids de l'arete nd1->nd2 ou 0 si pas d'arête\"\"\"\n",
    "        if nd2 not in self.voisins(nd1):\n",
    "            return 0\n",
    "        for a in self.__noeuds[nd1]:\n",
    "            if a[0] == nd2:\n",
    "                return a[1]\n",
    "    \n",
    "    def show(self):\n",
    "        \"\"\"Représentation graphique avec graphviz\"\"\"\n",
    "        dot = Digraph(comment=\"Graphe\", format='svg')\n",
    "        for nd in self.liste_noeuds():\n",
    "            dot.node(nd,nd)\n",
    "            for a in self.__noeuds[nd]:\n",
    "                # Teste si l'arête est orientée\n",
    "                if self.arete(a[0], nd) == self.arete(nd, a[0]) :\n",
    "                    # dessin d'une arête non orientée\n",
    "                    if a[0]< nd:\n",
    "                        # On ne dessine qu'une seule arête sur les 2\n",
    "                        if a[1] != 1:\n",
    "                            dot.edge(nd, a[0],label=str(a[1]), dir=\"none\")\n",
    "                        else:\n",
    "                            dot.edge(nd, a[0], dir=\"none\")\n",
    "                else:\n",
    "                    # dessin d'une arête orientée\n",
    "                    if a[1] != 1:\n",
    "                        dot.edge(nd, a[0],label=str(a[1]))\n",
    "                    else:\n",
    "                        dot.edge(nd, a[0])\n",
    "        return dot\n",
    "    \n",
    "    def parcours_profondeur(self, depart):\n",
    "        \"\"\"Parcourt l'arbre en profondeur\"\"\"\n",
    "        def dfs(nd):\n",
    "            # YOUR CODE HERE\n",
    "            raise NotImplementedError()\n",
    "        deja_vu = []  # noeuds déjà visités\n",
    "        dfs(depart)\n",
    "        return deja_vu\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "73e00244097b948ea68c97cd1f7ee8dd",
     "grade": true,
     "grade_id": "cell-3e6e472b9cd5f7c8",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Testez votre classe\n",
    "matrice = [[0,1,1,0,0,0,0,0],\n",
    "          [1,0,0,1,1,0,0,0],\n",
    "          [1,0,0,1,0,0,0,0],\n",
    "          [0,1,1,0,1,0,0,0],\n",
    "          [0,1,0,1,0,1,1,0],\n",
    "          [0,0,0,0,1,0,1,0],\n",
    "          [0,0,0,0,1,1,0,1],\n",
    "          [0,0,0,0,0,0,1,0]]\n",
    "gr2 = Graphe()\n",
    "gr2.importe_matrice(matrice, [\"A\", \"B\", \"C\", \"D\", \"E\", \"F\", \"G\", \"H\"])\n",
    "assert set(gr2.parcours_profondeur(\"A\")) == {'A', 'B', 'D', 'C', 'E', 'F', 'G', 'H'}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "ec68cf06b268c29c5639c220a9a62fbb",
     "grade": false,
     "grade_id": "cell-278b82b4be147a95",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Parcours en largeur\n",
    "\n",
    "Complétez la classe Graphe afin d'ajouter la méthode `parcours_largeur`. Celle-ci aura le même comportement que la méthode `parcours_profondeur` précédente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "e8842ff9dfa088859cd95c55e734072d",
     "grade": false,
     "grade_id": "cell-14baac25eed3cc05",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "class Graphe():\n",
    "    \"\"\"Graphe implémenté à l'aide d'un dictionnaire\n",
    "    Exemple : \n",
    "    {'A': [('M', 65), ('R', 90), ('T', 80)],\n",
    "     'G': [('L', 70)],\n",
    "     'L': [('G', 70), ('P', 230), ('T', 260)],\n",
    "     'M': [('A', 65), ('P', 95), ('R', 90), ('T', 55)],\n",
    "     'P': [('L', 230), ('M', 95), ('T', 130)],\n",
    "     'R': [('A', 90), ('M', 90)],\n",
    "     'T': [('A', 80), ('L', 260), ('M', 55), ('P', 130)]}\n",
    "    \"\"\"\n",
    "    def __init__(self, noeuds = None):\n",
    "        \"\"\"Initialisation avec un graphe vide\n",
    "        __noeuds est un dictionnaire\n",
    "        - clé = Valeur du noeud (chaine, entier)\n",
    "        - valeur = liste d'aretes (clé, poids)\"\"\"\n",
    "        if noeuds is None:\n",
    "            self.__noeuds = dict()\n",
    "        else:\n",
    "            self.__noeuds = noeuds\n",
    "    \n",
    "    def importe_matrice(self, matrice, noms):\n",
    "        \"\"\"Importe une matrice d'adjacence\"\"\"\n",
    "        longueur = len(matrice)\n",
    "        for i in range(longueur):\n",
    "            self.__noeuds[noms[i]] = []\n",
    "            for j in range(longueur):\n",
    "                if matrice[i][j] != 0:\n",
    "                    self.__noeuds[noms[i]].append((noms[j], matrice[i][j]))\n",
    "    \n",
    "    def ajouter_noeud(self, nd):\n",
    "        \"\"\"Ajoute un nouveau noeud au graphe\"\"\"\n",
    "        if not nd in self.__noeuds:\n",
    "            self.__noeuds[nd] = []\n",
    "    \n",
    "    def ajouter_arete(self, nd1, nd2, poids=1):\n",
    "        \"\"\"Ajoute une arête au graphe\n",
    "        si poids n'est pas renseigné, il prendra la valeur 1\"\"\"\n",
    "        # On s'assure que les arètes existent\n",
    "        self.ajouter_noeud(nd1)\n",
    "        self.ajouter_noeud(nd2)\n",
    "        # On crée la connexion nd1 -> nd2\n",
    "        self.__noeuds[nd1].append((nd2, poids))\n",
    "    \n",
    "    def liste_noeuds(self):\n",
    "        \"\"\"Renvoie la liste des noeuds\"\"\"\n",
    "        nds = list(self.__noeuds.keys())\n",
    "        nds.sort()\n",
    "        return nds\n",
    "    \n",
    "    def voisins(self, nd):\n",
    "        \"\"\"Renvoie la liste des noeuds voisins de nd\"\"\"\n",
    "        if nd in self.liste_noeuds():\n",
    "            return [a[0] for a in self.__noeuds[nd]]\n",
    "        else:\n",
    "            return []\n",
    "    \n",
    "    def arete(self,nd1, nd2):\n",
    "        \"\"\"Renvoie le poids de l'arete nd1->nd2 ou 0 si pas d'arête\"\"\"\n",
    "        if nd2 not in self.voisins(nd1):\n",
    "            return 0\n",
    "        for a in self.__noeuds[nd1]:\n",
    "            if a[0] == nd2:\n",
    "                return a[1]\n",
    "    \n",
    "    def show(self):\n",
    "        \"\"\"Représentation graphique avec graphviz\"\"\"\n",
    "        dot = Digraph(comment=\"Graphe\", format='svg')\n",
    "        for nd in self.liste_noeuds():\n",
    "            dot.node(nd,nd)\n",
    "            for a in self.__noeuds[nd]:\n",
    "                # Teste si l'arête est orientée\n",
    "                if self.arete(a[0], nd) == self.arete(nd, a[0]) :\n",
    "                    # dessin d'une arête non orientée\n",
    "                    if a[0]< nd:\n",
    "                        # On ne dessine qu'une seule arête sur les 2\n",
    "                        if a[1] != 1:\n",
    "                            dot.edge(nd, a[0],label=str(a[1]), dir=\"none\")\n",
    "                        else:\n",
    "                            dot.edge(nd, a[0], dir=\"none\")\n",
    "                else:\n",
    "                    # dessin d'une arête orientée\n",
    "                    if a[1] != 1:\n",
    "                        dot.edge(nd, a[0],label=str(a[1]))\n",
    "                    else:\n",
    "                        dot.edge(nd, a[0])\n",
    "        return dot\n",
    "    \n",
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "12a7af7a421ff0806f9447cb243400a4",
     "grade": true,
     "grade_id": "cell-9a71bd0f38e4e55a",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Testez votre classe\n",
    "matrice = [[0,1,1,0,0,0,0,0],\n",
    "          [1,0,0,1,1,0,0,0],\n",
    "          [1,0,0,1,0,0,0,0],\n",
    "          [0,1,1,0,1,0,0,0],\n",
    "          [0,1,0,1,0,1,1,0],\n",
    "          [0,0,0,0,1,0,1,0],\n",
    "          [0,0,0,0,1,1,0,1],\n",
    "          [0,0,0,0,0,0,1,0]]\n",
    "gr2 = Graphe()\n",
    "gr2.importe_matrice(matrice, [\"A\", \"B\", \"C\", \"D\", \"E\", \"F\", \"G\", \"H\"])\n",
    "assert set(gr2.parcours_largeur(\"A\")) == {'A', 'B', 'D', 'C', 'E', 'F', 'G', 'H'}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "e0c209cfe50856dfc2e4cbdbcfb45084",
     "grade": false,
     "grade_id": "cell-29265cb161b971ec",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Chercher les cycles\n",
    "\n",
    "Pour finir ce TP, vous allez implémenter la méthode `cycle` qui ne prend aucun paramètres et qui renvoie un booleen selon que le graphe\n",
    "contient un cycle ou non.\n",
    "\n",
    "Vous implémenterez pour cela des parcours en largeur légèrement modifié\n",
    "- pour partir de tous les noeuds possibles\n",
    "- pour détecter si à un moment donné du parcours on atteint le noeud de départ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "2253177f6c5482eab01f82b729b60113",
     "grade": false,
     "grade_id": "cell-237e4fab4e492b27",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "class Graphe():\n",
    "    \"\"\"Graphe implémenté à l'aide d'un dictionnaire\n",
    "    Exemple : \n",
    "    {'A': [('M', 65), ('R', 90), ('T', 80)],\n",
    "     'G': [('L', 70)],\n",
    "     'L': [('G', 70), ('P', 230), ('T', 260)],\n",
    "     'M': [('A', 65), ('P', 95), ('R', 90), ('T', 55)],\n",
    "     'P': [('L', 230), ('M', 95), ('T', 130)],\n",
    "     'R': [('A', 90), ('M', 90)],\n",
    "     'T': [('A', 80), ('L', 260), ('M', 55), ('P', 130)]}\n",
    "    \"\"\"\n",
    "    def __init__(self, noeuds = None):\n",
    "        \"\"\"Initialisation avec un graphe vide\n",
    "        __noeuds est un dictionnaire\n",
    "        - clé = Valeur du noeud (chaine, entier)\n",
    "        - valeur = liste d'aretes (clé, poids)\"\"\"\n",
    "        if noeuds is None:\n",
    "            self.__noeuds = dict()\n",
    "        else:\n",
    "            self.__noeuds = noeuds\n",
    "    \n",
    "    def importe_matrice(self, matrice, noms):\n",
    "        \"\"\"Importe une matrice d'adjacence\"\"\"\n",
    "        longueur = len(matrice)\n",
    "        for i in range(longueur):\n",
    "            self.__noeuds[noms[i]] = []\n",
    "            for j in range(longueur):\n",
    "                if matrice[i][j] != 0:\n",
    "                    self.__noeuds[noms[i]].append((noms[j], matrice[i][j]))\n",
    "    \n",
    "    def ajouter_noeud(self, nd):\n",
    "        \"\"\"Ajoute un nouveau noeud au graphe\"\"\"\n",
    "        if not nd in self.__noeuds:\n",
    "            self.__noeuds[nd] = []\n",
    "    \n",
    "    def ajouter_arete(self, nd1, nd2, poids=1):\n",
    "        \"\"\"Ajoute une arête au graphe\n",
    "        si poids n'est pas renseigné, il prendra la valeur 1\"\"\"\n",
    "        # On s'assure que les arètes existent\n",
    "        self.ajouter_noeud(nd1)\n",
    "        self.ajouter_noeud(nd2)\n",
    "        # On crée la connexion nd1 -> nd2\n",
    "        self.__noeuds[nd1].append((nd2, poids))\n",
    "    \n",
    "    def liste_noeuds(self):\n",
    "        \"\"\"Renvoie la liste des noeuds\"\"\"\n",
    "        nds = list(self.__noeuds.keys())\n",
    "        nds.sort()\n",
    "        return nds\n",
    "    \n",
    "    def voisins(self, nd):\n",
    "        \"\"\"Renvoie la liste des noeuds voisins de nd\"\"\"\n",
    "        if nd in self.liste_noeuds():\n",
    "            return [a[0] for a in self.__noeuds[nd]]\n",
    "        else:\n",
    "            return []\n",
    "    \n",
    "    def arete(self,nd1, nd2):\n",
    "        \"\"\"Renvoie le poids de l'arete nd1->nd2 ou 0 si pas d'arête\"\"\"\n",
    "        if nd2 not in self.voisins(nd1):\n",
    "            return 0\n",
    "        for a in self.__noeuds[nd1]:\n",
    "            if a[0] == nd2:\n",
    "                return a[1]\n",
    "    \n",
    "    def show(self):\n",
    "        \"\"\"Représentation graphique avec graphviz\"\"\"\n",
    "        dot = Digraph(comment=\"Graphe\", format='svg')\n",
    "        for nd in self.liste_noeuds():\n",
    "            dot.node(nd,nd)\n",
    "            for a in self.__noeuds[nd]:\n",
    "                # Teste si l'arête est orientée\n",
    "                if self.arete(a[0], nd) == self.arete(nd, a[0]) :\n",
    "                    # dessin d'une arête non orientée\n",
    "                    if a[0]< nd:\n",
    "                        # On ne dessine qu'une seule arête sur les 2\n",
    "                        if a[1] != 1:\n",
    "                            dot.edge(nd, a[0],label=str(a[1]), dir=\"none\")\n",
    "                        else:\n",
    "                            dot.edge(nd, a[0], dir=\"none\")\n",
    "                else:\n",
    "                    # dessin d'une arête orientée\n",
    "                    if a[1] != 1:\n",
    "                        dot.edge(nd, a[0],label=str(a[1]))\n",
    "                    else:\n",
    "                        dot.edge(nd, a[0])\n",
    "        return dot\n",
    "    \n",
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "85e999358138f50bc3f9c8d2275ed9fa",
     "grade": true,
     "grade_id": "cell-6373f7a5227c23b1",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Testez votre classe\n",
    "matrice = [[0,1,1,0,0,0,0,0],\n",
    "          [1,0,0,1,1,0,0,0],\n",
    "          [1,0,0,1,0,0,0,0],\n",
    "          [0,1,1,0,1,0,0,0],\n",
    "          [0,1,0,1,0,1,1,0],\n",
    "          [0,0,0,0,1,0,1,0],\n",
    "          [0,0,0,0,1,1,0,1],\n",
    "          [0,0,0,0,0,0,1,0]]\n",
    "gr2 = Graphe()\n",
    "gr2.importe_matrice(matrice, [\"A\", \"B\", \"C\", \"D\", \"E\", \"F\", \"G\", \"H\"])\n",
    "assert gr2.cycle()"
   ]
  },
  {
   "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.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}