Application des parcours de graphe

On s'intéresse dans ce tp à différentes applications directes des parcours (en profondeur, en largeur) de graphes.

###

Lancer Télécharger Téléverser Recharger Sauvegarder

class Pile:bksl-nl def py-undpy-undinitpy-undpy-und(self, maxpy-undelt = float('inf')):bksl-nl self.contenu = []bksl-nl self.maxpy-undelt = maxpy-undeltbksl-nl self.logpy-undlist = []bksl-nlbksl-nl def py-undpy-undreprpy-undpy-und(self):bksl-nl return "[" + ", ".join(b.py-undpy-undreprpy-undpy-und() for b in self.contenu) + "] (Sommet pile)" bksl-nlbksl-nl def py-undpy-undlenpy-undpy-und(self):bksl-nl return len(self.contenu)bksl-nlbksl-nl def log(self):bksl-nl print("\n".join(self.logpy-undlist))bksl-nlbksl-nl def affiche(self):bksl-nl print(self)bksl-nlbksl-nl def estpy-undvide(self):bksl-nl return self.contenu == []bksl-nlbksl-nl def estpy-undpleine(self):bksl-nl return self.maxpy-undelt == len(self)bksl-nlbksl-nl def empiler(self, c):bksl-nl self.logpy-undlist.append(f"Empile {c}")bksl-nl if self.estpy-undpleine():bksl-nl raise IndexError("Capacité maximale de la pile atteinte")bksl-nl self.contenu.append(c)bksl-nlbksl-nl def depiler(self):bksl-nl if self.estpy-undvide():bksl-nl raise IndexError("Impossible de dépiler : la pile est vide.")bksl-nl c = self.contenu.pop()bksl-nl self.logpy-undlist.append(f"Dépile {c}")bksl-nl return cbksl-nlbksl-nlclass File:bksl-nl def py-undpy-undinitpy-undpy-und(self, maxpy-undelt = float('inf')):bksl-nl self.contenu = []bksl-nl self.maxpy-undelt = maxpy-undeltbksl-nl self.logpy-undlist = []bksl-nlbksl-nl def py-undpy-undreprpy-undpy-und(self):bksl-nl return "(Début file) [" + ", ".join(b.py-undpy-undreprpy-undpy-und() for b in self.contenu) + "]"bksl-nlbksl-nl def py-undpy-undlenpy-undpy-und(self):bksl-nl return len(self.contenu)bksl-nlbksl-nl def log(self):bksl-nl print("\n".join(self.logpy-undlist))bksl-nlbksl-nl def affiche(self):bksl-nl print(self)bksl-nlbksl-nl def estpy-undvide(self):bksl-nl return self.contenu == []bksl-nlbksl-nl def estpy-undpleine(self):bksl-nl return len(self) == self.maxpy-undelt bksl-nlbksl-nl def enfiler(self, b):bksl-nl self.logpy-undlist.append(f"Enfile {b}")bksl-nl if self.estpy-undpleine():bksl-nl raise IndexError("Capacité maximale de la file atteinte")bksl-nl self.contenu.append(b)bksl-nlbksl-nl def defiler(self):bksl-nl if self.estpy-undvide():bksl-nl raise IndexError("Impossible de défiler : la file est vide.")bksl-nl c = self.contenu.pop(0)bksl-nl self.logpy-undlist.append(f"Défile {c}")bksl-nl return cbksl-nlbksl-nlclass Graphe:bksl-nl """ Un graphe représenté par un dictionnaire d'adjacence. """bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl self.adj = dict()bksl-nlbksl-nl def ajouterpy-undsommet(self, s):bksl-nl """ Graphe, str -> Nonetypebksl-nl Ajoute le sommet s au graphe self """bksl-nl # self.adj.setdefault(source, [])bksl-nl if s not in self.adj:bksl-nl self.adj[s] = []bksl-nlbksl-nl def ajouterpy-undarc(self, source, destination):bksl-nl """ Graphe, str, str -> Nonetypebksl-nl Ajoute l'arc source -> destination au graphe self """bksl-nl self.adj[source].append(destination)bksl-nlbksl-nl def estpy-undvoisin(self, source, destination):bksl-nl """ Graphe, str, str -> boolbksl-nl Détermine si source et destination sont voisins """bksl-nl for v in self.adj[source]:bksl-nl if v == destination:bksl-nl return Truebksl-nl return Falsebksl-nl bksl-nl def sommets(self):bksl-nl """ Graphe -> [str]bksl-nl Renvoie la liste des sommets du graphe self """bksl-nl return sorted(list(self.adj.keys()))bksl-nl bksl-nl def voisins(self, s):bksl-nl """ Graphe, stsr -> [str]bksl-nl Renvoie la liste des voisins de sommet """bksl-nl return sorted(self.adj[s])bksl-nl bksl-nl def listepy-undarcs(self):bksl-nl """ Graphe -> [(str, str)]bksl-nl Renvoie la liste des arcs du graphe """bksl-nl arcs = []bksl-nl for u in self.sommets():bksl-nl for v in self.adj[u]:bksl-nl arcs.append((u, v))bksl-nl return arcsbksl-nl bksl-nl def supprimerpy-undarc(self, source, destination):bksl-nl """ Graphe, int, int -> Nonetypebksl-nl Supprime le ou les arcs source -> destination """bksl-nl for i, v in enumerate(self.adj[source]):bksl-nl if v == destination:bksl-nl self.adj[source].pop(i)bksl-nl bksl-nl def supprimerpy-undsommet(self, sommet):bksl-nl """ Graphe, str -> Nonetypebksl-nl Supprime le sommet i du graphe. """bksl-nl for s in self.sommets():bksl-nl self.supprimerpy-undarc(s, sommet)bksl-nl self.adj.pop(sommet)bksl-nl bksl-nl def ordre(self):bksl-nl """ Graphe -> intbksl-nl Renvoie l'ordre du graphe """bksl-nl return len(self.adj)bksl-nl bksl-nl def taille(self):bksl-nl """ Graphe -> intbksl-nl Renvoie la taille du graphe """bksl-nl return len(self.listepy-undarcs())bksl-nl bksl-nl def decrire(self):bksl-nl """ Graphe -> Nonetypebksl-nl Affiche une description du graphe self """bksl-nl print(f"Graphe d'ordre {self.ordre()} et de taille {self.taille()}")bksl-nl for s in self.sommets():bksl-nl print(f"Sommet {s} -> {' '.join(str(i) for i in self.voisins(s))}")bksl-nlbksl-nlclass Ensemble:bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl """ Ensemble -> Nonetype """bksl-nl self.contenu = dict()bksl-nlbksl-nl def ajouter(self, elt):bksl-nl """ Ensemble, elt -> Nonetype """bksl-nl self.contenu[elt] = Truebksl-nlbksl-nl def supprimer(self, elt):bksl-nl """ Ensemble, elt -> Nonetype """bksl-nl self.contenu.pop(elt)bksl-nlbksl-nl def py-undpy-undcontainspy-undpy-und(self, elt):bksl-nl """ Ensemble, elt -> bool """bksl-nl if self.contenu.get(elt):bksl-nl return Truebksl-nl return Falsebksl-nlbksl-nldef arcspy-undverspy-undgraphepy-undo(arcs):bksl-nl """ [(Sommet, Sommet)] -> Graphebksl-nl Sommet peut être de type int ou strbksl-nl Construit le graphe non orienté dont on donne la liste des arêtes. """bksl-nl g = Graphe()bksl-nl for (source, destination) in arcs:bksl-nl g.ajouterpy-undsommet(source)bksl-nl g.ajouterpy-undsommet(destination)bksl-nl g.ajouterpy-undarc(source, destination)bksl-nl return gbksl-nlbksl-nldef arcspy-undverspy-undgraphepy-undno(arcs):bksl-nl """ [(Sommet, Sommet)] -> Graphebksl-nl Sommet peut être de type int ou strbksl-nl Construit le graphe non orienté dont on donne la liste des arêtes. """bksl-nl g = Graphe()bksl-nl for (source, destination) in arcs:bksl-nl g.ajouterpy-undsommet(source)bksl-nl g.ajouterpy-undsommet(destination)bksl-nl g.ajouterpy-undarc(source, destination)bksl-nl g.ajouterpy-undarc(destination, source)bksl-nl return gbksl-nlbksl-nlbksl-nldef parcourspy-undprofondeur(G, depart):bksl-nl """ Graphe, Sommet -> [Sommet]bksl-nl Parcours le graphe G depuis le sommet depart en profondeur """bksl-nl vus = Ensemble()bksl-nl ordrepy-undvisites = []bksl-nl àpy-undexplorer = Pile()bksl-nl àpy-undexplorer.empiler(depart)bksl-nl while not àpy-undexplorer.estpy-undvide():bksl-nl # définition du sommet courant bksl-nl sommet = àpy-undexplorer.depiler()bksl-nl if sommet in vus:bksl-nl continuebksl-nl # opération de traitementbksl-nl vus.ajouter(sommet)bksl-nl ordrepy-undvisites.append(sommet)bksl-nl # ajout des voisins non visitésbksl-nl for destination in reversed(G.voisins(sommet)):bksl-nl if not destination in vus:bksl-nl àpy-undexplorer.empiler(destination)bksl-nl return ordrepy-undvisitesbksl-nlbksl-nldef parcourspy-undlargeur(G, depart):bksl-nl """ Graphe, Sommet -> [Sommet]bksl-nl Parcours le graphe G depuis le sommet depart en largeur """bksl-nl vus = Ensemble()bksl-nl ordrepy-undvisites = []bksl-nl àpy-undexplorer = File()bksl-nl àpy-undexplorer.enfiler(depart)bksl-nl while not àpy-undexplorer.estpy-undvide():bksl-nl # définition du sommet courant bksl-nl sommet = àpy-undexplorer.defiler()bksl-nl if sommet in vus:bksl-nl continuebksl-nl # opération de traitementbksl-nl vus.ajouter(sommet)bksl-nl ordrepy-undvisites.append(sommet)bksl-nl # ajout des voisins non visitésbksl-nl for destination in G.voisins(sommet):bksl-nl if not destination in vus:bksl-nl àpy-undexplorer.enfiler(destination)bksl-nl return ordrepy-undvisitesbksl-nlbksl-nldef oubliepy-undorientation(G):bksl-nl """ Graphe -> Graphebksl-nl Renvoie le graphe non orienté G' dans lequel on a "oublié"bksl-nl le sens des arcs de G """bksl-nl Gp = Graphe()bksl-nl for s in G.sommets():bksl-nl Gp.ajouterpy-undsommet(s)bksl-nl for (source, destination) in G.listepy-undarcs():bksl-nl Gp.ajouterpy-undarc(source, destination)bksl-nl Gp.ajouterpy-undarc(destination, source)bksl-nl return Gpbksl-nlbksl-nlg1 = arcspy-undverspy-undgraphepy-undo([(0, 2), (1, 0), (1, 3),bksl-nl (3, 2), (4, 5), (5, 6), (6, 4)]) bksl-nlg2 = arcspy-undverspy-undgraphepy-undno([(0, 1), (0, 5), (0, 8),bksl-nl (1, 2), (2, 3), (3, 4), (3, 7),bksl-nl (3, 8), (4, 5), (4, 7)])bksl-nlg3 = arcspy-undverspy-undgraphepy-undo([(1, 2), (4, 5), (4, 3), (5, 3)])bksl-nlg3.ajouterpy-undsommet(0)bksl-nlg4 = arcspy-undverspy-undgraphepy-undo([(0, 1), (1, 2), (2, 3), (2, 4),bksl-nl (3, 5), (5, 4), (4, 1)])bksl-nlbksl-nl

Existence de chemin entre deux sommets distincts

Écrire une fonction existe_chemin qui étant donné un graphe G (orienté ou non) et deux sommets source et destination distincts détermine s'il est possible de trouver un chemin dans le graphe G entre le sommet source et le sommet destination. Vous utiliserez pour cela une des fonctions de parcours de graphe écrite précédemment.

###

Lancer def testpy-undexistepy-undchemin():bksl-nl """ Tests pour la fonction existepy-undchemin """bksl-nl print("Tests de existepy-undchemin passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import existepy-undcheminbksl-nl# testpy-undexistepy-undchemin()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def existepy-undchemin(G, sommet, destination):bksl-nl """ Graphe, Sommet, Sommet -> boolbksl-nl Renvoie True si et seulement si il existe un chemin entre source et destination dans G. """bksl-nl passbksl-nlbksl-nl

Composantes connexes d'un graphe non orienté

Écrire une fonction composantes_connexes qui étant donné un graphe G non orienté en détermine les composantes connexes. Cette fonction renverra un dictionnaire définit de la manière suivante :

• k est une clé du dictionnaire si et seulement si k est un sommet de G
• on associera à la clé k un entier représentant le numéro de la composante connexe associée à k. L'entier choisit peut-être arbitraire, mais deux clés k1 et k2 doivent être associé au même entier si et seulement si les sommets k1 et k2 appartiennent à la même composante connexe.

Indication. On pourra utiliser l'algorithme suivant :

• on initialise un dictionnaire composantes ainsi qu'un entier composante_num qui permettront respectivement de mémoriser le numéro de la composante connexe de chaque sommet et le numéro de la dernière composante connexe découverte.
• pour chaque sommet du graphe, on détermine la liste des sommets atteignables depuis sommet à l'aide d'un parcours du graphe depuis sommet.
  • pour chaque sommet atteignable présent dans la liste atteignables, on attribue à atteignable dans le dictionnaire composantes le numéro de la composante connexe de sommet.
  • on prendra soin de mettre à jour convenablement le numéro de la dernière composante connexe découverte ainsi que de ne pas explorer inutilement le graphe depuis les sommets dont on a déjà trouvé la composante connexe.

###

Lancer def testpy-undcomposantespy-undconnexes():bksl-nl """ Tests pour la fonction composantespy-undconnexes """bksl-nl print("Tests de composantespy-undconnexes passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import composantespy-undconnexesbksl-nl# testpy-undcomposantespy-undconnexes()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def composantespy-undconnexes(G):bksl-nl """ Graphe -> {Sommet:int}bksl-nl Détermine les composantes connexes du graphe G sous la forme d'un dictionnaire """bksl-nl passbksl-nlbksl-nl

Repérer la présence d'un cycle dans un graphe orienté

On cherche dans cette question à détecter si un cycle est présent dans un graphe orienté G. On rappelle qu'un cycle (ou circuit) dans un graphe \(G = (S, A)\) est une suite d'arcs consécutifs \(a_0, \ldots, a_{n - 1}\) de telle sorte que le sommet source de l'arc \(a_0\) soit le sommet destination de l'arc \(a_{n - 1}\) (\(n \geq 1\) est la longueur du cycle).

L'algorithme de détection de cycle dans un graphe se base sur l'algorithme de parcours en profondeur récursif, dont on rappelle une version ci-dessous.

def parcours_profondeur(G, depart, vus):
    """ Graphe, Sommet, [Sommet] -> [Sommet]
    Parcourt le graphe G depuis depart en profondeur (sachant que
    la liste des sommets présents dans vus ont déjà été visités).
    On suppose que depart n'est pas dans vus. """
    vus.append(depart)
    for destination in G.voisins(depart):
        if not destination in vus:
            parcours_profondeur(G, destination, vus)
    return vus

Commenter les différences entre les deux algorithmes de parcours en profondeur.

Afin de détecter les éventuels cycles dans le graphe, on va marquer les sommets avec un code couleur :

• les sommets en BLANC sont les sommets non atteints par le parcours en profondeur ;
• les sommets en GRIS sont les sommets atteints dont le parcours en profondeur est en cours ;
• les sommets en NOIR sont les sommets atteints dont le parcours en profondeur est terminé.

Détection d'un cycle depuis un sommet donné

On remplace l'ensemble vus de l'algorithme récursif du parcours en profondeur par un dictionnaire couleurs définit de la manière suivante :

• les clés k sont les sommets du graphe ;
• la valeur associée à la clé k dans le dictionnaire couleurs est un entier représentant la couleur actuelle du sommet k dans le parcours en profondeur du graphe. On prendra comme convention que l'entier 0 représente la couleur blanche, l'entier 1 représente la couleur grise, et l'entier 2 la couleur noire.

Lors de l'appel récursif parcours_cycle(G, depart, couleurs) le sommet depart (dont on suppose qu'il n'a pas encore été exploré, il est donc en BLANC) :

• on commence par marquer en GRIS le sommet départ ;
• pour chaque destination voisine de depart :
  • si la destination n'a pas encore été explorée, alors on l'explore récursivement et on renvoie True dans le cas où cette exploration détecte un cycle, False sinon.
  • sinon, si la destination est déjà en cours d'exploration, alors cela veut dire l'on vient de détecter un cycle. On renvoie donc True.
• on marque le sommet en NOIR pour indiquer qu'il a été complètement exploré et que l'on n'a pas trouvé de cycle. On renvoie donc False.

###

Lancer def testpy-undparcourspy-undcycle():bksl-nl """ Tests pour la fonction parcourspy-undcycle """bksl-nl print("Tests de parcourspy-undcycle passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import parcourspy-undcyclebksl-nl# testpy-undparcourspy-undcycle()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

BLANC, GRIS, NOIR = 0, 1, 2bksl-nlbksl-nldef parcourspy-undcycle(G, depart, couleurs):bksl-nl """ Graphe, Sommet, {Sommet:Couleur} -> boolbksl-nl Renvoie True si et seulement si il existe un cycle dans le graphe G dans la composante connexe de depart. bksl-nl On suppose que depart est en BLANC. """bksl-nl couleurs[...] = GRISbksl-nl for destination in G.voisins(depart):bksl-nl if ...:bksl-nl return ...bksl-nl elif ...bksl-nl return ...bksl-nl couleurs[...] = ...bksl-nl return ...bksl-nlbksl-nl

Détection d'un cycle dans un graphe

En déduire une fonction contient_cycle qui étant donné un graphe orienté G détermine si celui-ci contient un cycle. On fera pour cela appel à la fonction précédente, en initialisant un dictionnaire couleurs dans lequel tous les sommets du graphe G sont coloriés en blanc. On parcourra le graphe à l'aide de la fonction parcours_cycle depuis les sommets du graphe, et on renverra True si on détecte un cycle depuis un sommet de cette façon. On prendra garde à ne pas explorer de manière inutile le graphe à partir de sommets déjà parcourus en utilisant astucieusement les couleurs des sommets.

###

Lancer def testpy-undcontientpy-undcycle():bksl-nl """ Tests pour la fonction contientpy-undcycle """bksl-nl print("Tests de contientpy-undcycle passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import contientpy-undcyclebksl-nl# testpy-undcontientpy-undcycle()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def contientpy-undcycle(G):bksl-nl """ Graphe -> boolbksl-nl Renvoie True ssi le graphe orienté G contient un cycle """bksl-nl passbksl-nlbksl-nl

Distance entre deux sommets

Écrire une fonction distance qui étant donné un graphe G ainsi que deux sommets source et arrivee détermine la plus petite longueur d'un chemin de source vers arrivee. Si arrivee n'est pas accessible depuis source, la fonction renverra -1.

Indication. On reprendra l'algorithme du parcours en largueur d'un graphe en le modifiant. On enfilera dans la file à_explorer le couple (sommet, distance) où distance correspond à la longueur d'un plus petit chemin entre source et sommet. Ainsi, si l'on défile le couple (sommet, distance) et que sommet est égal à arrivee, alors on pourra renvoyer la valeur distance.

En particulier :

• on commencera par enfiler le couple (depart, 0) dans la file à_explorer ;
• si le sommet courant se trouve à distance du sommet source, alors ses voisins non encore explorés se trouvent à distance + 1 du sommet source, lorsque le graphe est parcouru en largeur.

###

Lancer def testpy-unddistance():bksl-nl """ Tests pour la fonction distance """bksl-nl print("Tests de distance passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import distancebksl-nl# testpy-unddistance()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def distance(G, depart, arrivee):bksl-nl """ Graphe, Sommet, Sommet -> int bksl-nl Renvoie la longueur du plus petit chemin entre depart et arrivee dans G """bksl-nl passbksl-nlbksl-nl

Diamètre d'un graphe

Écrire une fonction diametre qui étant donné un graphe G en détermine le diamètre d ainsi que les deux sommets (source, destination) les plus éloignés du graphe. On rappelle que le diamètre d'un graphe est la plus grande distance possible entre deux sommets source et destination quelconques du graphe.

###

Lancer def testpy-unddiametre():bksl-nl """ Tests pour la fonction diametre """bksl-nl print("Tests de diametre passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import diametrebksl-nl# testpy-unddiametre()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def diametre(G):bksl-nl """ Graphe -> intbksl-nl Renvoie la distance maximale entre deux sommets quelconques du graphe """bksl-nl passbksl-nlbksl-nl