{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graphes et Machine Learning - Interro\n",
    "\n",
    "Le devoir se compose de trois parties :\n",
    "\n",
    "* la partie I de questions de cours, où il faut juste répondre aux questions (en général une phrase courte suffit) ;\n",
    "* la partie II, dont le but est de manipuler un peu les graphes, et où on va chercher à calculer le nombre de composantes connexes dans un graphe en utilisant des outils d'algèbre linéaire que l'on a vus en cours ;\n",
    "* la partie III, où l'on va chercher des chemins dans un graphe pondéré, qui représente un terrain de jeu.\n",
    "\n",
    "De façon générale, cherchez toujours à commenter ce que vous observez, il vaut mieux en dire un peu trop qu'un peu pas assez !\n",
    "Le barème n'est pas précisément établi, mais ne paniquez pas si vous n'avez pas le temps de tout faire, c'est normal et cela sera pris en compte lors de la correction.\n",
    "\n",
    "Toute forme de recherche d'une réponse sera valorisée.\n",
    "Ainsi, même si vous n'avez pas la réponse à une question, n'hésitez pas à montrer ce que vous avez essayé de faire.\n",
    "\n",
    "Le devoir est à déposer sur Moodle à l'endroit approprié (Rendu Interro), avant 16h15.\n",
    "\n",
    "Bon courage !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## I - Questions de Cours (~1/3 des points)\n",
    "\n",
    "Répondez aux questions suivantes.\n",
    "\n",
    "\n",
    "### I.1. Représentation de Graphes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question I.1.a.** Quelles sont les deux façons de représenter des graphes en mémoire ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse:*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question I.1.b.** Quels sont les avantages et inconvénients de chacune de ces représentations ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse:*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### I.2. Parcours de Graphe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question I.2.a.** Expliquez le principe du parcours en profondeur. Pourquoi appelle-t-on ce type de parcours un parcours \"en profondeur\" ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse:*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question I.2.b.** Prenons le graphe suivant, dans quel ordre un parcours en profondeur partant du sommet 2 pourrait visiter les sommets ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.Graph()\n",
    "G.add_edges_from([(1,2),(2,3),(3,4),(1,3),(3,5),(5,6)])\n",
    "pos = nx.spring_layout(G, seed=42)\n",
    "nx.draw(G, pos, edgecolors=\"black\", node_color=\"pink\", with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse:*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question I.2.c.** Ce parcours en profondeur du graphe est-il le seul possible ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse:*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### I.3. Cliques"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question I.3.a.** Qu'est-ce qu'une clique ? Est-il toujours possible de trouver une clique dans un graphe ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse:*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question I.3.b.** Peut-on trouver une clique de taille $3$ dans un arbre ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse:*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## II - Composantes Connexes (~1/3 des points)\n",
    "\n",
    "On appelle composante connexe d'un graphe un ensemble de sommets entre lesquels il existe des chemins.\n",
    "Un graphe est dit connexe s'il n'est composé que d'une seule composante connexe."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question II.1.** Donner un exemple de graphe connexe. Affichez le avec la fonction `nx.draw()` de `networkx`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question II.2.** Coder une fonction qui prend en entrée deux entiers $k$ et $n$ et qui génère un graphe composé de $k$ composantes connexes, chaque composante connexe étant une clique de $n$ éléments.\n",
    "\n",
    "Le graphe renvoyé doit être un `nx.Graph()`. Pour rajouter des sommets et des arêtes à un graphe, vous pouvez vous référer à la documentation de `networkx`, soit sur internet soit avec `help(nx.Graph)` par exemple.\n",
    "\n",
    "Remarque: on **n'utilisera pas** la fonction `nx.caveman_graph`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def graphe_composantes_connexes(n, k):\n",
    "    # k le nombre de composantes connexes\n",
    "    # n le nombre de sommets par composante connexe\n",
    "    \n",
    "    # ~~ implémentez la fonction ~~"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question II.3.** Vérifiez que votre fonction fonctionne en affichant un graphe composé de $3$ composantes connexes ayant chacune $2$ sommets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question II.4.** Implémentez une fonction qui prend un graphe en entrée et qui en calcule la matrice laplacienne."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def laplace(G):\n",
    "    # G un `nx.Graph()`\n",
    "    \n",
    "    # ~~~ implémentez la fonction ~~~"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question II.5.** On rappelle qu'on peut calculer les valeurs propres d'une matrice avec la fonction `np.linalg.eig`. Utilisez cette fonction pour écrire une fonction qui prend en entrée un graphe et renvoie son nombre de composantes connexes. (Regardez la documentation de `numpy` pour voir ce que renvoie exactement cette fonction. Notez qu'en anglais, valeur propre se dit \"eigenvalue\".)\n",
    "\n",
    "*Indice.* Pour vérifier si un nombre est nul, on se contentera de vérifier s'il est compris entre `-1e-6` et `1e-6`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "help(np.linalg.eig)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nb_composantes(G):\n",
    "    # G un `nx.Graph`\n",
    "    \n",
    "    # ~~~ implémentez la fonction ~~~"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question II.6.** Testez votre fonction sur des graphes ayant $1$, $5$ et $50$ composantes connexes. On pourra à cet effet utiliser la fonction de la question II.3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## III - Plus Court Chemin dans un Graphe Pondéré (~1/3 des points)\n",
    "\n",
    "Dans cette partie, on essaye de trouver le chemin le plus court pour aller d'un point à un autre sur une carte.\n",
    "Pour cela, on peut utiliser des parcours de graphes.\n",
    "\n",
    "**Question III.0.** Quel type de parcours de graphes utiliser pour trouver le plus court chemin entre deux points ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse:*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Terrain de jeu."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib.collections import LineCollection\n",
    "from matplotlib.colors import ListedColormap\n",
    "cmap = ListedColormap([\"sandybrown\", \"aquamarine\"])\n",
    "\n",
    "def afficher_terrain(terrain, chemin=None):\n",
    "    plt.imshow(terrain, cmap=cmap)\n",
    "    plt.axis(\"off\");\n",
    "    \n",
    "    if chemin is not None:\n",
    "        solx = [v for (u, v) in chemin]\n",
    "        soly = [u for (u, v) in chemin]\n",
    "        plt.plot(solx, soly, color=\"red\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction ci-dessus permet d'afficher un terrain de jeu, représenté sous la forme d'une matrice.\n",
    "Prenons le terrain suivant, où la terre est représentée en marron et l'eau en bleu."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "terrain = np.zeros((10, 10))\n",
    "terrain = np.array(\n",
    "      [[0, 0, 1, 1, 0, 0, 0, 0, 0, 0],\n",
    "       [0, 0, 1, 0, 0, 0, 1, 0, 0, 0],\n",
    "       [0, 1, 1, 0, 0, 1, 1, 1, 0, 0],\n",
    "       [0, 1, 1, 0, 1, 1, 1, 1, 1, 0],\n",
    "       [0, 0, 1, 0, 0, 1, 1, 0, 0, 0],\n",
    "       [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],\n",
    "       [0, 0, 0, 0, 0, 1, 1, 0, 0, 0],\n",
    "       [0, 0, 0, 0, 1, 1, 0, 0, 0, 0],\n",
    "       [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],\n",
    "       [0, 0, 0, 0, 0, 1, 1, 0, 0, 0]])\n",
    "\n",
    "afficher_terrain(terrain)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Coûts des Déplacements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Représentons ce terrain sous la forme d'un graphe pondéré.\n",
    "Les sommets du graphe seront les cases du terrain, la case de coordonnées $(x, y)$ ayant pour nom $(x, y)$.\n",
    "\n",
    "Supposons que l'on puisse facilement se déplacer d'une case de terre à un autre, et que l'on se déplace avec un peu plus de difficulté dans l'eau.\n",
    "En revanche, on n'a vraiment pas envie de se mouiller, donc passer d'une case de terre à une case d'eau nous demande beaucoup de préparations et d'énergie.\n",
    "\n",
    "Résumons cela par les règles de déplacements suivantes :\n",
    "* passer d'une case de terre à une case de terre a un coût de $1$ ;\n",
    "* passer d'une case d'eau à une case d'eau a un coût de $2$ ;\n",
    "* passer d'une case de terre à une d'eau ou le contraire a un coût de $200$.\n",
    "\n",
    "On peut alors traduire notre carte par un graphe pondéré, dont les poids sont ceux décrits au dessus."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les fonctions suivantes sont des fonctions qui génèrent le graphe correspondant au terrain et des fonctions d'affichage."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def valeur(u, v, val_eau=200):\n",
    "    if u + v == 0:\n",
    "        return 1\n",
    "    if u + v == 1:\n",
    "        return val_eau\n",
    "    else:\n",
    "        return 2\n",
    "    \n",
    "valeur_normale = lambda u, v: valeur(u, v, 200)\n",
    "valeur_nulle = lambda u, v: valeur(u, v, 0)\n",
    "\n",
    "def graphe_terrain(terrain, valeur=valeur_normale):\n",
    "    width, height = terrain.shape\n",
    "    \n",
    "    aretes_poids =  [((u, v), (u+1,v), valeur(terrain[u,v], terrain[u+1,v])) \\\n",
    "                      for u in range(width - 1) for v in range(height)]\n",
    "    aretes_poids += [((u, v), (u,v+1), valeur(terrain[u,v], terrain[u,v+1])) \\\n",
    "                      for u in range(width) for v in range(height-1)]\n",
    "    \n",
    "    G = nx.Graph()\n",
    "    G.add_weighted_edges_from(aretes_poids)\n",
    "    \n",
    "    return G\n",
    "\n",
    "\n",
    "def afficher_graphe_terrain(Gterrain, terrain):\n",
    "    fig, ax = plt.subplots(figsize=(10,10))\n",
    "\n",
    "    pos = {(u, v): (v, terrain.shape[0]-u) for u in range(terrain.shape[0]) for v in range(terrain.shape[1])}\n",
    "    aretes_poids = {(u,v,): d['weight'] for u,v,d in Gterrain.edges(data=True)}\n",
    "\n",
    "    nx.draw(Gterrain, pos,\n",
    "        node_color=[\"sandybrown\" if terrain[u] == 0 else \"aquamarine\" for u in Gterrain.nodes()],\n",
    "        edgecolors=\"black\")\n",
    "    nx.draw_networkx_edge_labels(Gterrain,pos,edge_labels=aretes_poids);\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Graphe des déplacements.\n",
    "\n",
    "Affichons le graphe correspondant au terrain ci-dessus.\n",
    "Les sommets du graphe ont pour étiquette les coordonées $(x, y)$ de la case du terrain à laquelle ils correspondent, et les arêtes sont pondérées par le coût du passage d'un sommet à un autre."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Gterrain = graphe_terrain(terrain)\n",
    "\n",
    "afficher_graphe_terrain(Gterrain, terrain)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voilà une fonction qui prend un graphe en entrée et qui renvoit sa liste d'adjacence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def liste_adjacence(G):\n",
    "    adj = {}\n",
    "    \n",
    "    for sommet, adjacence in G.adjacency():\n",
    "        adj[sommet] = adjacence.keys()\n",
    "        \n",
    "    return adj"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Recherche de Chemin.\n",
    "\n",
    "Pour trouver le chemin le plus court dans ce graphe pondéré, on procède comme pour trouver le chemin le plus court dans un graphe non pondéré.\n",
    "\n",
    "On part donc d'un sommet, puis on visite ses voisins, et ainsi de suite.\n",
    "Seulement, quand on rencontre un nouveau voisin, on a deux possibilités :\n",
    "* soit on ne l'a jamais rencontré, et le chemin actuel est le plus court pour l'instant ;\n",
    "* soit on l'a déjà rencontré, auquel cas, soit le chemin actuel est plus court, et peut donc remplacer le chemin déjà connu, soit il est plus long, et on peut l'ignorer.\n",
    "\n",
    "On ne gardera donc plus en mémoire l'ensemble des sommets que l'on a déjà visités, mais la longueur du chemin le plus court que l'on connaît jusqu'à ce sommet."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question III.1.** Implémentez une fonction `plus_court_chemin` qui prend en entrée un graphe pondéré et qui **renvoie le plus court chemin** (sous la forme d'une liste de sommets) entre les deux sommets s'il en existe un, et qui renvoie `False` sinon.\n",
    "\n",
    "On pourra garder en mémoire :\n",
    "* une queue`a_visiter` (utiliser par exemple `deque`) des sommets qui restent à visiter ;\n",
    "* un dictionnaire `predecesseur` qui associe à chaque sommet son prédécesseur dans le chemin le plus court connu jusqu'ici ;\n",
    "* un dictionnaire `distance` qui associe à chaque sommet sa distance au sommet de départ. Au début, ce dictionnaire associera la valeur `np.inf` à tous les sommets sauf au sommet de départ, auquel il associera `0`. De cette façon, on pourra facilement calculer si le chemin courant est plus court ou plus long qu'un chemin déjà connu.\n",
    "\n",
    "Remarques :\n",
    "* on peut récupérer le poids d'une arête $(u, v)$ en utilisant : `poids = G.get_edge_data(u, v)[\"weight\"]` ;\n",
    "* la fonction `liste_adjacence` ci-dessus renvoie la liste d'adjacence du graphe sous forme d'un dictionnaire dont les valeurs sont les listes d'adjacences et les clés les sommets (comme en TP)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "def plus_court_chemin(G, s1, s2):\n",
    "    # G un `nx.Graph` pondéré\n",
    "    # s1 le sommet de départ\n",
    "    # s2 le sommet d'arrivée\n",
    "    \n",
    "    # ~~~ implémentez la fonction ~~~"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question III.2.** Utilisez votre fonction pour chercher le plus court chemin partant d'en haut à gauche (sommet $(0, 0)$) jusqu'au sommet en bas à droite (sommet $(9, 9)$). On utilisera le graphe `Gterrain` défini ci-dessus.\n",
    "\n",
    "Affichez ensuite le chemin obtenu en utilisant la fonction `afficher_terrain`, à laquelle vous donnerez `terrain` comme premier argument et votre chemin comme second argument."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Supposons maintenant que l'on ait extrêmement envie de plonger, et donc que, maintenant, passer de la terre ferme à l'eau a un coût de $0$.\n",
    "\n",
    "Le graphe correspondant aux coûts de déplacements sur notre terrain est donc maintenant le suivant :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "Gterrain0 = graphe_terrain(terrain, valeur_nulle)\n",
    "afficher_graphe_terrain(Gterrain0, terrain)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question III.3.** Avec ces nouvelles règles de déplacement, affichez le plus court chemin entre les sommets $(0, 0)$ et $(9, 9)$. On cherchera pour cela un chemin dans le graphe `Gterrain0` défini ci-dessus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question III.4.** Commentez le chemin obtenu. Est-ce bien le chemin le plus court ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse:*"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}