{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TP sur les graphes\n",
    "\n",
    "> Cours NSI Terminale - Thème 1.\n",
    "\n",
    "- toc: true \n",
    "- badges: true\n",
    "- comments: false\n",
    "- categories: [python, NSI, Terminale, Structure_donnees, graphes, TP]\n",
    "- image: images/nsi1.png"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On représente le réseau autoroutier entre les villes de Rennes (R), Angers (A), Tours (T), Le Mans (M), Paris (P), Lyon (L) et Grenoble (G) à l’aide d’un graphe. Les villes sont les sommets du graphe et les (auto)routes sont représentées par les arêtes du graphe.\n",
    "On a indiqué les distances entre les villes sur les arêtes\n",
    "![Graphe](my_icons/graphe.png)\n",
    "\n",
    "## Matrice d'adjacence\n",
    "Ecrire la matrice d'adjacence de ce graphe :\n",
    "- La matrice sera représentée par un tableau à 2 dimensions\n",
    "- la variable s'appellera `matrice1`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "e733851eed6894c9038935e25ce5a5ba",
     "grade": false,
     "grade_id": "cell-cbda8db5817922be",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# Votre réponse ici\n",
    "\n",
    "matrice1 = [[]]\n",
    "\n",
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "40f9051646f1158b3ad6b298420815d4",
     "grade": true,
     "grade_id": "cell-86e4baa48a49b197",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Vérification de la réponse\n",
    "assert matrice1[0][6] == 120"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "fe396aadf4bb3390b7d53a230e774217",
     "grade": false,
     "grade_id": "cell-c4d829d9d2c42595",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Liste d'adjacence\n",
    "\n",
    "Ecrire une fonction `matrice2liste(matrice, noms)`\n",
    "- prenant en paramètres `matrice` : matrice d'adjacence et `noms` : noms des sommets dans l'ordre de la matrice\n",
    "- renvoyant un dictionnaire dont les clés sont les sommets et les valeurs sont un tableau de tuples au format `('Nom', distance)`.\n",
    "\n",
    "Exemple : A est reliée à M, R et T. le dictionnaire commencera par \n",
    "`{'A':[('M',100), ('R', 120), ('T', 120)] ...} `"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "b68aeef3e0b21d5c58bacebbc4c03c0b",
     "grade": false,
     "grade_id": "cell-62df081910a72b0f",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def matrice2liste(matrice, noms):\n",
    "    \"\"\"Renvoie la liste d'adjacence sous format dictionnaire\"\"\"\n",
    "    \n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "aba4298e411f2ae03422a2ae7312f3ce",
     "grade": true,
     "grade_id": "cell-9207e2eb47edfee2",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "matrice = [[1, 2, 1, 0],\n",
    "           [2, 3, 0, 1],\n",
    "           [1, 0, 0, 0],\n",
    "           [0, 1, 0, 4]]\n",
    "test = matrice2liste(matrice, ['A', 'B', 'C', 'D'])\n",
    "\n",
    "assert test['C'] == [('A', 1)]\n",
    "assert ('B', 2) in test['A']\n",
    "assert ('D', 4) in test['D']\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "a0e657356b995d5c5b02dab41f45dd56",
     "grade": false,
     "grade_id": "cell-159970c9b81290b3",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Liste d'adjacence vers matrice\n",
    "\n",
    "On considère à présent le graphe représentant les mêmes villes mais les sommets sont pondérés par le temps de parcours en minutes. Voici sa liste d'adjacence au format dictionnaire tel que décrit plus haut:\n",
    "```python\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",
    "\n",
    "Ecrire une fonction `liste2matrice(dico)` prenant en paramètre un graphe donné par une liste d'adjacence sous format dictionnaire comme ci-dessus et renvoyant la matrice d'adjacence de ce graphe ainsi que un tableau des sommets.\n",
    "\n",
    "En d'autre termes, la fonction `liste2matrice` est l'inverse de la fonction `matrice2liste` précédente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "20903caf80658514819ff130ad622f36",
     "grade": false,
     "grade_id": "cell-b0af5dc3a2200c7b",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def liste2matrice(dico):\n",
    "    \"\"\"Converti une liste d'adjacence en matrice d'adjacence\"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "79b12b24343eea647106fe6f747d2f1b",
     "grade": true,
     "grade_id": "cell-e60d21c6b7c1954a",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Vérification\n",
    "\n",
    "test = {'A': [('A', 1), ('B', 2), ('C', 1)],\n",
    " 'B': [('A', 2), ('B', 3), ('D', 1)],\n",
    " 'C': [('A', 1)],\n",
    " 'D': [('B', 1), ('D', 4)]}\n",
    "l, n = liste2matrice(test)\n",
    "assert n == ['A', 'B', 'C', 'D']\n",
    "assert l == [[1, 2, 1, 0], [2, 3, 0, 1], [1, 0, 0, 0], [0, 1, 0, 4]]\n"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Aucun(e)",
  "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": 2
}