T – 4 – Implémenter les graphes

Comme les listes, les piles, et les files, il est important de distinguer le type abstrait de représentation des données, du type implémenté dans le langage.

En Python il n'existe pas de type GRAPHE prédéfini. C'est donc à chacun de l'implémenter avec les outils disponibles dans le langage.

Comme pour les listes il peut exister, selon les auteurs, des différences sur le nombre et la définition des primitives de bases. Nous allons utiliser ici ce jeu de primitives :

creerGrapheVide() : retourne un graphe vide
estVideGraphe(G) : retourne True si G est un graphe vide
ajouterSommet(G,s) : retourne le graphe après ajout du sommet s
supprimerSommet(G,s) : retourne le graphe après suppression du sommet s (et tout les arcs rliés à s)
existeSommet(G,s) : retourne True si s est un sommet du graphe G
Pour un graphe orienté :

ajouterArc(G,sd,sa) : retourne le graphe après ajout d'un arc reliant sd à sa (orienté)
supprimerArc(G,sd,sa) : retourne le graphe après suppression de l'arc sd->sa
existeArc(G,sd,sa) : retourne True si sd->sa est un arc du graphe G

Pour un graphe non orienté :

ajouterArete(G,sd,sa) : retourne le graphe après ajout d'une arête reliant sd à sa (non-orienté)
supprimerArete(G,sd,sa) : retourne le graphe après suppression de l'arête sd->sa
existeArete(G,sd,sa) : retourne True si sd->sa est une arête du graphe G

Une première implémentation (d'un graphe orienté) avec un dictionnaire

Comme nous l'avons vu, un graphe peut être représenté par une liste de successeur. Cette représentation peut être implémentée efficacement avec un dictionnaire. Chaque sommet sera donc une clé dictionnaire, et sa valeur sera la liste des sommets sa reliés à s dans le sens s -> sa.

En conséquence, un graphe vide est un dictionnaire vide.

Exemple : implémentation des graphes avec un dictionnaire

Premier exemple d'implémentation d'un graphe, en utilisant une liste de dictionnaire dont les clés sont les sommets et les valeurs les listes de successeurs des sommets.

def  creerGrapheVide() -> dict:
      return {}
def estVideGraphe(G : dict) -> bool :
      return G=={}
def ajouterSommet(G : dict , s ) -> dict : 
#s peut être str ou int
     assert s not in G,'Vous ne pouvez pas ajouter un sommet déjà existant'
     G[s]=[] 
def ajouterArc(G : dict ,sd,sa) -> dict : 
#sd et sa peuvent être str ou int
# on implemente la liste de successeurs
     assert sd in G ,'le graphe ne contient pas le sommet de départ'
     assert sa in G ,'le graphe ne contient pas le sommet d\'arrivée'     
     G[sd].append(sa)
def supprimerSommet(G : dict , s ) -> dict:
#s peut être str ou int
     assert s in G,'le graphe ne contient pas le sommet'
     del G[s]
     for sommet in G.keys() :
         if s in G[sommet] :
             G[sommet].remove(s)
def supprimerArc(G : dict,sd,sa) -> dict : 
# sd et sa peuvent etre int ou str
     assert sd in G,'le graphe ne contient pas le sommet de départ'
     assert sa in G,'le graphe ne contient pas le sommet d\'arrivée'
     assert sa in G[sd] , 'l arc n existe pas.'
     G[sd].remove(sa) 
def existeSommet(G : dict ,s) -> bool :  
#s peut être str ou int 
    return s in G 
def existeArc(G : dict ,sd,sa) -> bool :  
#sd et sa peuvent être str ou int 
    return sd in G and sa in G[sd] 
G=creerGrapheVide();ajouterSommet(G,'A') ; ajouterSommet(G,'B') ;ajouterSommet(G,'C') ;ajouterSommet(G,'D') 
ajouterArc(G,'A','B') ; ajouterArc(G,'C','D') 
print('après ajout des 4 sommets et des arcs A->B et C->D:\nG = ',G)
print('A dans G ? :',existeSommet(G,'A')) 
print('A->B dans G ? :',existeArc(G,'A','B')) 
supprimerArc(G,'A','B')
print('A->B dans G après suppression ? :',existeArc(G,'A','B'))
supprimerSommet(G,'D') 
print('Après suppression du sommet D\n G = ',G)

Pages : 1 2 3 4