#!/usr/bin/env python # coding: utf-8 # # Algorithmes sur les graphes # > Cours NSI Terminale - Thème 5. # - toc: true # - badges: true # - comments: false # - categories: [python, NSI, Terminale, graphes, Algorithmique, POO, TP] # - image: images/nsi5.png # ## TP sur les graphes # # Nous comencerons par introduire la classe Graphe que nous allons compléter au fur à mesure de ce TP. # # Elle reprend un certain nombre de notions vues lors de la découverte des graphes dans la partie *Structures de données*. # # Un graphe y est représenté en interne par un dictionnaire d'adjacence : # - chaque clé est un noeud # - chaque valeur est la liste des noeuds connectés représenté par un tuple (noeud, pondération) # # 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()` # # 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. # In[ ]: from graphviz import Digraph class Graphe(): """Graphe implémenté à l'aide d'un dictionnaire Exemple : {'A': [('M', 65), ('R', 90), ('T', 80)], 'G': [('L', 70)], 'L': [('G', 70), ('P', 230), ('T', 260)], 'M': [('A', 65), ('P', 95), ('R', 90), ('T', 55)], 'P': [('L', 230), ('M', 95), ('T', 130)], 'R': [('A', 90), ('M', 90)], 'T': [('A', 80), ('L', 260), ('M', 55), ('P', 130)]} """ def __init__(self, noeuds = None): """Initialisation avec un graphe vide __noeuds est un dictionnaire - clé = Valeur du noeud (chaine, entier) - valeur = liste d'aretes (clé, poids)""" if noeuds is None: self.__noeuds = dict() else: self.__noeuds = noeuds def importe_matrice(self, matrice, noms): """Importe une matrice d'adjacence""" longueur = len(matrice) for i in range(longueur): self.__noeuds[noms[i]] = [] for j in range(longueur): if matrice[i][j] != 0: self.__noeuds[noms[i]].append((noms[j], matrice[i][j])) def ajouter_noeud(self, nd): """Ajoute un nouveau noeud au graphe""" if not nd in self.__noeuds: self.__noeuds[nd] = [] def ajouter_arete(self, nd1, nd2, poids=1): """Ajoute une arête au graphe si poids n'est pas renseigné, il prendra la valeur 1""" # On s'assure que les arètes existent self.ajouter_noeud(nd1) self.ajouter_noeud(nd2) # On crée la connexion nd1 -> nd2 self.__noeuds[nd1].append((nd2, poids)) def liste_noeuds(self): """Renvoie la liste des noeuds""" nds = list(self.__noeuds.keys()) nds.sort() return nds def voisins(self, nd): """Renvoie la liste des noeuds voisins de nd""" if nd in self.liste_noeuds(): return [a[0] for a in self.__noeuds[nd]] else: return [] def arete(self,nd1, nd2): """Renvoie le poids de l'arete nd1->nd2 ou 0 si pas d'arête""" if nd2 not in self.voisins(nd1): return 0 for a in self.__noeuds[nd1]: if a[0] == nd2: return a[1] def show(self): """Représentation graphique avec graphviz""" dot = Digraph(comment="Graphe", format='svg') for nd in self.liste_noeuds(): dot.node(nd,nd) for a in self.__noeuds[nd]: # Teste si l'arête est orientée if self.arete(a[0], nd) == self.arete(nd, a[0]) : # dessin d'une arête non orientée if a[0]< nd: # On ne dessine qu'une seule arête sur les 2 if a[1] != 1: dot.edge(nd, a[0],label=str(a[1]), dir="none") else: dot.edge(nd, a[0], dir="none") else: # dessin d'une arête orientée if a[1] != 1: dot.edge(nd, a[0],label=str(a[1])) else: dot.edge(nd, a[0]) return dot # En utilisant la commande `help()` vous aurez un résumé des méthodes à votre disposition # dans cette classe. # In[ ]: help(Graphe) # ### Exemples de graphes # # 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. # In[ ]: # Premier exemple gr1=Graphe() gr1.ajouter_arete("A", "B") gr1.ajouter_arete("C", "A") gr1.ajouter_arete("C", "B") gr1.show() # In[ ]: # testez ici les méthodes sur gr1 # In[ ]: # Deuxième exemple : le graphe du cours matrice = [[0,1,1,0,0,0,0,0], [1,0,0,1,1,0,0,0], [1,0,0,1,0,0,0,0], [0,1,1,0,1,0,0,0], [0,1,0,1,0,1,1,0], [0,0,0,0,1,0,1,0], [0,0,0,0,1,1,0,1], [0,0,0,0,0,0,1,0]] gr2 = Graphe() gr2.importe_matrice(matrice, ["A", "B", "C", "D", "E", "F", "G", "H"]) gr2.show() # In[ ]: # Testez ici quelques méthodes # ## Parcours en profondeur # # 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`. # In[ ]: class Graphe(): """Graphe implémenté à l'aide d'un dictionnaire Exemple : {'A': [('M', 65), ('R', 90), ('T', 80)], 'G': [('L', 70)], 'L': [('G', 70), ('P', 230), ('T', 260)], 'M': [('A', 65), ('P', 95), ('R', 90), ('T', 55)], 'P': [('L', 230), ('M', 95), ('T', 130)], 'R': [('A', 90), ('M', 90)], 'T': [('A', 80), ('L', 260), ('M', 55), ('P', 130)]} """ def __init__(self, noeuds = None): """Initialisation avec un graphe vide __noeuds est un dictionnaire - clé = Valeur du noeud (chaine, entier) - valeur = liste d'aretes (clé, poids)""" if noeuds is None: self.__noeuds = dict() else: self.__noeuds = noeuds def importe_matrice(self, matrice, noms): """Importe une matrice d'adjacence""" longueur = len(matrice) for i in range(longueur): self.__noeuds[noms[i]] = [] for j in range(longueur): if matrice[i][j] != 0: self.__noeuds[noms[i]].append((noms[j], matrice[i][j])) def ajouter_noeud(self, nd): """Ajoute un nouveau noeud au graphe""" if not nd in self.__noeuds: self.__noeuds[nd] = [] def ajouter_arete(self, nd1, nd2, poids=1): """Ajoute une arête au graphe si poids n'est pas renseigné, il prendra la valeur 1""" # On s'assure que les arètes existent self.ajouter_noeud(nd1) self.ajouter_noeud(nd2) # On crée la connexion nd1 -> nd2 self.__noeuds[nd1].append((nd2, poids)) def liste_noeuds(self): """Renvoie la liste des noeuds""" nds = list(self.__noeuds.keys()) nds.sort() return nds def voisins(self, nd): """Renvoie la liste des noeuds voisins de nd""" if nd in self.liste_noeuds(): return [a[0] for a in self.__noeuds[nd]] else: return [] def arete(self,nd1, nd2): """Renvoie le poids de l'arete nd1->nd2 ou 0 si pas d'arête""" if nd2 not in self.voisins(nd1): return 0 for a in self.__noeuds[nd1]: if a[0] == nd2: return a[1] def show(self): """Représentation graphique avec graphviz""" dot = Digraph(comment="Graphe", format='svg') for nd in self.liste_noeuds(): dot.node(nd,nd) for a in self.__noeuds[nd]: # Teste si l'arête est orientée if self.arete(a[0], nd) == self.arete(nd, a[0]) : # dessin d'une arête non orientée if a[0]< nd: # On ne dessine qu'une seule arête sur les 2 if a[1] != 1: dot.edge(nd, a[0],label=str(a[1]), dir="none") else: dot.edge(nd, a[0], dir="none") else: # dessin d'une arête orientée if a[1] != 1: dot.edge(nd, a[0],label=str(a[1])) else: dot.edge(nd, a[0]) return dot def parcours_profondeur(self, depart): """Parcourt l'arbre en profondeur""" def dfs(nd): # YOUR CODE HERE raise NotImplementedError() deja_vu = [] # noeuds déjà visités dfs(depart) return deja_vu # In[ ]: # Testez votre classe matrice = [[0,1,1,0,0,0,0,0], [1,0,0,1,1,0,0,0], [1,0,0,1,0,0,0,0], [0,1,1,0,1,0,0,0], [0,1,0,1,0,1,1,0], [0,0,0,0,1,0,1,0], [0,0,0,0,1,1,0,1], [0,0,0,0,0,0,1,0]] gr2 = Graphe() gr2.importe_matrice(matrice, ["A", "B", "C", "D", "E", "F", "G", "H"]) assert set(gr2.parcours_profondeur("A")) == {'A', 'B', 'D', 'C', 'E', 'F', 'G', 'H'} # ## Parcours en largeur # # 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. # In[ ]: class Graphe(): """Graphe implémenté à l'aide d'un dictionnaire Exemple : {'A': [('M', 65), ('R', 90), ('T', 80)], 'G': [('L', 70)], 'L': [('G', 70), ('P', 230), ('T', 260)], 'M': [('A', 65), ('P', 95), ('R', 90), ('T', 55)], 'P': [('L', 230), ('M', 95), ('T', 130)], 'R': [('A', 90), ('M', 90)], 'T': [('A', 80), ('L', 260), ('M', 55), ('P', 130)]} """ def __init__(self, noeuds = None): """Initialisation avec un graphe vide __noeuds est un dictionnaire - clé = Valeur du noeud (chaine, entier) - valeur = liste d'aretes (clé, poids)""" if noeuds is None: self.__noeuds = dict() else: self.__noeuds = noeuds def importe_matrice(self, matrice, noms): """Importe une matrice d'adjacence""" longueur = len(matrice) for i in range(longueur): self.__noeuds[noms[i]] = [] for j in range(longueur): if matrice[i][j] != 0: self.__noeuds[noms[i]].append((noms[j], matrice[i][j])) def ajouter_noeud(self, nd): """Ajoute un nouveau noeud au graphe""" if not nd in self.__noeuds: self.__noeuds[nd] = [] def ajouter_arete(self, nd1, nd2, poids=1): """Ajoute une arête au graphe si poids n'est pas renseigné, il prendra la valeur 1""" # On s'assure que les arètes existent self.ajouter_noeud(nd1) self.ajouter_noeud(nd2) # On crée la connexion nd1 -> nd2 self.__noeuds[nd1].append((nd2, poids)) def liste_noeuds(self): """Renvoie la liste des noeuds""" nds = list(self.__noeuds.keys()) nds.sort() return nds def voisins(self, nd): """Renvoie la liste des noeuds voisins de nd""" if nd in self.liste_noeuds(): return [a[0] for a in self.__noeuds[nd]] else: return [] def arete(self,nd1, nd2): """Renvoie le poids de l'arete nd1->nd2 ou 0 si pas d'arête""" if nd2 not in self.voisins(nd1): return 0 for a in self.__noeuds[nd1]: if a[0] == nd2: return a[1] def show(self): """Représentation graphique avec graphviz""" dot = Digraph(comment="Graphe", format='svg') for nd in self.liste_noeuds(): dot.node(nd,nd) for a in self.__noeuds[nd]: # Teste si l'arête est orientée if self.arete(a[0], nd) == self.arete(nd, a[0]) : # dessin d'une arête non orientée if a[0]< nd: # On ne dessine qu'une seule arête sur les 2 if a[1] != 1: dot.edge(nd, a[0],label=str(a[1]), dir="none") else: dot.edge(nd, a[0], dir="none") else: # dessin d'une arête orientée if a[1] != 1: dot.edge(nd, a[0],label=str(a[1])) else: dot.edge(nd, a[0]) return dot # YOUR CODE HERE raise NotImplementedError() # In[ ]: # Testez votre classe matrice = [[0,1,1,0,0,0,0,0], [1,0,0,1,1,0,0,0], [1,0,0,1,0,0,0,0], [0,1,1,0,1,0,0,0], [0,1,0,1,0,1,1,0], [0,0,0,0,1,0,1,0], [0,0,0,0,1,1,0,1], [0,0,0,0,0,0,1,0]] gr2 = Graphe() gr2.importe_matrice(matrice, ["A", "B", "C", "D", "E", "F", "G", "H"]) assert set(gr2.parcours_largeur("A")) == {'A', 'B', 'D', 'C', 'E', 'F', 'G', 'H'} # ## Chercher les cycles # # 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 # contient un cycle ou non. # # Vous implémenterez pour cela des parcours en largeur légèrement modifié # - pour partir de tous les noeuds possibles # - pour détecter si à un moment donné du parcours on atteint le noeud de départ. # In[ ]: class Graphe(): """Graphe implémenté à l'aide d'un dictionnaire Exemple : {'A': [('M', 65), ('R', 90), ('T', 80)], 'G': [('L', 70)], 'L': [('G', 70), ('P', 230), ('T', 260)], 'M': [('A', 65), ('P', 95), ('R', 90), ('T', 55)], 'P': [('L', 230), ('M', 95), ('T', 130)], 'R': [('A', 90), ('M', 90)], 'T': [('A', 80), ('L', 260), ('M', 55), ('P', 130)]} """ def __init__(self, noeuds = None): """Initialisation avec un graphe vide __noeuds est un dictionnaire - clé = Valeur du noeud (chaine, entier) - valeur = liste d'aretes (clé, poids)""" if noeuds is None: self.__noeuds = dict() else: self.__noeuds = noeuds def importe_matrice(self, matrice, noms): """Importe une matrice d'adjacence""" longueur = len(matrice) for i in range(longueur): self.__noeuds[noms[i]] = [] for j in range(longueur): if matrice[i][j] != 0: self.__noeuds[noms[i]].append((noms[j], matrice[i][j])) def ajouter_noeud(self, nd): """Ajoute un nouveau noeud au graphe""" if not nd in self.__noeuds: self.__noeuds[nd] = [] def ajouter_arete(self, nd1, nd2, poids=1): """Ajoute une arête au graphe si poids n'est pas renseigné, il prendra la valeur 1""" # On s'assure que les arètes existent self.ajouter_noeud(nd1) self.ajouter_noeud(nd2) # On crée la connexion nd1 -> nd2 self.__noeuds[nd1].append((nd2, poids)) def liste_noeuds(self): """Renvoie la liste des noeuds""" nds = list(self.__noeuds.keys()) nds.sort() return nds def voisins(self, nd): """Renvoie la liste des noeuds voisins de nd""" if nd in self.liste_noeuds(): return [a[0] for a in self.__noeuds[nd]] else: return [] def arete(self,nd1, nd2): """Renvoie le poids de l'arete nd1->nd2 ou 0 si pas d'arête""" if nd2 not in self.voisins(nd1): return 0 for a in self.__noeuds[nd1]: if a[0] == nd2: return a[1] def show(self): """Représentation graphique avec graphviz""" dot = Digraph(comment="Graphe", format='svg') for nd in self.liste_noeuds(): dot.node(nd,nd) for a in self.__noeuds[nd]: # Teste si l'arête est orientée if self.arete(a[0], nd) == self.arete(nd, a[0]) : # dessin d'une arête non orientée if a[0]< nd: # On ne dessine qu'une seule arête sur les 2 if a[1] != 1: dot.edge(nd, a[0],label=str(a[1]), dir="none") else: dot.edge(nd, a[0], dir="none") else: # dessin d'une arête orientée if a[1] != 1: dot.edge(nd, a[0],label=str(a[1])) else: dot.edge(nd, a[0]) return dot # YOUR CODE HERE raise NotImplementedError() # In[ ]: # Testez votre classe matrice = [[0,1,1,0,0,0,0,0], [1,0,0,1,1,0,0,0], [1,0,0,1,0,0,0,0], [0,1,1,0,1,0,0,0], [0,1,0,1,0,1,1,0], [0,0,0,0,1,0,1,0], [0,0,0,0,1,1,0,1], [0,0,0,0,0,0,1,0]] gr2 = Graphe() gr2.importe_matrice(matrice, ["A", "B", "C", "D", "E", "F", "G", "H"]) assert gr2.cycle() # In[ ]: