Représentation d'un graphe en informatique

Plusieurs modes de représentation peuvent être implémentés pour stocker des graphes : matrices d’adjacence (ou sommet-sommet), listes des voisins, des successeurs ou des prédécesseurs. Lors de cette séance nous allons écrire les classes réalisant ces implémentations.

Structure de graphe basée sur une liste d’adjacence

  1. Écrire le code de la méthode __init__ de la classe Sommet dont la spécification est :

    1
2
3
4

    def __init__(self: Sommet, val: str) -> None:
    """
    Initialisation d'un sommet.
    """

    Remarque : La classe Sommet possède deux attributs :

    • val représente la valeur du sommet ou son étiquette. Cet attribut est de type chaîne de caractères (str) ;
    • adj représente la liste des sommets adjacents au sommet, instance de la classe. Cet attribut référence une liste de sommets ; lors de l’initialisation d’un sommet il doit référencer une liste vide.
Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Sommet:
"""
Représentation d'un sommet.
"""

def __init__(self: Sommet, val: str) -> None:
    """
    Initialisation du sommet.
    """
    self.val = val
    self.adj = []  # Sommets adjacents

  1. Ajouter au code de la classe Sommet la re-définition de la méthode __repr__ donnée ci-dessous :

    1
2
3
4
5
6
7
8

    def __repr__(self: Sommet) -> str:
    rep = str(self.val) + " : ["
    for i, sommet in enumerate(self.adj):
        rep += str(sommet.val)
        if i < len(self.adj) - 1:
            rep += ", "
    rep += "]"
    return rep

    Cette méthode permet de représenter un sommet sous la forme d’une chaîne de caractères.

  2. Tester la définition de la classe Sommet en ajoutant les lignes de code suivantes au fichier :

    1
2
3
4
5
6
7
8

    if __name__ == "__main__":
    s1 = Sommet("a")
    s2 = Sommet("b")
    s3 = Sommet("c")
    s1.adj.append(s2)
    s1.adj.append(s3)
    print(s1)
    print(s2)

  3. Écrire le code de la méthode __init__ de la classe Graphe dont la spécification est :

    1
2
3
4
5
6
7
8
9

    def __init__(self: Graphe, valeurs: str = "") -> None:
    """
    La liste des sommets peut être passée dans une
    chaîne de caractères. Chaque sommet doit alors être
    séparé du précédent par une virgule.

    Hypothèse : chaque sommet n'est présent qu'une seule
    fois dans valeurs.
    """

    Remarque : La classe Sommet possède un seul attribut, sommets. Ce dernier référence une liste d’objets de type Sommet. Cette liste est initialement :

    • Soit vide,

    • Soit constituée des sommets passés en argument lors de l’initialisation d’un objet de type Graphe.

Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Graphe:
    """
    Représentation du graphe.
    """

    def __init__(self: Graphe, valeurs: str = "") -> None:
        """
        La liste des sommets peut être passée dans une
        chaîne de caractères. Chaque sommet doit être
        séparé du précédent par une virgule.

        Hypothèse : chaque sommet n'est présent qu'une seule
        fois dans valeurs.
        """
        self.sommets = []  # liste des sommets

        if valeurs != "":
            for sommet in valeurs.split(","):
                self.sommets.append(Sommet(sommet))

  1. Ajouter au code de la classe Graphe la re-définition de la méthode __repr__ donnée ci-dessous :

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    def __repr__(self: Graphe) -> str:
    """
    Représentation du graphe sous forme d'une chaîne de 
    caractères.
    """
    rep = "{"
    for i, sommet in enumerate(self.sommets):
        rep += repr(sommet)
        if i < len(self.sommets) - 1:  # Ajout de la virgule sauf dernier tour
            rep += ', '
    rep += "}"
    return rep

    Cette méthode permet de représenter un graphe sous la forme d’une chaîne de caractères.

  2. Tester la définition de la classe Graphe à l’aide du code suivant, sous les lignes de code de la question 3 :

    1
2

    g1 = Graphe("a,b,c,d")
print(g1)

  3. Écrire le code de la méthode existe_sommet dont la spécification est :

    1
2
3
4

    def existe_sommet(self: Graphe, s: str) -> bool:
    """
    Vérifie que le sommet s existe bien dans le graphe.
    """
Réponse 
1
2
3
4
5
6
7
8
9

def existe_sommet(self: Graphe, s: str) -> bool:
    """
    Vérifie que le sommet s existe bien dans le graphe.
    """
    sommet_present = False       # Sommet pas présent
    for sommet in self.sommets:  # sommet référence un objet
        if sommet.val == s:
            sommet_present = True
    return sommet_present

  1. Tester le code précédent en ajoutant les instructions suivantes, à la fin du fichier :

    1
2

    print(f"Sommet g présent dans le graphe : {g1.existe_sommet('g')}")
print(f"Sommet a présent dans le graphe : {g1.existe_sommet('a')}")

  2. Écrire le code de la méthode ajout_sommet dont la spécification est :

    1
2
3
4
5
6
7

    def ajout_sommet(self: Graphe, val: str) -> None:
    """
    Ajout du sommet de valeur val au graphe.

    Si le sommet est déjà présent dans le graphe une exception
    est levée.
    """
Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def ajout_sommet(self: Graphe, val: str) -> None:
    """
    Ajout du sommet de valeur val.

    Si le sommet est déjà présent dans le graphe une exception
    est levée.
    """
    if self.existe_sommet(val):
        raise Exception("Sommet déjà présent dans le graphe !")

    self.sommets.append(Sommet(val))

  1. Tester le code précédent en ajoutant les instructions suivantes, à la fin du fichier :

    1
2

    g1.ajout_sommet("e")
print(g1)

  2. Écrire le code de la méthode recuperation_sommet dont la spécification est :

    1
2
3
4
5
6

    def recuperation_sommet(self: Graphe, s: str) -> Sommet:
    """
    Récupère l'objet de type sommet, présent dans la liste
 sommets, dont la valeur/étiquette est s.
    Lève une exception si le sommet n'existe pas.
    """

​ Remarque : Cette méthode simplifie l’écriture des méthodes suivantes.

Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def recuperation_sommet(self: Graphe, s: str) -> Sommet:
    """
    Récupère le sommet de valeur s.
    Lève une exception si le sommet n'existe pas.
    """
	if not self.existe_sommet(s):
	    raise Exception(f"Le sommet {s} n'existe pas.")

	for objet_sommet in self.sommets:
	    if objet_sommet.val == s:
	        return objet_sommet

  1. Écrire le code de la fonction existe_arete dont la spécification est :

    1
2
3
4
5
6
7

    def existe_arête(self, s1: str, s2: str) -> bool:
    """
    Détermine si l'arête {s1, s2} existe dans le graphe.

    Ne vérifie pas l'existence de l'arête {s2, s1}.
    Lève une exception si l'un des sommets n'existe pas.
    """
Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def existe_arête(self, s1: str, s2: str) -> bool:
    """
    Détermine si l'arête {s1, s2} existe dans le graphe.

    Ne vérifie pas l'existence de l'arête {s2, s1}.
    Lève une exception si l'un des sommets n'existe pas.
    """
	objet_sommet_depart = self.recuperation_sommet(s1)
	objet_sommet_arrivee = self.recuperation_sommet(s2)

	return objet_sommet_arrivee in objet_sommet_depart.adj

  1. Écrire le code de la fonction ajout_arete dont la spécification est :

    1
2
3
4
5
6
7
8

    def ajout_arete(self: Graphe, s1: str, s2: str) -> None:
    """
    Ajoute l'arête (ou l'arc) {s1, s2} au graphe.

    Si les sommets n'existent pas, on lève une exception.
    Si l'arête existe déjà, on lève une exception.
    Ne crée pas l'arête {s2, s1}.
    """
Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def ajout_arete(self: Graphe, s1: str, s2: str) -> None:
    """
    Ajoute l'arête (ou l'arc) {s1, s2} au graphe.

    Si les sommets n'existent pas, on lève une exception.
    Si l'arête existe déjà, on lève une exception.
    Ne crée pas l'arête {s2, s1}.
    """
    # L'arête existe-t-elle déjà ?
    if self.existe_arête(s1, s2):
        raise Exception("Arête existe déjà !")

    # Récupération des sommets
    sommet_depart = self.recuperation_sommet(s1)
    sommet_destination = self.recuperation_sommet(s2)

    # Ajout du sommet s2 à la liste des adjacents de s1
    sommet_depart.adj.append(sommet_destination)

  1. Tester le code précédent en ajoutant les instructions suivantes, à la fin du fichier :

    1
2
3
4
5
6
7

    g1.ajout_arete("a", "b")
g1.ajout_arete("b", "a")
g1.ajout_arete("a", "e")
# g1.ajout_arete("a", "b")
g1.ajout_arete("c", "e")
g1.ajout_arete("e", "c")
print(g1)

  2. Écrire le code de la fonction est_non_oriente dont la spécification est :

    1
2
3
4

    def est_non_oriente(self: Graphe) -> bool:
    """
    Détermine si le graphe est non orienté.
    """
Réponse 
1
2
3
4
5
6
7
8
9

def est_non_oriente(self: Graphe) -> bool:
    """
    Détermine si le graphe est non orienté.
    """
    for sommet1 in self.sommets:
        for sommet2 in sommet1.adj:
            if not self.existe_arête(sommet2.val, sommet1.val):
                return False
    return True

  1. Tester le code précédent en ajoutant les instructions suivantes, à la fin du fichier :

    1
2
3

    print(f"Le graphe est non orienté : {g1.est_non_oriente()}")
g1.ajout_arete("e", "a")
print(f"Le graphe est non orienté : {g1.est_non_oriente()}")

  2. On souhaite maintenant écrire le code de la fonction construction_matrice dont la spécification est :

    1
2
3
4

    def construction_matrice(self: Graphe) -> list[list[int]]:
    """
    Construction de la matrice sommet - sommet du graphe.
    """

    Compléter le code suivant :

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    def construction_matrice(self: Graphe) -> list[list[int]]:
    """
    Construction de la matrice sommet - sommet du graphe.
    """
    val_sommets_ordonnees = sorted([sommet.val for sommet in self.sommets])

    matrice = .....  # Initialisation de la matrice
    for nom_sommet in val_sommets_ordonnees:
        # Récupération de l'objet de type sommet associé au nom
        sommet = .....
        # Récupération des noms des sommets adjacents
        nom_sommets_adjacents = [
            sommet_adj.val for sommet_adj in sommet.adj]

        ligne_matrice = .....         # Initialisation de la ligne de la matrice
        for i in range(len(val_sommets_ordonnees)):
            if val_sommets_ordonnees[i] in nom_sommets_adjacents:
                ......
            else:
                ......
        .....  # Ajout de la ligne à la matrice

    return matrice
Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def construction_matrice(self: Graphe) -> list[list[int]]:
    """
    Construction de la matrice sommet - sommet du graphe.
    """
    val_sommets_ordonnees = sorted([sommet.val for sommet in self.sommets])

    matrice = []  # Initialisation de la matrice

    for nom_sommet in val_sommets_ordonnees:
        # Récupération de l'objet de type sommet associé au nom
        sommet = self.recuperation_sommet(nom_sommet)
        # Récupération des noms des sommets adjacents
        nom_sommets_adjacents = [
            sommet_adj.val for sommet_adj in sommet.adj]

        ligne_matrice = []            # Initialisation de la ligne de la matrice
        for i in range(len(val_sommets_ordonnees)):
            if val_sommets_ordonnees[i] in nom_sommets_adjacents:
                ligne_matrice.append(1)
            else:
                ligne_matrice.append(0)
        matrice.append(ligne_matrice)  # Ajout de la ligne à la matrice

    return matrice

  1. Tester le code précédent en ajoutant les instructions suivantes, à la fin du fichier :

    1

    print(f"Matrice : {g1.construction_matrice()}")

  2. Écrire le code de la méthode representation_matrice dont la spécification est :

    1
2
3
4
5

    def representation_matrice(self: Graphe) -> str:
    """
    Retourne une chaîne de caractères qui permet un
    affichage classique de la matrice (lignes x colonnes).
    """

    Tester le code.

Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def representation_matrice(self: Graphe) -> str:
    """
    Retourne une chaîne de caractères qui permet un
    affichage classique de la matrice (lignes x colonnes).
    """
    matrice = self.construction_matrice()

    rep = ""
    nbre = len(matrice)  # nombre de lignes et de colonnes
    for i in range(nbre):
        for j in range(nbre):
            rep += str(matrice[i][j]) + '\t'
        rep += "\n"
    return rep

Extensions possibles

Il est possible de compléter la classe en définissant les méthodes suivantes :

  • taille, de spécification :

    1
2
3
4

    def taille(self: Graphe) -> int:
    """
    Retourne le nombre de sommets dans le graphe.
    """

  • rend_non_oriente, de spécification :

    1
2
3
4
5
6

    def rend_non_oriente(self: Graphe) -> None:
    """
    Assure que pour toute arête {s1, s2} il existe une 
    arête {s2, s1}. Si ce n'est pas le cas, cette arête
    est créée.
    """

  • suppression_arete, de spécification :

    1
2
3
4
5

    def suppression_arete(self: Graphe, s1: str, s2: str) -> None:
    """
    Supprime l'arête {s1, s2} si elle existe, lève une exception
    dans le cas contraire.
    """

  • suppression_sommet, de spécification :

    1
2
3
4
5
6
7
8

    def suppression_sommet(self: Graphe, s: str) -> None:
    """
    Supprime le sommet s s'il existe, lève une exception dans
    le cas contraire.

    S'assure avant la suppression du sommet que toute arrête
    dans laquelle il intervient est supprimée.
    """
Graphe  Structure de données 

Suggestions de lecture :