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.

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.

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.

# Premier exemple

gr1=Graphe()
gr1.ajouter_arete("A", "B")
gr1.ajouter_arete("C", "A")
gr1.ajouter_arete("C", "B")
gr1.show()
# testez ici les méthodes sur gr1
# 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()
# 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.

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
  
# 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.

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()
# 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.
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()
# 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()