LesGraphes_2020_partie9.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "5Tv2duaSSfZH"
   },
   "source": [
    "\n",
    " Structure de données 2 : Les Graphes#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "MBn9rl7EzXJ0"
   },
   "source": [
    "## **9. Implémentation en pratique (en Python)**\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "gRD9kFq4zVcO"
   },
   "source": [
    "**Comment choisir l'implémentation à utiliser (matrice d'adjacence ou liste d'adjacence) ?**\n",
    "\n",
    "\n",
    "  le choix se fait en fonction de la densité du graphe, c'est-à-dire du rapport entre le nombre d'arêtes et le nombre de sommets. Pour un graphe dense on utilisera plutôt une matrice d'adjacence.\n",
    "\n",
    "  Certains algorithmes travaillent plutôt avec les listes d'adjacences alors que d'autres travaillent plutôt avec les matrices d'adjacences. Le choix doit donc aussi dépendre des algorithmes utilisés (nous aurons très prochainement l'occasion d'étudier plusieurs de ces algorithmes).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "iOoEG3wR0Lsr"
   },
   "source": [
    "**Implémenter les graphes :**\n",
    "\n",
    "Comme les listes, les piles, et les files, il est important de distinguer le type abstrait de représentation des données, du type implémenté dans le langage.\n",
    "\n",
    "En Python il n'existe pas de type GRAPHE prédéfini. C'est donc à chacun de l'implémenter avec les outils disponibles dans le langage.\n",
    "\n",
    "Comme pour les listes il peut exister, selon les auteurs, des différences sur le nombre et la définition des primitives de bases. Nous allons utiliser ici ce jeu de primitives :  \n",
    "\n",
    "- `creerGrapheVide()` : retourne un graphe vide\n",
    "- `estVideGraphe(G)` : retourne True si G est un graphe vide\n",
    "- `ajouterSommet(G,s)` : retourne le graphe après ajout du sommet s\n",
    "- `supprimerSommet(G,s)` : retourne le graphe après suppression du sommet s (et tout les arcs rliés à s)\n",
    "- `existeSommet(G,s)` : retourne True si s est un sommet du graphe G  \n",
    "  \n",
    "  \n",
    "    \n",
    "- Pour un graphe orienté :\n",
    "  - `ajouterArc(G,sd,sa)` : retourne le graphe après ajout d'un arc reliant sd à sa (orienté)\n",
    "  - `supprimerArc(G,sd,sa)` : retourne le graphe après suppression de l'arc sd->sa\n",
    "  - `existeArc(G,sd,sa)` : retourne True si sd->sa est un arc du graphe G\n",
    "- Pour un graphe non orienté :\n",
    "  - `ajouterArete(G,sd,sa)` : retourne le graphe après ajout d'une arête reliant sd à sa (non-orienté)\n",
    "  - `supprimerArete(G,sd,sa)` : retourne le graphe après suppression de l'arête sd->sa\n",
    "  - `existeArete(G,sd,sa)` : retourne True si sd->sa est une arête du graphe G\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "4VGUcrZe0Y06"
   },
   "source": [
    "**Une première implémentation avec un dictionnaire**\n",
    "\n",
    "Comme nous l'avons vu, un graphe peut être représenté par une liste d'adjacence. Cette représentation peut être implémentée efficacement avec un dictionnaire. Chaque sommet sera donc une clé dictionnaire, et sa valeur sera la liste des sommets sa reliés à s dans le sens s -> sa.\n",
    "\n",
    "En conséquence, un graphe vide est un dictionnaire vide."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "pE9ZlDsF0bJs"
   },
   "outputs": [],
   "source": [
    "def creerGrapheVide() -> dict:\n",
    "    return {}\n",
    "def estVideGraphe(G : dict) -> bool :\n",
    "    return G=={}\n",
    "def ajouterSommet(G : dict , s ) -> dict : #s peut être str ou int\n",
    "    assert s not in G,'Vous ne pouvez pas ajouter un sommet déjà existant'\n",
    "    G[s]=[]\n",
    "def ajouterArc(G : dict ,sd,sa) -> dict : #sd et sa peuvent être str ou int\n",
    "    assert sd in G ,'le graphe ne contient pas le sommet  de depart '\n",
    "    assert sa in G ,'le graphe ne contient pas le sommet  arrivee '\n",
    "    G[sd].append(sa)\n",
    "def supprimerSommet(G : dict , s ) -> dict:  #s peut être str ou int\n",
    "    assert s in G,'le graphe ne contient pas le sommet '\n",
    "    del G[s]\n",
    "    for sommet in G.keys() :\n",
    "        if s in G[sommet] :\n",
    "            G[sommet].remove(s)\n",
    "def supprimerArc(G : dict,sd,sa) -> dict : # sd et sa peuvent etre int ou str \n",
    "    assert sd in G,'le graphe ne contient pas le sommet '\n",
    "    assert sa in G,'le graphe ne contient pas le sommet dcarrivee'\n",
    "    assert sa in G[sd] , 'l arc  n existe pas.'\n",
    "    G[sd].remove(sa)\n",
    "def existeSommet(G : dict ,s) -> bool :  #s peut être str ou int\n",
    "    return s in G\n",
    "def existeArc(G : dict ,sd,sa) -> bool :  #sd et sa peuvent être str ou int\n",
    "    return sd in G and sa in G[sd]\n",
    "\n",
    "G=creerGrapheVide()\n",
    "ajouterSommet(G,'A')\n",
    "ajouterSommet(G,'B')\n",
    "ajouterSommet(G,'C')\n",
    "ajouterSommet(G,'D')\n",
    "ajouterArc(G,'A','B')\n",
    "ajouterArc(G,'C','D')\n",
    "\n",
    "print('après ajout des 4 sommets et des arcs A->B et C->D:\\nG = ',G)\n",
    "\n",
    "print('A dans G ? :',existeSommet(G,'A'))\n",
    "print('A->B dans G ? :',existeArc(G,'A','B'))\n",
    "supprimerArc(G,'A','B')\n",
    "print('A->B dans G après suppression ? :',existeArc(G,'A','B'))\n",
    "\n",
    "supprimerSommet(G,'D')\n",
    "\n",
    "print('Après suppression du sommet D\\n G = ',G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "kC4_Wwgx3Egi"
   },
   "source": [
    "**Exercice 1 : Implémenter un graphe**\n",
    "\n",
    "En utilisant l'implémentation de l'exemple précédant, créez le dictionnaire G correspondant au graphe ci-dessous. Votre code doit afficher le dictionnaire correspondant à ce graphe. \n",
    "\n",
    "implémentation avec dictionnaire\n",
    "<img src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/2/23/Directed_graph_no_background.svg/1920px-Directed_graph_no_background.svg.png\" width=\"300\" height=\"300\" />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "t0CE7iry362I"
   },
   "outputs": [],
   "source": [
    "def creerGrapheVide() -> dict:\n",
    "    return {}\n",
    "def estVideGraphe(G : dict) -> bool :\n",
    "    return G=={}\n",
    "def ajouterSommet(G : dict , s ) -> dict : #s peut être str ou int\n",
    "    assert s not in G.keys(),'vous ne pouvez pas ajouter un sommet déjà existant'\n",
    "    G[s]=[]\n",
    "def ajouterArc(G : dict , sd , sa ) -> dict : #sa et sd peuvent être str ou int\n",
    "    assert sd in G ,'le graphe ne contient pas le sommet de depart '\n",
    "    assert sa in G ,'le graphe ne contient pas le sommet d arrivee'\n",
    "    G[sd].append(sa)\n",
    "def supprimerSommet(G : dict , s ) -> dict : #s peut être str ou int\n",
    "    assert s in G,'le graphe ne contient pas le sommet '\n",
    "    del G[s]\n",
    "    for sommet in G.keys() :\n",
    "        if s in G[sommet] :\n",
    "            G[sommet].remove(s)\n",
    "def supprimerArc(G : dict ,sd , sa ) -> dict: #sd et sa peuvent être str ou int\n",
    "    assert sd in G,'le graphe ne contient pas le sommet de depart '\n",
    "    assert sa in G,'le graphe ne contient pas le sommet '\n",
    "    assert sa in G[sd] , 'l arc  n existe pas.'\n",
    "    G[sd].remove(sa)\n",
    "def existeSommet(G : dict , s ) -> bool:\n",
    "    return s in G\n",
    "def existeArc(G : dict , sd  , sa ) -> bool: #sd et sa peuvent être str ou int\n",
    "    return sd in G and sa in G and sa in G[sd]\n",
    "\n",
    "G=creerGrapheVide()\n",
    "# complétez ici\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Visualiser un graphe orienté :**  \n",
    "Il est pratique de visualiser un graphe implémenté par exemple sous forme de dictionnaire.  \n",
    "Pour cela nous allons utiliser la bibliothèque networkx. Vous pouvez lire un documentation ici : [https://networkx.github.io/documentation/stable/reference/introduction.html]  \n",
    "Voici un exemple qui montre comment créer un graphe orienté de type networkx, et qui l'affiche"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "\n",
    "def cree_graphe_oriente_nx(dictionnaire: dict) -> nx.DiGraph:\n",
    "    \"\"\"\n",
    "    Cette fonction premet de transformer une représentation en dictionnaire en\n",
    "    une représentation «complexe» d'un objet graphe orienté.\n",
    "\n",
    "    - Précondition : l'entrée est un dictionnaire\n",
    "    - Postcondition : la sortie est un graphe orienté (DiGraph) de Networkx\n",
    "    \"\"\"\n",
    "    G = nx.DiGraph()  # pour un graph non oriente :  G = nx.Graph()\n",
    "    for sommets in dictionnaire.keys():\n",
    "        G.add_node(sommets) # Creation des sommets\n",
    "    for sommet in dictionnaire:\n",
    "        for sommets_adjacents in dictionnaire[sommet]:\n",
    "            G.add_edge(sommet, sommets_adjacents) # Creation des arcs\n",
    "    return G\n",
    "\n",
    "\n",
    "gr = {1: [2, 3], 2: [], 3: [2, 4], 4: [3]}\n",
    "G=cree_graphe_oriente_nx(gr)\n",
    "# Pour une representation circulaire : nx.draw_circular(G,with_labels=True)\n",
    "nx.draw(G,with_labels=True) # Pour une representation classique\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "XsMJsY5S7ced"
   },
   "source": [
    "**Exercice 2 : Modifier l'implémentation pour modéliser un graphe non orienté (primitives d'ajout)** \n",
    "\n",
    "Vous allez modifier notre première implémentation pour modéliser un graphe non orienté.\n",
    "\t\n",
    "\n",
    "  Dans la version d'implémentation fournie ci-dessous, on a remplacé la primitives ajouterArc par ajouterArete, mais on a pas modifié le code de cette primitive. Vous devez le faire vous même : dans le cas d'un graphe non orienté, ajouter une arrête SD-SA revient à ajouter SD dans la liste d'ajacence de SA, et SA dans la liste d'adjacence de SD. Le code doit donc faire le travail correctement.\n",
    "\n",
    "  Dans cet exercice nous n'incluerons que les primitives d'ajout de sommets et d'arêtes, les primitives pour retirer seront traitées dans un second temps.  \n",
    "  \n",
    "  Compléter également la fonction existeArete\n",
    "\n",
    "En modifiant l'implémentation de l exemple précédant, créez le dictionnaire G correspondant au graphe ci-dessous.Les instructions données en fin de code devraient afficher le dictionnaire correct, si vos primitives ont été modifiées comme attendu.\n",
    "\n",
    "![](https://upload.wikimedia.org/wikipedia/commons/thumb/b/b2/Ungerichteter_Graph_mit_4_Knoten_und_3_Kanten.svg/220px-Ungerichteter_Graph_mit_4_Knoten_und_3_Kanten.svg.png)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "3gCVKTmu8GNF"
   },
   "outputs": [],
   "source": [
    "def  creerGrapheVide() -> dict:\n",
    "     return {}\n",
    "def ajouterSommet(G : dict , s ) -> dict : #s peut être str ou int\n",
    "    assert s not in G.keys(),'vous ne pouvez pas ajouter un sommet déjà existant'\n",
    "    G[s]=[]\n",
    "def ajouterArete(G : dict , sd , sa ) -> dict : #sa et sd peuvent être str ou int\n",
    "    assert sd in G ,'le graphe ne contient pas le sommet de depart '\n",
    "    assert sa in G ,'le graphene contient pas le sommet d arrivee'\n",
    "    G[sd].append(sa)\n",
    "    #completer\n",
    "\n",
    "def existeSommet(G : dict , s ) -> bool:\n",
    "    return s in G\n",
    "def existeArete(G : dict , sd  , sa ) -> bool: #sd et sa peuvent être str ou int\n",
    "    return sd in G and sa in G and sa in G[sd] # completer\n",
    "\n",
    "G=creerGrapheVide()\n",
    "# complétez ici\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Visualiser un graphe non orienté**  \n",
    "De même que précédemment, la bibliothèque networkx permet de visualiser un graphe non orienté."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cree_graphe_non_oriente_nx(dictionnaire: dict) -> nx.Graph:\n",
    "    \"\"\"\n",
    "    Cette fonction premet de transformer une représentation en dictionnaire en\n",
    "    une représentation «complexe» d'un objet graphe orienté.\n",
    "\n",
    "    - Précondition : l'entrée est un dictionnaire\n",
    "    - Postcondition : la sortie est un graphe orienté (Graph) de Networkx\n",
    "    \"\"\"\n",
    "    Gnx = nx.Graph() \n",
    "    for sommets in dictionnaire.keys():\n",
    "        Gnx.add_node(sommets) # Creation des sommets\n",
    "    for sommet in dictionnaire.keys():\n",
    "        for sommets_adjacents in dictionnaire[sommet]:\n",
    "            Gnx.add_edge(sommet, sommets_adjacents) # Creation des arcs\n",
    "    return Gnx\n",
    "\n",
    "G=creerGrapheVide()\n",
    "for i in range(1,5):\n",
    "    ajouterSommet(G,i)\n",
    "ajouterArete(G,1,2)\n",
    "ajouterArete(G,2,3)\n",
    "ajouterArete(G,2,4)\n",
    "print(G)\n",
    "G1=cree_graphe_non_oriente_nx(G)\n",
    "# Pour une representation circulaire : nx.draw_circular(G,with_labels=True)\n",
    "nx.draw(G1,with_labels=True) # Pour une representation classique\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "3TbSjZiF8Un_"
   },
   "source": [
    "**Exercice 3 : Modifier l'implémentation pour modéliser un graphe non orienté (primitives de suppression)** \n",
    "\n",
    "Vous allez compléter l'implémentation pour modéliser un graphe non orienté.\n",
    "\t\n",
    "\n",
    "  Comme dans l'exercice 2 ci-dessus, dans la version d'implémentation fournie ci-dessous, on a remplacé la primitive supprimerArc par supprimerArete, mais on a pas modifié le code de cette primitive. Vous devez le faire vous même : dans le cas d'un graphe non orienté, supprimer une arrête SD-SA revient à modifier les listes d'adjacence des deux sommets SD et SA. Le code doit donc faire le travail correctement.\n",
    "  \n",
    "  Dans cet exercice nous n'incluerons que les primitives de suppression, nous allons générer pour vous un objet graphe qui sera utilisé pour tester votre code. Vous devez coder supprimerSommet et supprimerArete et utiliser ces 2 primitives pour supprimer le sommet 'A' et l’arête 'B-C' du graphe généré par le système.\n",
    "\n",
    "Modifiez les primitives supprimerSommet et supprimerArete. Puis utilisez les pour supprimer le sommet A et l'arrête B-C du graphe suivant :\n",
    "\n",
    "**G={'A': ['B'], 'B': ['A', 'C', 'D'], 'C': ['B','D'], 'D': ['B','C']}**\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "hQm-aZvc9Lbc"
   },
   "outputs": [],
   "source": [
    "def existeSommet(G : dict,s) -> bool: # s peut être str ou int\n",
    "    return s in G\n",
    "\n",
    "def existeArete(G : dict ,sd,sa) -> bool : # sd et sa peuvent être str ou int\n",
    "    return sd in G and sa in G[sd] # completer\n",
    "\n",
    "def supprimerSommet(G : dict,s) -> dict : # s peut être str ou int\n",
    "    pass # remplacez cette ligne par votre implémentation (pensez aux assert)\n",
    "\n",
    "def supprimerArete(G : dict,sd,sa) -> dict : # sd et sa peuvent être str ou int\n",
    "    pass # remplacez cette ligne par votre implémentation (pensez aux assert)\n",
    "\n",
    "G={'A': ['B'], 'B': ['A', 'C', 'D'], 'C': ['B','D'], 'D': ['B','C']}\n",
    "# insérez ici les instructions pour supprimer A puis supprimer B-C\n",
    "\n",
    "\n",
    "print(str(G))\n",
    "G_nx=cree_graphe_non_oriente_nx(G)\n",
    "# Pour une representation circulaire : nx.draw_circular(G,with_labels=True)\n",
    "nx.draw(G_nx,with_labels=True) # Pour une representation classique\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "l7fLENcD-g_r"
   },
   "source": [
    "**Exercice 4 : Modifier de nouveau l'implémentation pour modéliser un graphe pondéré non orienté** \n",
    "\n",
    "Vous allez modifier de nouveau l'implémentation pour modéliser un graphe pondéré et non orienté.\n",
    "\n",
    "En modifiant de nouveau l'implémentation du graphe, créez le dictionnaire G correspondant au graphe pondéré non orienté ci-dessous.\n",
    "\n",
    "Attention, ici vous devez modifier les primitives mais aussi les instructions pour créer le graphe attendu.\n",
    "\n",
    "Les clé resteront les sommets. La  valeur correspondant à chaque sommet ne sera plus une liste d’adjacence, mais un dictionnaires dont les clés seront les sommets d'arrivée des arêtes, et les valeurs le poids de chaque arête.  \n",
    "Par exemple: pour le graphe ci-dessous :  \n",
    "G1 = {1: {2: 1, 5: 5}, 2: {1: 1, 5: 6, 3: 2}, 3: {2: 2, 4: 3}, 4: {5: 4, 3: 3}, 5: {1: 5, 2: 6, 4: 4}}.  \n",
    "<img src=\"graphe_non_or_pond.png\" width=\"200\" height=\"200\" />\n",
    "\n",
    "Il faut donc modifier :  \n",
    "- `ajouterSommet` (la valeur de la clé s doit être un dictionnaire)   \n",
    "- `ajouterArete` (pour ajouter un dictionnaire, et non plus une liste). \n",
    "- `supprimerArete` devra aussi être modifiée pour tenir comte de la structure différente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def  creerGrapheVide() -> dict:\n",
    "    return {}\n",
    "def estVideGraphe(G: dict) -> bool:\n",
    "    return G=={}\n",
    "def ajouterSommet(G : dict,s) : # s est str ou int\n",
    "    pass\n",
    "def ajouterArete(G : dict , sd , sa, pds) -> dict :  # sd et sa sont str ou int\n",
    "    pass\n",
    "def supprimerSommet(G : dict , s ) : # s est str ou int\n",
    "    pass\n",
    "def supprimerArete(G : dict , sd , sa) -> dict :  # sd et sa sont str ou int \n",
    "    pass\n",
    "def existeSommet(G : dict , s ) -> bool:  # s est str ou int\n",
    "    return s in G\n",
    "def existeArete(G : dict , sd , sa ) -> bool :  # sd et sa sont str ou int\n",
    "    return sd in G and sa in G[sd]\n",
    "\n",
    "# Completez également les instructions ci-dessous :\n",
    "G=creerGrapheVide()\n",
    "\n",
    "\n",
    "print(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***Jean-Louis THIROT, Mireille COILHAC, Valérie MOUSSEAUX  \n",
    "Ce document est sous licence Creative Commons  Attribution - Pas d’Utilisation Commerciale - \n",
    "Partage dans les Mêmes Conditions 4.0 International.***\n"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "authorship_tag": "ABX9TyOz2rkm7TmUTLQeTaYq/DFI",
   "name": "LesGraphes.ipynb",
   "provenance": [],
   "toc_visible": true
  },
  "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": 1
}