Parcours de graphe

On utilisera dans ce tp les classes Graphe, Pile, File définies dans le fichier ds.py, ainsi que la fonction randint du module random qui étant donné deux entiers a et b renvoie un entier aléatoire compris entre a (inclus) et b (inclus). On rappelle que la classe Graphe permet de représenter des graphes orientés.

###

from random import randintbksl-nlclass 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 -> Nonebksl-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 -> Nonebksl-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 -> Nonebksl-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 -> Nonebksl-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 -> Nonebksl-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-nl

Quelques modifications ont été apportées par rapport aux classes écrites en cours :

la méthode log des variables de classe Pile (resp. File) affiche toutes les opérations d'empilement (resp. enfilement) et de dépilement (resp. défilement) auxquelles elles ont été soumises.
1 2 3 4 5
p = Pile() p.empiler(1) p.depiler() p.empiler(2) p.log()
```
Empile 1
Dépile 1
Empile 2
```
la méthode sommets et la méthode voisins de la classe Graphe renvoient une liste de sommets triée par ordre croissant.

Afin de faciliter l'écriture des codes python, on s'autorisera dans ce tp uniquement l'utilisation du mot-clé python in. L'instruction val in collection renvoie True si val est un élément de la collection, False sinon. Cette instruction est valide lorsque collection est une liste, un dictionnaire (dans ce cas on teste si val est une clé du dictionnaire)…

l = [0, 1, 2]
d = {0:'a', 1:'b', 2:'c'}
print(1 in l)
print(42 in l)
print(1 in d)
print('b' in d)

True
False
True
False

Exemples de graphes non orientés¶

Écrire une fonction arcs_vers_graphe_no qui étant donnée une liste d'arêtes construit le graphe non orienté correspondant. On représentera un graphe non orienté à l'aide d'un graphe orienté dans lequel tous les arcs (s, d) ont été doublés avec leur arc retour (d, s). La valeur renvoyée par la méthode taille est alors le double de la taille du graphe non orienté.

On commencera par instancier une variable g de type Graphe que l'on modifiera de la façon suivante : pour toutes les arêtes (s, d) présentes dans la liste aretes,

on créé si besoin les sommets s et d dans le graphe ;
on ajoute les arcs (s, d) et (d, s).

###

def arcspy-undverspy-undgraphepy-undno(aretes):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 passbksl-nlbksl-nl

aretes = [(0, 1), (0, 3), (0, 6),
          (0, 9), (1, 4), (1, 6),
          (2, 5), (3, 6), (3, 8),
          (4, 7), (5, 6), (5, 7)]    
g1 = arcs_vers_graphe_no(aretes)
g1.decrire()

Graphe d'ordre 10 et de taille 24
Sommet 0 -> 1 3 6 9
Sommet 1 -> 0 4 6
Sommet 2 -> 5
Sommet 3 -> 0 6 8
Sommet 4 -> 1 7
Sommet 5 -> 2 6 7
Sommet 6 -> 0 1 3 5
Sommet 7 -> 4 5
Sommet 8 -> 3
Sommet 9 -> 0

aretes = [(0, 1), (0, 5),
    (1, 2), (1, 6), (1, 5), (2, 3),
    (2, 7), (2, 6), (3, 7), (3, 4),
    (4, 5), (4, 6), (4, 7), (6, 7)]    
g2 = arcs_vers_graphe_no(aretes)
g2.decrire()

Graphe d'ordre 8 et de taille 28
Sommet 0 -> 1 5
Sommet 1 -> 0 2 5 6
Sommet 2 -> 1 3 6 7
Sommet 3 -> 2 4 7
Sommet 4 -> 3 5 6 7
Sommet 5 -> 0 1 4
Sommet 6 -> 1 2 4 7
Sommet 7 -> 2 3 4 6

aretes = [(0, 6), (0, 1),
    (0, 2), (0, 7), (1, 2), (1, 6),
    (1, 8), (1, 4), (2, 4), (2, 5),
    (2, 7), (3, 8), (4, 5),
    (4, 7)]    
g3 = arcs_vers_graphe_no(aretes)
g3.decrire()

Graphe d'ordre 9 et de taille 28
Sommet 0 -> 1 2 6 7
Sommet 1 -> 0 2 4 6 8
Sommet 2 -> 0 1 4 5 7
Sommet 3 -> 8
Sommet 4 -> 1 2 5 7
Sommet 5 -> 2 4
Sommet 6 -> 0 1
Sommet 7 -> 0 2 4
Sommet 8 -> 1 3

g4 = Graphe()
aretes = [(0, 1), (0, 2),
    (1, 2), (1, 3), (2, 3), (4, 5)]
g4 = arcs_vers_graphe_no(aretes)
g4.decrire()

Graphe d'ordre 6 et de taille 12
Sommet 0 -> 1 2
Sommet 1 -> 0 2 3
Sommet 2 -> 0 1 3
Sommet 3 -> 1 2
Sommet 4 -> 5
Sommet 5 -> 4

Représenter graphiquement le graphe non orientés \(G_1\) que représente la variable g1.

Parcours aléatoire¶

Écrire une fonction parcours_aleatoire qui étant donné un graphe G, un sommet depart et un entier nombre_sauts renverra le nombre de fois où chaque sommet du graphe a été visité si on le parcourt depuis le sommet depart en choisissant à chaque étape une destination aléatoire parmi les voisins du sommet courant. Plus précisément :

On utilisera un dictionnaire visites pour compter le nombre de fois où le parcours est passé par chaque sommet. Les clés de ce dictionnaire sont les sommets du graphe G, et la valeur associée au sommet s le nombre de fois où le parcours est passé par le sommet s. On initialise le dictionnaire en associant à chaque clé la valeur 0.
On utilisera une variable sommet_courant pour mémoriser le sommet en cours de visite par le parcours. À chaque itération, on incrémentera de 1 la valeur associée à sommet_courant dans le dictionnaire visites.
On choisira le prochain sommet à explorer à partir du sommet courant (un "saut") aléatoirement à l'aide de la fonction randint. Si voisins est la liste des voisins du sommet courant, on tire un indice aléatoire i compris entre 0 et len(voisins) - 1 et on choisit le sommet voisins[i] comme nouveau sommet courant.

###

def parcourspy-undaleatoire(G, depart, nombrepy-undsauts):bksl-nl """ Graphe, Sommet, int -> {Sommet: int}bksl-nl Parcourt aléatoirement le graphe G depuis le sommet departbksl-nl en effectuant nombrepy-undsauts choix de sommets. """bksl-nl passbksl-nlbksl-nl

Parcours en profondeur¶

Version récursive¶

Le parcours en profondeur d'un graphe correspond à une exploration commençant par un sommet de depart du graphe, suivie d'une exploration récursive de chacun de ses voisins. Il est nécessaire de marquer les sommets du graphe par lesquels l'exploration passe, sans quoi l'algorithme ne termine pas lorsque le graphe possède un cycle.

Dans le code donné ci-dessous, on ajoute à la liste vus les sommets dans l'ordre dans lequel ils sont visités lors d'un parcours en profondeur. On considère qu'un sommet est marqué s'il est présent dans la liste vus.

###

def parcourspy-undprofondeur(G, depart, vus):bksl-nl """ Graphe, Sommet, [Sommet] -> [Sommet]bksl-nl Parcourt le graphe G depuis depart en profondeur (sachant quebksl-nl la liste des sommets présents dans vus ont déjà été visités). """bksl-nl if depart not in vus:bksl-nl vus.append(depart)bksl-nl # appels récursif sur les voisins bksl-nl for destination in G.voisins(depart):bksl-nl parcourspy-undprofondeur(G, destination, vus)bksl-nl return vusbksl-nlbksl-nl

Pour chacun des graphes \(G_1\), \(G_2\), \(G_3\) et \(G_4\).
1. Dresser l'arbre d'appel de l'instruction parcours_profondeur(G, 0, []). On indiquera sur les nœuds de l'arbre d'appel uniquement le sommet correspondant du parcours. La liste vus est modifiée en place par tous les appels récursifs : on pourra considérer qu'il s'agit d'une variable globale.
2. En déduire la valeur renvoyée par parcours_profondeur(G, 0, []).
Vérifier vos réponses aux questions précédentes en exécutant la fonction parcours_profondeur.
On supprime la ligne 5 de la fonction parcours_profondeur (l'indentation est modifiée en conséquence).

Donner un exemple de graphe \(G\) tel que parcours_profondeur(g, 0, []) ne termine pas.

Version itérative¶

Le parcours en profondeur récursif peut poser problème dans le cas de graphe de très grande taille. En effet, il est (par défaut) impossible d'empiler plus de 1000 appels récursifs lorsque l'on exécute un programme python.

On modifie l'algorithme de parcours en profondeur afin de ne plus utiliser d'appel récursif : on utilise une Pile pour stocker les sommets à explorer.

on initialise une pile à_explorer dans laquelle on empile le sommet depart
tant que la pile des sommets à_explorer n'est pas vide :
- on dépile le sommet courant
- si celui-ci n'est pas encore marqué :
  - on le marque comme exploré en l'ajoutant à la liste vus ;
  - on empile dans le bon ordre les voisins de sommet à la pile des sommets à_explorer.

Pour le graphe g1 avec pour sommet de départ 0, on créé une pile vide à_explorer dans laquelle on empile 0. Lors du premier passage dans la boucle, on dépile 0, puis marque 0 en l'ajoutant à la liste vus. À la fin du premier passage dans la boucle la pile est constituée des éléments 9 6 3 1 (l'élément au sommet de la pile est 1). Le prochain sommet à explorer est donc 1.

###

def parcourspy-undprofondeurpy-undpile(G, depart):bksl-nl """ Graphe, Sommet, [Sommet] -> [Sommet]bksl-nl Parcours le graphe G depuis le sommet depart en profondeurbksl-nl (sachant que la liste des sommets présents dans vus ont déjà été visités). """bksl-nl vus = []bksl-nl àpy-undexplorer = ...bksl-nl ...bksl-nl while ...:bksl-nl sommet = ...bksl-nl if ...:bksl-nl vus.append(sommet)bksl-nl for destination in reversed(G.voisins(sommet)):bksl-nl ...bksl-nl return vusbksl-nlbksl-nl

Donner un exemple de graphe pour lequel le parcours en profondeur récursif soulève l'erreur RecursionError.

Une liste chaînée vue comme un graphe constitué de 1001 sommets.
1. Compléter le code de la fonction parcours_profondeur_pile.
2. Exécuter parcours_profondeur_pile(g, 0) pour chaque graphe g de l'énoncé. Que constate-t-on ?
1. Exécuter pas à pas l'instruction parcours_profondeur_pile(g1, 0). Vous suivrez l'évolution des variables vus et à_explorer et noterez EX (resp. DX) lorsque l'on empile X (resp. dépile X) dans (resp. depuis) à_explorer.
2. Modifier la fonction parcours_profondeur_pile de telle sorte qu'elle renvoie également la pile à_parcourir. À l'aide de la méthode log de la classe Pile, vérifier votre réponse à la question précédente.

Parcours en largeur¶

L'algorithme de parcours en largeur d'un graphe est très similaire à l'algorithme de parcours en largeur d'un arbre, à ceci près que l'on doit prendre en compte le marquage des sommets :

On maintient la liste des éléments à parcourir dans une file : initialement la file est constituée d'un élément, correspondant au sommet de départ du parcours.
Tant que la file des éléments à parcourir n'est pas vide :
1. Défiler le premier sommet \(A\).
2. Si celui-ci n'est pas marqué comme exploré :
  1. Marquer le sommet comme exploré.
  2. Traiter le sommet \(A\).
  3. Ajouter à la file d'attente les successeurs de \(A\).

###

def parcourspy-undlargeur(G, depart):bksl-nl """ Graphe, Sommet -> [Sommet]bksl-nl Parcours le graphe G depuis le sommet depart en largeurbksl-nl (sachant que la liste des sommets présents dans vus ont déjà été visités). """bksl-nl vus = []bksl-nl àpy-undexplorer = ...bksl-nl ...bksl-nl while ...:bksl-nl sommet = ...bksl-nl if ...:bksl-nl vus.append(sommet)bksl-nl for destination in G.voisins(sommet):bksl-nl ...bksl-nl return vusbksl-nlbksl-nl

Compléter le code de la fonction parcours_largeur.
1. Exécuter pas à pas l'instruction parcours_largeur(g1, 0). Vous suivrez l'évolution des variables vus et à_explorer et noterez EX (resp. DX) lorsque l'on enfile X (resp. défile X) dans (resp. depuis) à_explorer.
2. Modifier la fonction parcours_largeur de telle sorte qu'elle renvoie également la file à_parcourir. À l'aide de la méthode log de la classe Pile, vérifier votre réponse à la question précédente.
1. Pour chacun des graphes de l'énoncé, indiquer pour chaque sommet à quelle distance il se trouve du sommet 0.
  
  Rappel. Dans un graphe, la distance entre deux sommets est la plus petite longueur d'un chemin reliant les deux sommets dans le graphe. Elle n'est pas définie s'il n'existe pas de chemin entre les deux sommets.
2. Exécuter et faire afficher la valeur renvoyée par l'instruction parcours_largeur(g, 0) pour chaque graphe de l'énoncé.
  
  Quel est le lien entre le parcours en largeur d'un graphe à partir du sommet 0 et la distance de chaque sommet par rapport au sommet 0 ?
  
  Le parcours en largeur renvoie la liste de tous les sommets du graphe ordonnés par distance croissante par rapport à leur distance au sommet 0. Les sommets à même distance du sommet 0 apparaissent par ordre croissant (les sommets sont des entiers).

Intermède complexité : autour du mot-clé `in`¶

Dans toutes les fonctions écrites jusqu'à présent, nous avons utilisé le mot-clé in afin de tester l'appartenance d'un élément elt à une liste. On se propose dans cette partie de détailler le fonctionnement en python du mot-clé in.

Test d'appartenance d'un élément à un tableau¶

On propose le code de la classe MonTableau ci-dessous. Celle-ci est munie d'un unique attribut contenu de type list. On pourra supposer que les éléments de contenu sont tous de type int. L'instruction 0 in tab soulève une erreur lorsque tab est de type MonTableau.

###

class MonTableau:bksl-nl def py-undpy-undinitpy-undpy-und(self, tab):bksl-nl """ MonTableau, [int] -> None """bksl-nl self.contenu = tabbksl-nlbksl-nl

tab = MonTableau([0, 1, 2, 3])    
print(tab)
print(tab.contenu)
print(0 in tab)

<__main__.MonTableau object at 0x7f16d2acc7c0>
[0, 1, 2, 3]
----------------------------------
TypeError Traceback (most recent call last)
Input In [141], in <cell line: 4>()
      2 print(tab)
      3 print(tab.contenu)
----> 4 print(0 in tab)

TypeError: argument of type 'MonTableau' is not iterable

1. Écrire une méthode __contains__ de la classe MonTableau qui étant donné un élément elt renvoie True si et seulement si l'élément elt se trouve dans la liste contenu de self.
  1 2 3 4
  def __contains__(self, elt): """ MonTableau, int -> bool Détermine si elt appartient à self.contenu """ pass
2. Quelle est la complexité de la méthode __contains__ en fonction de la taille de la liste contenu ?
  
  Dans le pire des cas (elt n'est pas présent dans self.contenu) la complexité est linéaire par rapport à la taille de contenu.
Exécuter les instructions 0 in tab, 4 in tab. Que constate-t-on ?

Commentaire : ça marche. La méthode spéciale __contains__ permet de tester l'appartenance d'un élément à la structure de donnée à l'aide du mot-clé in. Ainsi v in contenu est équivalent à contenu.__contains__(v) lorsque cette méthode est implémentée.

Test d'appartenance d'un élément à un ensemble¶

En python, le type dict est implémenté à l'aide de tables de hachage. Ainsi, lorsque d est un dictionnaire, on peut considérer que l'instruction e in d s'exécute en temps constant (une opération élémentaire). On peut utiliser les dictionnaires pour implémenter une classe Ensemble dont l'interface est la suivante :

Ensemble() : créer un ensemble vide ;
s.ajouter(e) : ajouter l'élément e à l'ensemble s ;
s.supprimer(e) : supprimer l'élément e de l'ensemble s (ne soulève pas d'erreur si e n'est pas un élément de s) ;
s.__contains__(e) : renvoie True si et seulement si e est un élément de l'ensemble s.

###

class Ensemble:bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl """ Ensemble -> None """bksl-nl self.contenu = dict()bksl-nlbksl-nl def ajouter(self, elt):bksl-nl """ Ensemble, elt -> None """bksl-nl passbksl-nlbksl-nl def supprimer(self, elt):bksl-nl """ Ensemble, elt -> None """bksl-nl passbksl-nlbksl-nl def py-undpy-undcontainspy-undpy-und(self, elt):bksl-nl """ Ensemble, elt -> bool """bksl-nl passbksl-nlbksl-nl

On donne ci-dessus le code d'une classe Ensemble. Celle-ci est munie d'un unique attribut de type dict. Un élément e appartient à l'ensemble s si et seulement si e est une clé de s.contenu associé à la valeur True.

Compléter le code de l'énoncé afin que celui-ci implémente correctement l'interface du type Ensemble tel que décrit dans l'énoncé.
Quelle est la complexité de la méthode __contains__ de la classe Ensemble en fonction du nombre d'éléments de l'ensemble ?

La méthode __contains__ de la classe Ensemble s'exécute en temps constant.

Conclusion¶

Modifier le code des fonctions parcours_profondeur_pile et parcours_largeur afin d'en améliorer la complexité. On utilisera un objet vus de type Ensemble pour mémoriser les sommets déjà visités lors du parcours. On renverra une liste ordre_visite contenant la liste de tous les sommets visités sans répétition dans l'ordre chronologique du parcours.

###

def parcourspy-undprofondeurpy-undmieux(G, depart):bksl-nl """ Graphe, Sommet -> [Sommet]bksl-nl Parcours le graphe G depuis le sommet depart en profondeur """bksl-nl passbksl-nlbksl-nldef parcourspy-undlargeurpy-undmieux(G, depart):bksl-nl """ Graphe, Sommet -> [Sommet]bksl-nl Parcours le graphe G depuis le sommet depart en largeur """bksl-nl passbksl-nlbksl-nl

print(parcours_profondeur_mieux(g1, 0))
print(parcours_largeur_mieux(g1, 0))

[0, 1, 4, 7, 5, 2, 6, 3, 8, 9]
[0, 1, 3, 6, 9, 4, 8, 5, 7, 2]