Les graphes sont employés par exemple par les GPS pour trouver le chemin le plus court entre deux villes

• On se limitera dans ce chapitre à des graphes dans lesquels il y a au plus un arc entre deux sommets. On parle de 1-graphe.
• Les graphes sont une structure de donnée relationnelle : ils permettent de représenter des situations dans lesquelles des éléments sont en relations les uns avec les autres : internet, web, réseau social, réseau routier, carte, labyrinthe...

Remarque.

On peut représenter un graphe par un tableau listant les successeurs de chaque sommet.

Exemple.

Remarque.

On peut représenter un graphe par un tableau listant les prédécesseurs de chaque sommet.

Exemple.

Exemple :

     1  2   3  4  5

Exemple :

cliquez sur la matrice pour la modifier

On considère notre réseau routier :

Etablir le tableau des villes voisines

Donner la matrice d'ajacence du graphe

On considère notre réseau routier mais avec certaines routes en sens unique :

Etablir le tableau des villes voisines

Donner la matrice d'ajacence du graphe

On considère le graphe orienté donné par les tableau des successeurs ci-dessous :

Donner la matrice d'adjacence de ce graphe.

Tracer une représentation sagittale de ce graphe. https://app.diagrams.net/

0n considère la matrice ci-dessous :

Cette matrice peut-elle correspondre à un graphe non orienté ?

Tracer une représentation sagittale du graphe associé à cette matrice (on appellera A, B et C ses sommets).

Le but de cet exercice est de construire des représentations de graphes en Python. Dans cet exercice les sommets seront représentés par des entiers de 0 à n-1 où n est 'ordre du graphe. Pour faciliter les tests, une fonction d'affichage est fournie dans le affichier à compléter.

import networkx as nx # nécessite d'installer le paquet networkx import matplotlib.pyplot as plt # nécessite d'installer le paquet matplotlib # ------------ classes Graphe ------------ # class GrapheO: """Dans cette classe, les graphes sont représentés par leur matrice d'adjacence. Les sommets seront numérotés de 0 à n-1.""" def __init__(self, n): """self(Graphe), int -> void Préconditions : n > 0 Rôle : initialise un objet de classe Graphe représentant un graphe sans arc de taille n""" def ordre(self): """self(Graphe) -> int Préconditions : aucune Rôle : retourne la taille du graphe""" def ajouter_arc(self, i, j): """self(Graphe), int, int -> void Préconditions : 0 <= i,j < self.taille Rôle : ajoute l'arc i -> j""" def existe_arc(self, i, j): """self(Graphe), int, int -> void Préconditions : 0 <= i,j < self.taille Rôle : teste si l'arc i -> j existe""" def liste_successeurs(self, i): """self(Graphe), int -> list[int] Précondition : 0 <= i < self.taille Rôle : retourne la liste des successeurs de i""" class GrapheNO: """Dans cette classe, les graphes sont représentés par leur matrice d'adjacence. Les sommets seront numérotés de 0 à n-1.""" def __init__(self, n): """self(Graphe), int -> void Préconditions : n > 0 Rôle : initialise un objet de classe Graphe représentant un graphe sans arc de taille n""" def ordre(self): """self(Graphe) -> int Préconditions : aucune Rôle : retourne la taille du graphe""" def ajouter_arc(self, i, j): """self(Graphe), int, int -> void Préconditions : 0 <= i,j < self.taille Rôle : ajoute l'arc i -> j""" def existe_arc(self, i, j): """self(Graphe), int, int -> void Préconditions : 0 <= i,j < self.taille Rôle : teste si l'arc i -> j existe""" def liste_voisins(self, i): """self(Graphe), int -> list[int] Précondition : 0 <= i < self.taille Rôle : retourne la liste des successeurs de i""" # ------------ partie à ne pas modifier ------------ # # À ne pas modifier def afficher_grapheO(g): """GrapheO1 ou GrapheO2 -> void Préconditions : aucune Rôle : affiche le graphe orienté""" nxg = nx.DiGraph() n = g.ordre() nxg.add_nodes_from([i for i in range(n)]) for i in range(n): nxg.add_edges_from([(i, j) for j in g.liste_successeurs(i)]) nx.draw(nxg, with_labels=True, font_weight='bold') plt.show() def afficher_grapheNO(g): """GrapheNO -> void Préconditions : aucune Rôle : affiche le graphe non orienté""" nxg = nx.Graph() n = g.ordre() nxg.add_nodes_from([i for i in range(n)]) for i in range(n): nxg.add_edges_from([(i, j) for j in g.liste_voisins(i)]) nx.draw(nxg, with_labels=True, font_weight='bold') plt.show() # ------------ fin de partie à ne pas modifier ------------ # # ------------ tests ------------ #

• Copier et coller le code dans Thonny ou Edupython
• Dans Edupython :
• dans le menu outils - outils - installer un module avec conda, entrer networkx et valider.
• Dans Thonny :
• dans le menu outils - Gérer les Paquets...
• recherchez le module networkx et installer-le.
• Installer le module networkx.
• Intaller ensuite le module matplotlib de la même manière.

Ce fichier contient :

• une fonction afficher_grapheO, qui permet d'afficher des graphes orientés, et plus précisément les objets des classes GrapheO ci-dessous, à conditions que toutes les méthodes aient été écrites,
• une fonction afficher_grapheNO, qui permet d'afficher les objets de la classe GrapheNO ci-dessous, à conditions que toutes les méthodes aient été écrites.

1) Compléter le fichier avec une classe GrapheO permettant de représenter des graphes orientés grâce à leur matrice d'adjacence et décrite ci-dessous :

• Attributs : mat_adj de type list[list[int]]
• Méthodes :
  • __init__(self, n) -> void : initialise une matrice d'ajacence d'un graphe d'ordre n sans aucun arc
  • ordre(self) -> int : retourne l'ordre du graphe
  • ajouter_arc(self,i,j) -> void : ajoute un arc du sommet i au sommet j
  • existe_arc(self, i, j) -> bool : retourne True si il existe un arc du sommet i au sommet j
  • liste_successeurs(self, i) -> list[int] : retourne la liste des successeurs du sommet i

2) Compléter le fichier avec une classe GrapheNO permettant de représenter des graphes non orientés grâce à leur matrice d'adjacence et décrite ci-dessous :

• Attributs : mat_adj de type list[list[int]]
• Méthodes :
• __init__(self, n) -> void : initialise une matrice d'ajacence d'un graphe d'ordre n sans aucun arc
• ordre(self) -> int : retourne l'ordre du graphe
• ajouter_arete(self,i,j) -> void : ajoute une arête entre les sommets i et j
• existe_arete(self, i, j) -> bool : retourne True si il existe une arête entre les sommets i et j
• liste_voisins(self, i) -> list[int] : retourne la liste des voisins du sommet i

Chemin

Remarque.

Le parcours en largeur permet entre autres de déterminer les chemins les plus courts entre deux sommets. Il permet de ce fait de calculer la distance entre deux sommets.

Exemple :

Remarque.

Pour éviter de passer deux fois par le même sommet, il est nécessaire, lorsqu'on parcourt un graphe, de garder une trace des sommets déjà visités.

Exemple

Cette fois, on construit la matrice qui permet de donner le nombre d'arrêtes minimales séparant deux sommets

             

Partons de Strasbourg : On marque le sommet pour indiquer qu'il a été visité puis on cherche les voisins. On marque les voisins et progressivement on enlève les arrêtes des sommets déjà visités. Quand tous les sommets sont marqués on obtient un arbre. Si On recommence en partant d'un autre sommet (ville) on aura un arbre différent.

 
A partir d'un nœud source S, il liste d'abord les voisins de S pour ensuite les explorer un par un. Ce mode de fonctionnement utilise donc une file dans laquelle il prend le premier sommet et place en dernier ses voisins non encore explorés.

Les nœuds déjà visités sont marqués afin d'éviter qu'un même nœud soit exploré plusieurs fois. Dans le cas particulier d'un arbre, le marquage n'est pas nécessaire.

Étapes de l'algorithme :

   1. Mettre le nœud source dans la file.
   2. Retirer le nœud du début de la file pour le traiter.
   3. Mettre tous les voisins non explorés dans la file (à la fin).
   4. Si la file n'est pas vide reprendre à l'étape 2.

Note : l'utilisation d'une pile au lieu d'une file transforme l'algorithme du parcours en largeur en l'algorithme de parcours en profondeur. 

Vidéo : introduction-aux-graphes

Le joueur (j) se trouve sur le sommet n°9 et la sortie (s) est au n°32

Le graphe non orienté du labyrinthe est le suivant :

Matrice d'adjacence partielle du labyrinthe :

5.2.1 - Création du graphe à partir des sommets

Instancier un objet de classe GrapheNO ayant comme grandeur le nombre de sommets
Parourir les tous les sommets
    si le sommet[i]+1 est dans la liste des sommets alors 
        ajouter une arrête entre sommets.index(sommets[i])et sommets.index(sommets[i]+1)
    si le sommets[i]+larg_laby est dans la liste des sommets 
        ajouter une arrête entre sommets.index(sommets[i])et sommets.index(sommets[i]+larg_laby)
Retourner la matrice d'ajacence et l'objet GrapheNO

5.2.2 Programmation du parcours en largeur

une liste deja_visites contenant tous les sommets déjà visités,
une file a_visiter contenant les prochains sommets à visiter,
une liste parcours,
Au début, deja_visites et parcours sont vides, a_visiter contient uniquement le sommet de départ.
Répèter jusqu'à ne plus avoir de sommet à visiter :
    défiler un sommet (notons le s),
    si s n'a pas déjà été visité :
        ajouter s dans la liste deja_visites,
        ajouter s dans la liste du parcours,
        enfiler tous les voisins de s dans la file a_visiter.
retourner la liste du parcours largeur

5.2.1 - Matrice d'adjacence :

Si on prend le sommet n° 26 : les sommets adjacents sont ceux qui sont :

• au-dessus : 26 - larg_laby
• en-dessous : 26 + larg_laby
• à gauche : 26 -1
• à droite : 26+1

Fonction matrice_adjacence   
paramètres : 
    la liste des sommets
Résultat :
    Liste contenant la matrice d'adjacence
DEBUT
    matrice ← []
    ligne ← [] 
    Pour chaque sommet dans la liste des sommets
        Pour chaque som dans la liste des sommets
            si le sommet = som-1 ou sommet = som+1 ou sommet = som+larg_laby ou sommet = som-larg_laby
                empiler 1 dans la liste ligne 
            sinon 
                empiler 0 dans la liste ligne
        empiler la ligne à la matrice
        ligne ← []
    affiche_matrice(sommets,matrice)     # appel de la fonction qui affiche la matrice pour vérifier le résultat 
    retourne matrice
Fin

2.3 - File des successeurs :

Il faut donc parcourir la matrice d'adjacence ligne par ligne et rechercher les 1 qui correspondent aux sommets adjacents.
On ajoute ce sommet dans la liste FS et on ajoute 0 pour terminer les successeurs. Au passage on construit la liste APS (l'Adresse des Premiers Successeurs).

Algorithme

Fonction File_successeurs   
paramètres : 
    matrice : liste matrice d'adjacence
    sommets : liste des sommets
Résultats :
    FS : la liste contenant la file des successeurs
    APS : la liste des adresses des premiers successeurs 
DEBUT 
    FS ← []
    APS ← [] 
    pour i variant de 0 à la hauteur de la matrice
        empiler la longueur de FS dans la liste APS 
        pour j variant de 0 à la largeur de la matrice
            si matrice[i][j]=1
                empiler sommets[j] à la liste FS
        empiler 0 à la liste FS 
    empiler la longueur de FS dans la liste APS
    retourne la liste des successeurs et les adresses des 1er successeurs
Fin

2.4- Parcours en largeur

On désire stocker la liste des sommets selon leur distance par rapport au nœud :

          

Ex : pour le nœud 10, on souhaite générer une liste de l'arbre suivant : [[10],[9,18,11],[12,26],[13,20,25,34],[14,...],...]

Algorithme

Fonction parcours_largeur   
paramètres : 
    noeud : représente la case du joueur
Résultat:
    arbre : liste contenant les distances du noeud à chaque sommet
Debut:

    arbre ← [[noeud]]
    file ← [0,noeud]
    visites ← []    # liste des sommets déjà visités 
    Tant que la longueur de la file contient plus d'un élément
        rang ← []    # liste qui permet de stocker les successeurs du sommet courant  
        Tant que le premier élément de la file est >0:    # la valeur 0 permet d'indiquer la fin de la file courante  
            sommet ← défiler la file     # sommet = file.pop()   
            Empiler le sommet à la liste visites 
            indice ← sommets.index(sommet)    # recherche de la position du sommet courant dans la liste des sommets 
            pour i variant de APS[indice] à APS[indice+1]-1:    # recherche des voisins du sommet dans FS en excluant 0 
                si FS[i] n'est pas dans la liste visites
                    Enfiler FS[i] dans rang   # rang.insert(0,FS[i]) 
                    Enfiler FS[i] dans file 
                    Empiler FS[i] dans visite
        Défiler la file (qui doit être 0)     # condition d'arrêt du tant que 
        Empiler à l'arbre la liste rang
        Enfiler la valeur 0 dans la file
    retourne la liste arbre
Fin 

5.2.3 Recherche du chemin le plus court vers la sortie

ch est une liste vide et contiendra les indices des sommets
Tant que la sortie est différente de position alors
    Réduire la liste parcours à l'indexe de la sortie
	mémoriser dans une variables la liste des voisins de la sortie
    Parcourrir la liste des voisins
        si un voisin se trouve dans la liste des voisins
            memoriser ce voisin
    ajouter ce voisin au Chemin
    remplacer la sortie par le voisin
retourner la liste des indexe des sommets