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.

Matrice sommet-sommet

Écrire le code de la classe GrapheM qui implémente une matrice sommet-sommet.
La spécification du constructeur de la classe est :

1
2
3
4


def __init__(self: GrapheM, mat: List[List[int]]) -> None:
        """
        Constructeur de la classe.
        """

Remarque : cette classe possède l’attribut mat qui référence la matrice d’adjacence.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class GrapheM:
    """
    Implémentation de la représentation
    matricielle d'un graphe.
    """
    def __init__(self: GrapheM, mat: List[List[int]]) -> None:
        """
        Constructeur de la classe.
        """
        self.mat = mat

Ajouter à la classe GrapheM une redéfinition de la méthode spéciale __str__ de façon à ce qu’un appel à la fonction print avec comme argument un objet représentant un graphe donne un affichage qui rappelle celui d’une matrice (lignes et colonnes).

Solution

1
2
3
4
5
6
7
8


def __str__(self: GrapheM) -> str:
    rep = ""
    for i in range(len(self.mat)):
        rep = rep + str(self.mat[i][0])  # Premier élement de la ligne
        for j in range(1, len(self.mat[0])):
            rep = rep + " " + str(self.mat[i][j])
        rep = rep + "\n"
    return rep

Écrire le code d’une fonction main qui permet de tester l’implémentation de la classe et la représentation du graphe à l’écran.
Choisir comme matrices tests

$$
M_1 =
\begin{pmatrix}
1 & 1 & 0 \cr
0 & 1 & 1 \cr
0 & 0 & 1 \cr
\end{pmatrix}
\text{ et }
M_2 =
\begin{pmatrix}
0 & 1 & 1 & 0 \cr
1 & 0 & 1 & 1 \cr
1 & 1 & 0 & 1 \cr
0 & 1 & 1 & 0 \cr
\end{pmatrix}
$$
Remarque: Les sommets du graphe sont représentés par des entiers naturels.

Solution

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


def main():
    """ Fonction principale """
    mat1 = [[1, 1, 0], [0, 1, 1], [0, 0, 1]]
    mat2 = [[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 0]]

    graph11 = GrapheM(mat1)
    graph21 = GrapheM(mat2)

    print(graph11)
    print(graph21)

main()

Représenter les deux graphes sur une feuille.
Écrire le code de la méthode nbre_sommets qui détermine le nombre de sommets du graphe.
Jeu de tests :

1
2


assert graph11.nbre_sommets() == 3
assert graph21.nbre_sommets() == 4

Solution

Une matrice sommet-sommet est carrée ; le nombre de lignes est donc égal au nombre de colonnes.

1
2
3
4
5


def nbre_sommets(self: GrapheM) -> int:
    """
    Retourne le nombre de sommets du graphe
    """
    return len(self.mat)

Écrire le code de la fonction est_lie dont la spécification est :

1
2
3
4
5


def est_lie(self: GrapheM, i: int, j: int) -> bool:
    """
    Retourne True s'il existe une relation (arête ou arc) 
    entre les sommets i et j, False sinon.
    """

Jeu de tests possible :

1
2
3


assert graph11.est_lie(1, 1) == True
assert graph11.est_lie(0, 1) == True
assert graph11.est_lie(2, 0) == False

Solution

1
2
3
4
5
6


def est_lie(self: GrapheM, i: int, j: int) -> bool:
    """
    Retourne True s'il existe une relation (arête ou arc) 
    entre les sommets i et j, False sinon.
    """
    return self.mat[i][j] != 0 

Quelle est la particularité de la matrice sommet-sommet d’un graphe non orienté ?

Solution

La matrice est symétrique par rapport à la diagonale.

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

1
2
3
4
5
6


def est_non_oriente(self: GrapheM) -> bool:
        """
        Retourne True si le graphe est non orienté 
        (si la matrice est symétrique) et False si le 
        graphe est orienté.
        """

Jeu de tests :

1
2


assert graph11.est_non_oriente() == False
assert graph21.est_non_oriente() == True

Solution

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


def est_non_oriente(self: GrapheM) -> bool:
        """
        Retourne True si le graphe est non orienté 
        (si la matrice est symétrique) et False si le 
        graphe est orienté.
        """
        n = len(self.mat)

        for i in range(n):
            for j in range(i+1, n):
                if self.mat[i][j] != self.mat[j][i]:
                    return False
        return True

Liste d’adjacence

Dans cette partie, on implémente la liste d’adjacence (liste des voisins) d’un graphe non orienté ou la liste des successeurs d’un graphe orienté.

Écrire le code de la classe GrapheL qui implémente une liste des voisins.
La spécification du constructeur de la classe est :

1
2
3
4


def __init__(self: GrapheL, lst: List[List[int]]) -> None:
        """
        Constructeur de la classe.
        """

Remarque : cette classe possède l’attribut lst qui référence une liste d’adjacence.

Solution

1
2
3
4
5
6


class GrapheL:
    """
    Implémentation de la liste des voisins d'un graphe non orienté.
    """
    def __init__(self, lst: List[List[int]]) -> None:
        self.lst = lst

Ajouter à la classe GrapheL une redéfinition de la méthode spéciale __str__ de façon à ce qu’un appel à la fonction print avec comme argument un objet représentant un graphe donne un affichage qui rappelle celui d’une liste de listes.

Solution

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


def __str__(self: GrapheLV) -> str:
    """
    Représentation sous forme d'une chaîne de caractères de l'objet.
    """
    rep = ""

    for i in range(len(self.lst)):
        rep += "{} :".format(i)
        for j in range(len(self.lst[i])):
            rep += " " + str((self.lst[i][j]))
        rep += "\n"

    return rep

Tester le code précédent à l’aide des listes des voisins/successeurs des graphes dont les matrices sommet-sommet sont données dans la première section.

Solution

1
2
3
4
5
6
7
8


lst1 = [[0, 1], [1, 2], [2]]
lst2 = [[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]]

graph12 = GrapheL(lst1)
graph22 = GrapheL(lst2)

print(graph12)
print(graph22)

Écrire le code de la méthode nbre_sommets qui détermine le nombre de sommets du graphe.
Jeu de tests :

1
2


assert graph12.nbre_sommets() == 3
assert graph22.nbre_sommets() == 4

Solution

1
2
3
4
5


def nbre_sommets(self: GrapheL) -> int:
    """
    Retourne le nombre de sommets du graphe.
    """
    return len(self.lst)

Écrire le code de la fonction est_lie dont la spécification est :

1
2
3
4


def est_lie(self: GrapheL, i: int, j: int) -> bool:
    """
    Retourne True s'il existe une relation (arête ou arc) entre les sommets i et j, False sinon.
    """

Jeu de tests possible :

1
2
3


assert graph12.est_lie(1, 1) == True
assert graph12.est_lie(0, 1) == True
assert graph12.est_lie(2, 0) == False

Solution

1
2
3
4
5


def est_lie(self: GrapheL, i: int, j: int) -> bool:
    """
    Retourne True s'il existe une relation (arête ou arc) entre les sommets i et j, False sinon.
    """
    return j in self.lst[i]

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

1
2
3
4


def est_non_oriente(self: GrapheL) -> bool:
    """
    Retourne True si le graphe est non orienté, False sinon.
    """

Jeu de tests :

1
2


assert graph12.est_non_oriente() == False
assert graph22.est_non_oriente() == True

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def est_non_oriente(self: GrapheL) -> bool:
    """
    Retourne True si le graphe est non orienté (si la matrice est symétrique) et False si le graphe est orienté.
    """
    for i in range(len(self.lst)):
        for j in range(len(self.lst[i])):
            s = self.lst[i][j]  # sommet
            if i not in self.lst[s]:
                return False
    return True

Passage d’une représentation à l’autre

Ajouter à la classe GrapheL la méthode lst_to_mat dont la spécification est :

1
2
3
4


def lst_to_mat(self: GrapheL) -> GrapheM:
    """
    Génère la matrice sommet-sommet à partir de la liste des voisins/successeurs.
    """

Tests :

1
2
3
4


graph13 = graph12.lst_to_mat()
print(graph13)
graph23 = graph22.lst_to_mat()
print(graph23)

Solution

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


def lst_to_mat(self: GrapheL) -> GrapheM:
    """
    Génère la matrice sommet-sommet à partir de la liste des 
    voisins/successeurs.
    """
    mat = []
    n = len(self.lst)

    for i in range(n):
        ligne = []
        for j in range(n):
            if j in self.lst[i]:
                ligne.append(1)
            else:
                ligne.append(0)
        mat.append(ligne)

    return GrapheM(mat)

Ajouter à la classe GrapheM la méthode mat_to_lst dont la spécification est :

1
2
3
4


def mat_to_lst(self: GrapheM) -> GrapheL:
    """
    Génère la liste des voisins/successeurs à partir de la matrice sommet-sommet.
    """

Tests :

1
2
3
4


graph14 = graph11.mat_to_lst()
print(graph14)
graph24 = graph21.mat_to_lst()
print(graph24)

Solution

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


def mat_to_lst(self: GrapheM) -> GrapheL:
    """
    Génère la liste des voisins/successeurs à partir de la matrice sommet-sommet.
    """
    liste = []  # liste des listes pour tous les sommets
    for i in range(len(self.mat)):
        rel = []  # relation pour le sommet i
        for j in range(len(self.mat)):
            if self.mat[i][j] != 0:
                rel.append(j)
        liste.append(rel) 
    return GrapheL(liste)

Code complet

Code complet en ligne

Graphe Structure de données

Suggestions de lecture :

Les graphes : structure de données