Aller au contenu

TP sur les graphes

Répondez aux questions dans un fichier texte (sur Geany , enregistré en .txt).

1) Représentation des graphes en python

Voici un exemple de graphe non-orienté :

GAABBA--BGGA--GCCB--CDDB--DFFG--FC--DD--FEED--E

Question 1 : Comment pourrait-on représenter ce graphe en python ? Écrivez sur papier les tableaux (éventuellement à plusieurs dimensions) ou dictionnaires qui donneraient une représentation de ce graphe (il y a plusieurs solutions possibles).

Question 2: Comment dans votre solution peut-on :

  • si on a deux sommets, savoir s'il existe une arête entre les deux
  • si on a un sommet, trouver tous ses voisins (sommets directement reliés)

Téléchargez maintenant l'archive zip qui contient un début de code python et plusieurs graphes stockés dans des fichiers. Créer un dossier vide pour le projet, déplacer le fichier zip dedans, puis clic-droit dessus et "extraire ici". Ouvrir ensuite le dossier avec VSCodium ou bien juste le code python avec Thonny.

Question 3: Afficher avec print le résultat de lire_graphe("graphe1.txt"). Quelle est la manière qui a été choisie pour stocker le graphe ?

2) Parcours en profondeur de graphe

On a souvent besoin de parcourir tous les sommets d'un graphe. On peut utiliser la même stratégie que pour les arbres et faire un parcours en profondeur.

L'algorithme récursif de parcours en profondeur, comme pour les arbres, ressemble à ça:

Parcours(sommet):
    Afficher(sommet)
    pour tout voisin de sommet:
        Parcours(voisin)

Question 4: Complétez la fonction python parcours pour qu'elle corresponde à cet algorithme. Que se passe-t-il quand on exécute parcours("A") ?

Parcours naïf (sans retenir ce qui a déjà été parcouru)

def parcours(sommet):
    print(sommet)
    for voisin in graphe[sommet]:
        parcours(voisin)

Question 5: Réfléchissez : de quelle façon pourrait-on corriger ce problème ?

Question 6: Écrivez la version corrigée et vérifiez que parcours("A") affiche bien chaque sommet une seule fois.

Parcours en profondeur

dejavu = []
def parcours(sommet):
    if sommet in dejavu:
        pass
    else:
        dejavu.append(sommet)
        print(sommet)			
        for voisin in graphe[sommet]:
            parcours(voisin)

3) Utilisation du parcours en profondeur

Question 7: Affichez le résultat de lire_graphe("graphe2.txt"). Combien de sommets, d'arêtes, et que représente ce graphe ? (vous pouvez regarder le fichier .txt pour trouver les réponses)

Question 8: Une des utilisations d'un parcours en profondeur est de tester si deux sommets sont connectés (reliables par un chemin).

Modifiez la fonction parcours pour qu'elle permette de tester cela, et vérifier si :

  • on peut passer de "AGILE" à "RAYON" ?
  • on peut passer de "RAYON" à "FUTON" ?
  • on peut passer de "MORAL" à "FLAIR" ?

Chercher un sommet avec un parcours en profondeur

dejavu = []
def parcours(sommet, objectif):
    if sommet in dejavu: # (1)
        pass
    else:
        dejavu.append(sommet)
        if sommet == objectif:
            print("le parcours a atteint le sommet", objectif)	
        for voisin in graphe[sommet]:
            parcours(voisin, objectif)

# exemple d'utilisation :
parcours("AGILE","RAYON") # (2)

  1. on pourrait aussi écrire if sommet not in dejavu pour éviter le pass et le else.
  2. ne renvoie rien (None) mais affiche le message si "RAYON" est trouvé dans le parcours.

dejavu = []
def parcours(sommet, objectif):
    if sommet in dejavu:
        return False # (2)
    dejavu.append(sommet)
    if sommet == objectif:
        return True	
    for voisin in graphe[sommet]:
        if parcours(voisin, objectif):
            return True
    return False

# exemple d'utilisation :
est_possible = parcours("AGILE","RAYON") # (1)

  1. vaudra True ou False
  2. ce return arrête la fonction, et permet de ne pas mettre la suite dans un else car elle ne sera de toute façon pas exécutée si on tombe sur le return. Ça simplifie un peu le code.

Question 9: Ajoutez un paramètre distance à votre fonction parcours pour obtenir le nombre d'étapes avant d'arriver au sommet recherché.

Avec la distance

```python
dejavu = []
def parcours(sommet, objectif, distance):
    if sommet in dejavu:
        pass
    else:
        dejavu.append(sommet)
        if sommet == objectif:
            print(f"{objectif} atteint en {distance} étapes")
        for voisin in graphe[sommet]:
            parcours(voisin, objectif, distance + 1)

# exemple d'utilisation :
parcours("AGILE", "RAYON", 0)
```

Question 10: Est-ce que le parcours en profondeur prend toujours le chemin le plus court ? Dessinez un exemple de graphe (3 ou 4 sommets suffisent) pour expliquer.

Question 11: Pour pouvoir retrouver le chemin pris jusqu'au sommet recherché, on peut créer une liste vide chemin en dehors de la fonction de parcours. On ajoute à la fin de cette liste le sommet visité au début de la fonction avec append, et on l'enlève à la fin de la fonction avec pop. Quand on trouve le sommet recherché, on peut afficher la liste. Donnez le chemin (ou le début du chemin s'il est trop long) pour les exemples précédents.

Avec le chemin

```python hl_lines="2 8 13"
dejavu = []
chemin = []
def parcours(sommet, objectif):
    if sommet in dejavu:
        pass
    else:
        dejavu.append(sommet)
        chemin.append(sommet)
        if sommet == objectif:
            print(f"{objectif} atteint avec le chemin : {chemin}")
        for voisin in graphe[sommet]:
            parcours(voisin, objectif)
        chemin.pop()        

# exemple d'utilisation :
parcours("AGILE", "RAYON")
```

4) Version non-récursive du parcours en profondeur, et parcours en largeur

Reprenez le graphe 1 et la fonction de parcours en profondeur standard.

Ajoutez avant les appels récursifs pour parcourir les voisins : print("ajouter",sommet) Ajoutez après les appels récursifs : print("enlever",sommet)

Question 12: Observez l'ordre dans l'affichage : à quelle structure de donnée cela vous fait penser ?

En fait, on la récursivité revient toujours à utiliser de manière cachée cette structure de donnée (c'est ce que fait python pour exécuter des appels récursifs sur le processeur). Donc on peut toujours écrire une version non-récursive, même si le code est parfois un peu plus long.

Question 13: Écrivez une nouvelle fonction parcours_profondeur_iteratif(depart) selon l'algorithme suivant:

Parcours en profondeur itératif (= non-récursif) :
    Créer une pile avec juste un élément : le sommet de départ.
    Initialiser la liste des sommets déjà vus avec la liste vide.
    Tant que la pile n'est pas vide:
        récupérer un sommet en haut de la pile (en l'enlevant)
        si on n'a pas encore vu le sommet:
            ajouter le sommet dans les sommets déjà vus
            pour chaque voisin de sommet:
                le rajouter sur la pile

Utiliser une pile

Vous pouvez utiliser une liste python comme pile, avec append() pour empiler, pop() pour dépiler, len(pile) pour la taille.

Ajouter un print pour afficher chaque sommet quand on le voit pour la première fois, et testez votre fonction sur le graphe1.

Question 16:

Et là, magie (mais c'est pareil que pour les arbres) : vous pouvez reprendre la même fonction en remplaçant la pile par une file : quel ordre obtenez vous ?

Utiliser une file

On a vu plusieurs implémentations en programmation orientée objet, mais on peut aussi utiliser une bibliothèque déjà faite :

from collections import deque # double-ended queue
# parce que cette structure permet d'ajouter et retirer
# efficacement des deux côtés (donc peut simuler pile et file)
ma_file = deque()
# enfiler un élément (à droite comme une liste)
ma_file.append(truc)
# défiler un élément (à gauche du coup)
element = ma_file.popleft()
# pour tester si la file est vide, len fonctionne :
if len(ma_file) == 0:
    ...

Question 16bis Si \(S\) est le nombre de sommets du graphe et \(A\) son nombre d'arêtes, quelle sera la complexité de ces parcours itératifs ? (Il faut se demander combien de fois la boucle se répète, et est-ce que dans un tour de boucle le nombre d'opérations est constant ou bien dépend de \(S\) ou \(A\)).

Question 17: Le parcours en largeur permet de trouver le plus court chemin si les arêtes ne sont pas pondérées (toutes de même longueur). Si elles sont pondérées, on devrait utiliser l'algorithme de Dijkstra dont on a parlé pour le routage avec OSPF.

Si on veut savoir la distance pour accéder à un sommet, on peut rajouter dans la file l'information de distance en stockant non pas juste le sommet mais le tuple (sommet, distance). Le premier élément dans la file sera (depart, 0).

Quelle est la distance la plus courte entre "AGILE" et "RAYON" ? "MORAL" et "FLAIR" ?

Question 18:

Pour obtenir le chemin, comme pour le parcours en profondeur, on peut stocker dans la file la paire du sommet et du chemin pour y arriver (sous forme de liste).

Quel est le chemin le plus court entre "AGILE" et "RAYON", et entre "MORAL" et "FLAIR" ?

bonus : ceci peut être lourd en mémoire, que pourrait-on stocker comme information plus courte qui permet quand même de retrouver le chemin à la fin ?

5) Applications du parcours en profondeur : composantes connexes et détection de cycle

Un graphe qui n'est pas connecté a des composantes connexes : les morceaux du graphe connectés, entre lesquels il n'y a pas d'arête.

Question 19 : En dessinant un petit exemple de graphe à 3-4 composantes connexes, trouver et expliquer comment on peut utiliser le parcours en profondeur (ou en largeur, c'est pareil ici) pour marquer pour chaque sommet à quelle composante connexe il appartient, en numérotant les composantes connexes à partir de 0.

Expliquer comment on peut trouver ensuite le nombre de composantes connexes et leur taille.

Coder cela pour le graphe 2 : combien y a-t-il de composantes connexes sur les mots du scrabble de 5 lettres, et de quelles tailles ? (et donc si on essaye de trouver un chemin entre deux mots pris au hasard, quelle chance a-t-on que ce soit possible ?)

Question 20: Le parcours en profondeur peut aussi être utilisé pour détecter si un graphe contient un cycle (s'il n'en a pas, c'est un graphe qui pourrait être transformé en arbre en choisissant une racine). Sur papier et sur des exemples, trouver comment on peut y arriver, puis coder la variation du parcours en profondeur qui le fait (une fonction contient_cycle qui renvoie un booléen par exemple).

Est-ce que votre méthode marche aussi sur les graphes orientés ?