Representing graphs

Reading time5 min

En bref

Résumé de l’article

Dans cet article, vous apprendrez des solutions pour représenter des graphes dans la mémoire d’un ordinateur. Après la vidéo, nous vous présenterons la structure de graphe que vous manipulerez dans le projet PyRat.

Points clés

  • La matrice d’adjacence d’un graphe peut être représentée en mémoire à l’aide d’un tableau.

  • Les listes et les dictionnaires sont également des solutions pour représenter un graphe en mémoire.

  • Chaque représentation a ses propres avantages et inconvénients.

  • Dans PyRat, la représentation d’un graphe est abstraite dans un objet.

Contenu de l’article

1 — Vidéo

Veuillez regarder la vidéo ci-dessous. Vous pouvez également lire la transcription si vous préférez.

Information

Bonjour à tous ! Dans cette leçon, nous allons parler de la manière de choisir des structures de données pour représenter des graphes.

Représenter les données dans la mémoire de l’ordinateur

Comme vous vous en souvenez sûrement, la mémoire de l’ordinateur est organisée en emplacements où les données sont stockées.

Accéder aux données nécessite donc de savoir à quel emplacement (ou adresse) elles ont été stockées.

De la même manière qu'il est plus facile de trouver une maison par son adresse plutôt que par sa description, ou un livre de bibliothèque par son numéro d'appel, il est plus facile de trouver des données quand on connaît l'adresse spécifique.

Structures de données de base pour représenter des graphes

Imaginons que nous voulons stocker la matrice d’adjacence d’un graphe.

Une façon de stocker des données en mémoire est d’utiliser un tableau. Les tableaux sont des structures de données adjacentes utilisées pour représenter des séquences de données, où chaque donnée utilise la même taille en mémoire.

Donc, si vous connaissez l'adresse de la première donnée, l'adresse de n'importe quelle autre donnée peut être facilement calculée. Par exemple, si l'adresse du premier élément est 45, et si chaque donnée est stockée en utilisant une adresse, alors l'adresse du quatrième élément est 48.

Cela signifie que vous pouvez accéder rapidement à la $n^{th}$ donnée d'un tableau. En revanche, accéder au $n^{th}$ élément non nul peut prendre du temps, car toutes les cases doivent être vérifiées une par une pour voir si elles contiennent un zéro ou non.

En termes de matrices d'adjacence de graphes, les tableaux sont efficaces pour vérifier si deux sommets $u$ et $v$ sont connectés par une arête.

En revanche, ils ne sont pas très efficaces si vous voulez récupérer tous les voisins de $u$, car vous devez tester chaque sommet $v$ un par un.

Une autre structure de données courante est la liste. Les listes ne sont pas adjacentes en mémoire, et pour trouver une donnée, vous devez d’abord trouver toutes les données précédentes.

Le principe des listes est que chaque adresse contient non seulement des données, mais aussi l'adresse de la prochaine donnée à chercher.

Donc, si vous voulez accéder à la troisième donnée dans une liste, vous devez d'abord accéder à la première, regarder l'adresse de la deuxième, puis regarder la deuxième pour trouver l'adresse de la troisième.

Accéder à la $n^{th}$ donnée dans une liste peut prendre du temps. Cependant, il est possible de contourner ce processus long d’accès à la $n^{th}$ donnée en ne stockant que les données d’intérêt, ce qui réduit considérablement l’utilisation de la mémoire comparé à un tableau.

En termes de graphes, les listes peuvent être utilisées pour stocker uniquement les informations sur les voisins des sommets par exemple, puisque les non-voisins sont souvent sans importance. Si chaque sommet n'a que quelques voisins, représenter uniquement les voisins avec des listes peut économiser beaucoup de mémoire. En revanche, vérifier si $u$ et $v$ sont connectés par une arête peut vous obliger à parcourir toute la liste des voisins de $u$.

Un dernier exemple de structures de données est les dictionnaires. Les dictionnaires sont des structures élaborées qui visent à combiner les avantages des tableaux et des listes. En particulier, un accès rapide et une utilisation efficace de la mémoire, respectivement.

Les dictionnaires utilisent des fonctions de hachage, qui sont essentiellement des mécanismes pour transformer des contenus en adresses. C'est le choix optimal pour le prototypage, car il permet aux programmeurs de bénéficier à la fois de la rapidité d'accès et d'une faible utilisation de la mémoire.

En règle générale, les dictionnaires devraient toujours être utilisés si vous ne savez pas exactement ce que vous faites.

Mots de conclusion

Merci pour votre attention ! C’est tout pour les structures mémoire, et je vous retrouverai très bientôt pour parler des bonnes pratiques de programmation. Au revoir !

2 — La représentation d’un graphe dans PyRat

Dans le logiciel PyRat, le graphe est encapsulé dans un objet, c’est-à-dire une structure complexe qui vous fournit une interface pratique pour le manipuler. En termes simples, vous n’avez pas un accès direct à la matrice d’adjacence, à la liste ou au dictionnaire qui stocke le graphe en mémoire. À la place, vous avez accès à de nombreux attributs et méthodes, qui vous permettent de manipuler le graphe sans entrer dans les détails de son implémentation.

Plus précisément, soit g une instance d’un Graph PyRat. Vous pouvez utiliser les éléments suivants :

  • g.vertices – Vous donne une liste des sommets du graphe.
  • g.nb_vertices – Vous donne le nombre de sommets dans le graphe.
  • g.edges – Vous donne la liste des arêtes du graphe.
  • g.nb_edges – Vous donne le nombre d’arêtes dans le graphe.
  • g.add_vertex(v) – Ajoute le sommet v au graphe.
  • g.add_edge(v1, v2, w) – Ajoute une arête de poids w entre v1 et v2.
  • g.get_neighbors(v) – Vous donne les voisins de v dans le graphe.
  • g.get_weight(v1, v2) – Vous donne le poids de l’arête entre v1 et v2.
  • g.remove_vertex(v) – Supprime le sommet v et toutes les arêtes qui y sont attachées du graphe.
  • g.remove_edge(v1, v2) – Supprime l’arête entre v1 et v2 du graphe.
  • g.is_connected() – Indique si le graphe est connexe.
  • g.has_edge(v1, v2) – Indique si une arête existe entre les sommets v1 et v2.
  • g.edge_is_symmetric(v1, v2) – Indique si l’arête de v1 vers v2 peut être utilisée pour aller de v2 à v1.
  • g.minimum_spanning_tree() – Vous donne un arbre couvrant minimal pour le graphe.
  • g.as_dict() – Vous donne une représentation dictionnaire du graphe.
  • g.as_numpy_ndarray() – Vous donne une représentation matricielle du graphe (comme un numpy.ndarray).
  • g.as_torch_tensor() – Vous donne une représentation matricielle du graphe (comme un torch.tensor).
Information

En pratique, un labyrinthe PyRat est une instance de la classe Maze, qui hérite de Graph. Par conséquent, il possède quelques attributs supplémentaires (par exemple, une width et une height en nombre de cellules) et des méthodes (par exemple, coords_difference(v1, v2) pour obtenir la différence selon les axes largeur et hauteur, i_exists(v) pour vérifier qu’une cellule existe dans le labyrinthe). Consultez la documentation de Maze.py pour toutes les informations !

Vous voyez, à aucun moment vous n’avez besoin de connaître la structure sous-jacente pour utiliser le graphe dans votre projet. C’est très pratique si le développeur de PyRat décide un jour de changer cette structure pour une raison quelconque. En effet, tant que l’interface reste inchangée, les codes des utilisateurs continueront de fonctionner.

Information

Il existe de nombreuses bibliothèques en ligne qui fournissent de telles interfaces pour utiliser des graphes. Quel que soit le langage que vous utilisez, il est toujours judicieux de vérifier les implémentations existantes avant de réimplémenter une structure à partir de zéro !

Pour aller plus loin

3 — Plus de détails sur la solution basée sur les listes

Nous avons vu précédemment qu’une matrice d’adjacence est un objet pratique pour représenter un graphe en mémoire.

Cependant, dans la plupart des cas, les graphes sont des objets clairsemés, c’est-à-dire que le nombre d’arêtes existantes est faible comparé au nombre d’arêtes d’un graphe complet. Une implication directe est que la plupart des entrées de la matrice d’adjacence sont des zéros. Puisque le nombre d’éléments dans une matrice d’adjacence est égal au carré de l’ordre du graphe, cela peut rapidement conduire à une grande consommation d’espace mémoire.

Une solution possible pour contourner ce problème est d’utiliser une structure de données différente : une liste de listes. Appelons un tel objet $L = (l_1, \dots, l_n)$, avec $l_1, \dots, l_n$ étant des listes. Dans cette structure, $l_i$ $(i \in [1, n])$ représentera les arêtes accessibles depuis le sommet $i$.

Par exemple, considérons la matrice d’adjacence suivante : $${\bf A} = \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}$$

En supposant que les sommets soient étiquetés de 1 à $n$, cette matrice est équivalente à la liste $L = ( (2, 4) , (1, 3, 4, 6), (2, 4), (1, 2, 3, 6), (6), (2, 4, 5, 7), (6) )$.

On peut rapidement remarquer que le nombre de nombres stockés est passé de $n^2$ = 49 à 18.

Bien que cette solution économise de l’espace mémoire, elle souffre de différentes limitations :

  • Vérifier l’existence d’une arête $\{i, j\}$ nécessite de parcourir tous les éléments de la liste $l_i$ pour vérifier si $j$ en fait partie. Cela peut prendre du temps si $i$ a beaucoup de voisins. En comparaison, faire la même vérification avec une matrice d’adjacence ${\bf A}$ ne prend qu’une seule opération, car il suffit de vérifier que ${\bf A}[i, j] \neq 0$.

  • Ce n’est pas aussi facile à étendre aux graphes pondérés. Dans le cas des matrices d’adjacence, les entrées représentent le poids associé à l’arête. Ici, les entrées sont des indices d’éléments non nuls, qui ne peuvent pas être modifiés sans créer/supprimer des arêtes. Une solution possible est de remplacer les listes d’indices $l_i = (j, k, \dots)$ par des listes de couples $l_i = ( (j, w_j), (k, w_k), \dots )$, où $w_j$ est le poids de l’arête $\{i, j\}$.

Pour aller encore plus loin