{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1><center> Graphes - Implémentations </center></h1>\n",
    "\n",
    "<h3> Il y a plusieurs façons d'implémenter des graphes **non orientés**.<br><br> Nous allons en voir deux :\n",
    "    <ul> <li> avec un dictionnaire </li>\n",
    "        <li> avec une matrice d'adjacence</li>\n",
    "    </ul>\n",
    "</h3>\n",
    "Dans tous les cas, nous chercherons à implémenter les méthodes suivantes :\n",
    "\n",
    "![Méthodes](https://nc-lycees.netocentre.fr/s/6A54DEy3dq22e2m/preview)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Utilsation de la structure ensemble de Python : set </h3>\n",
    "les sets sont des collections d'éléments non-ordonnées. <br>Dans un set, chaque élément doit être unique et immuable , c'est-à- dire qu'il ne peut pas être modifié."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "E=set() # création de l'ensemble E vide \n",
    "E.add(\"bonjour\") # ajout d'un élément dans E\n",
    "E.add(\"toi\")\n",
    "E.add(12)\n",
    "print(E)\n",
    "print(len(E))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "un élément est unique dans un ensemble"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "E.add(12) # on ajoute encore 12 à E\n",
    "print(E)\n",
    "print(len(E))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> Affichage d'un graphe </h2>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import de networkx pour l'affichage des graphes.\n",
    "import networkx\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> 1. Implémentation avec un dictionnaire </h2>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-warning\" role=\"alert\">\n",
    "    \n",
    "<h3> Exercice 1 </h3>\n",
    "<p> Voici ci-dessous la classe Graphe </p> \n",
    "    <p> un objet de cette classe est donc défini par un dictionnaire vide à sa création</p>\n",
    "<p> Compléter cette classe Graphe et éxécuter le test.<br> <b>Les clés seront les sommets du graphe et leur valeur sera l'ensemble des sommets adjacents.</b></p>\n",
    "    \n",
    "Attention, comme le graphe n'est pas orienté, si A et B sont adjacents, il faudra faire une arête de A vers B et aussi de B vers A.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graphe:\n",
    "    def __init__(self):\n",
    "        self.dico_adj={} # dictionnaire vide \n",
    "        \n",
    "    def ajouter_sommet(self,s):\n",
    "        \"\"\" ajoute un sommet s au graphe avec à la création aucune arete partant de s  \"\"\"\n",
    "        if s not in self.dico_adj:\n",
    "            self.dico_adj[s]=set() # ensemble vide\n",
    "            \n",
    "    def ajouter_arete(self, s1, s2):\n",
    "        \"\"\" crée l'arête entre le sommet s1 et le sommet s2 si s1 et s2 existe \n",
    "            et doit créer les sommets s'il(s) n'existe(nt) pas\"\"\"\n",
    "        pass\n",
    "        \n",
    "    def est_arete(self,s1,s2):\n",
    "        \"\"\" renvoie vraie s'il existe une arete entre le sommet s1 et le sommet s2, faux sinon\"\"\"\n",
    "        pass\n",
    "    \n",
    "    def sommets(self):\n",
    "        \"\"\" retourne la liste des sommets\"\"\"\n",
    "        pass\n",
    "    \n",
    "    def voisins(self,s):\n",
    "        \"\"\" renvoie la liste des voisins du sommet s \"\"\"\n",
    "        pass\n",
    "    \n",
    "    def __str__(self): \n",
    "        \"Affichage du graphe en utilisant le module networkx\"\n",
    "        plt.cla()\n",
    "        G = networkx.Graph()\n",
    "        for s1 in self.sommets():\n",
    "            for s2 in self.voisins(s1):\n",
    "                G.add_edge(s1,s2)\n",
    "        networkx.draw(G, with_labels=True,node_color=\"skyblue\" ) \n",
    "        plt.show()\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sommets du graphe :  None\n",
      "Voisins de A :  None\n",
      "Voisins de B :  None\n",
      " A et B sont reliés : None\n",
      " D et D sont reliés : None\n"
     ]
    }
   ],
   "source": [
    "# test\n",
    "\n",
    "G1 = Graphe()\n",
    "G1.ajouter_arete(\"A\",\"B\")\n",
    "G1.ajouter_arete(\"A\",\"D\")\n",
    "G1.ajouter_arete(\"B\",\"C\")\n",
    "G1.ajouter_arete(\"D\",\"B\")\n",
    "\n",
    "\n",
    "print(\"Sommets du graphe : \",G1.sommets())\n",
    "print(\"Voisins de A : \",G1.voisins(\"A\"))\n",
    "print(\"Voisins de B : \",G1.voisins(\"B\"))\n",
    "print(\" A et B sont reliés :\", G1.est_arete(\"A\",\"B\"))\n",
    "print(\" D et D sont reliés :\", G1.est_arete(\"B\",\"D\"))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'NoneType' object is not iterable",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_5944/4214906855.py\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;31m# Code qui utilise networkx pour afficher le graphe\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mG1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_5944/2605192585.py\u001b[0m in \u001b[0;36m__repr__\u001b[1;34m(self)\u001b[0m\n\u001b[0;32m     28\u001b[0m         \u001b[1;34m\"\"\"Affichage du graphe en utilisant le module networkx\"\"\"\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     29\u001b[0m         \u001b[0mG\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mnetworkx\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mGraph\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 30\u001b[1;33m         \u001b[1;32mfor\u001b[0m \u001b[0ms1\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0msommets\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     31\u001b[0m             \u001b[1;32mfor\u001b[0m \u001b[0ms2\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mvoisins\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ms1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     32\u001b[0m                 \u001b[0mG\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0madd_edge\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ms1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0ms2\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mTypeError\u001b[0m: 'NoneType' object is not iterable"
     ]
    }
   ],
   "source": [
    "# Code qui utilise networkx pour afficher le graphe\n",
    "print(G1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-warning\" role=\"alert\">\n",
    "    \n",
    "## Exercice 2\n",
    "Utilisez la classe précédente pour créer le graphe ci-dessous.\n",
    "</div>\n",
    "\n",
    "![Méthodes](https://nc-lycees.netocentre.fr/s/JFMCabYi72yJSA6/preview)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre code ici.\n",
    "G2=Graphe()\n",
    "pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test de validation\n",
    "# affichage des sommets\n",
    "pass\n",
    "# affichage des voisins de \"d\"\n",
    "pass\n",
    "# affichage de chaque sommet et ses voisins\n",
    "pass\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(G2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-warning\" role=\"alert\">\n",
    "    \n",
    "## Exercice 3\n",
    "Ecrire des fonctions qui permettent :\n",
    "\n",
    "1. d'afficher le nombre de sommets d'un graphe g passé en paramètre\n",
    "2. d'afficher le nombre d'arêtes d'un graphe passé en paramètre\n",
    "3. le degré d'un sommet passé en paramètre\n",
    "4. le sommet de plus haut degré d'un graphe passé en paramètre\n",
    "    \n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre code ici :\n",
    "# Question 1.\n",
    "def nb_sommets(g):\n",
    "    pass\n",
    "\n",
    "# Question 2.\n",
    "def nb_aretes(g):\n",
    "    pass\n",
    "\n",
    "# Question 3.\n",
    "def degre(g,s):\n",
    "    pass\n",
    "\n",
    "# Question 4.\n",
    "\n",
    "def maxdegre(g):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p> Ecrire des tests avec chaque fonction avec les graphes définis ci dessus </p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implémentation sous forme de matrice d'adjacence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-warning\" role=\"alert\">\n",
    "    \n",
    "## Exercice 4\n",
    "Compléter la classe `Graphe_M` ci-dessous. \n",
    "    On utilisera une matrice d'adjacence pour stocker les arêtes entre les différents sommets.  \n",
    "    La taille de la matrice sera spécifiée lors de la création du graphe via le paramètre `n`  \n",
    "    Les sommets sont accessible par leur indice (de 0 à n-1)\n",
    "    \n",
    "Attention, comme le graphe n'est pas orienté, si A et B sont adjacents, il faudra faire une arête de A vers B et aussi de B vers A.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graphe_M:    \n",
    "    def __init__(self,n:int):\n",
    "        self.n = n # taille de la matrice \n",
    "        self.mat_adj = [[False]*n for i in range(n)]\n",
    "        \n",
    "    def ajouter_arete(self, i_s1,i_s2):\n",
    "        \"\"\" ajoute une arète entre le sommet d'indice i_s1 et le sommet d'indice i_s2\"\"\"\n",
    "        pass\n",
    "        \n",
    "    def est arete(self,i_s1,i_s2):\n",
    "        \"\"\" renvoie vrai s'il existe une arete entre le sommet d'indice i_s1 et le sommet d'indice i_s2, faux sinon\"\"\"\n",
    "        pass\n",
    "    \n",
    "    def voisins(self,i_s):\n",
    "        \"\"\" renvoie la liste des indices des voisins du sommet i_s\"\"\"\n",
    "        pass\n",
    "    \n",
    "    def __str__(self): \n",
    "        \"Affichage du graphe en utilisant le module networkx\"\n",
    "        G = networkx.Graph()\n",
    "        for s1 in range(self.n):\n",
    "            for s2 in self.voisins(s1):\n",
    "                G.add_edge(s1,s2)\n",
    "        networkx.draw(G, with_labels=True, node_color=\"skyblue\")  \n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exemple\n",
    "G4 = Graphe_M(5)\n",
    "G4.ajouter_arete(0,1)\n",
    "G4.ajouter_arete(0,3)\n",
    "G4.ajouter_arete(1,2)\n",
    "G4.ajouter_arete(3,1)\n",
    "G4.ajouter_arete(2,0)\n",
    "G4.ajouter_arete(1,4)\n",
    "print(G4.voisins(2))\n",
    "print(G4.est_arete(2,3))\n",
    "print(G4.voisins(3))\n",
    "print(G4.est_arete(1,3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(G4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-warning\" role=\"alert\">\n",
    "    \n",
    "## Exercice 5\n",
    "Ecrire des fonctions qui permettent :\n",
    "\n",
    "1. d'afficher le nombre de sommets d'un graphe passé en paramètre\n",
    "2. d'afficher le nombre d'arêtes d'un graphe passé en paramètre\n",
    "3. le degré d'un sommet passé en paramètre\n",
    "4. le sommet de plus haut degré  d'un graphe passé en paramètre\n",
    "    \n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre code ici :\n",
    "# Question 1.\n",
    "def nb_sommetsM(g):\n",
    "    pass\n",
    "\n",
    "# Question 2.\n",
    "def nb_aretesM(g):\n",
    "    pass\n",
    "    \n",
    "\n",
    "# Question 3.\n",
    "def degreM(g,s):\n",
    "    pass\n",
    "\n",
    "# Question 4.\n",
    "\n",
    "def maxdegreM(g):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(nb_sommetsM(G4))\n",
    "print(nb_aretesM(G4))\n",
    "print(degreM(G2,0))\n",
    "print(maxdegreM(G2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> 3. Bonus : Recreer ces classes pour des graphes orientés </h2>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h4> a) Avec un dictionnaire </h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graphe_O :\n",
    "    def __init__(self):\n",
    "        self.adj={}\n",
    "        \n",
    "    def ajouter_sommet(self,s):\n",
    "        if s not in self.adj:\n",
    "            self.adj[s]=set()\n",
    "            \n",
    "    def ajouter_arc(self, s1, s2):\n",
    "        pass\n",
    "        \n",
    "    def est_arc(self,s1,s2):\n",
    "        pass\n",
    "    \n",
    "    def sommets(self):\n",
    "        pass\n",
    "    \n",
    "    def voisins(self,s):\n",
    "        pass\n",
    "       \n",
    "    \n",
    "    def __str__(self): \n",
    "        \"Affichage du graphe en utilisant le module networkx\"\n",
    "        G = networkx.DiGraph()\n",
    "        for s1 in self.sommets():\n",
    "            for s2 in self.voisins(s1):\n",
    "                G.add_edge(s1,s2)\n",
    "        networkx.draw(G, with_labels=True, node_color=\"skyblue\", arrowstyle=\"-|>\")  \n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exemple\n",
    "G5 = Graphe_O()\n",
    "G5.ajouter_arc(\"A\",\"B\")\n",
    "G5.ajouter_arc(\"A\",\"D\")\n",
    "G5.ajouter_arc(\"B\",\"C\")\n",
    "G5.ajouter_arc(\"D\",\"B\")\n",
    "\n",
    "print(\"Sommets du graphe:\",G5.sommets())\n",
    "print(\"Voisins de A:\",G5.voisins(\"A\"))\n",
    "print(\"Voisins de B:\",G5.voisins(\"B\"))\n",
    "print(\"arc entre  A et B :\",G.est_arc(0,1))\n",
    "print(\"arc entre  B et A :\",G.est_arc(1,0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(G5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h4> Avec une matrice d'adjacence :</h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graphe_O_M:    \n",
    "    def __init__(self,n : int):\n",
    "        self.n = n \n",
    "        self.adj = [[False]*n for i in range(n)]\n",
    "        \n",
    "    def ajouter_arc(self, s1, s2):\n",
    "        pass\n",
    "        \n",
    "    def est_arc(self,s1,s2):\n",
    "        pass\n",
    "    \n",
    "    def voisins(self, s):\n",
    "        pass\n",
    "    \n",
    "    def __str__(self): \n",
    "        \"Affichage du graphe en utilisant le module networkx\"\n",
    "        G = networkx.DiGraph()\n",
    "        for s1 in range(self.n):\n",
    "            for s2 in self.voisins(s1):\n",
    "                G.add_edge(s1,s2)\n",
    "        networkx.draw(G, with_labels=True, node_color=\"skyblue\", arrowstyle=\"-|>\",font_size=20)  \n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exemple\n",
    "G6 = Graphe_O_M(4)\n",
    "G6.ajouter_arc(0,1)\n",
    "G6.ajouter_arc(0,3)\n",
    "G6.ajouter_arc(1,2)\n",
    "G6.ajouter_arc(3,1)\n",
    "print(G6.voisins(1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(G6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ecrire un jeu de tests"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}