Pour mes travaux de recherche, j’ai été amené à utiliser les matrices d’adjacence orientées. Je vous propose ici mon implémentation en C++.

C’est quoi une matrice d’adjacence ?

Soit un ensemble de $latex n$ sommets d’un graphe, l’élément $latex a_{ij}$ de la matrice d’adjacence $latex A$ indique si les sommets $latex i$ et $latex j$ sont reliés par une arête (1 si oui, 0 sinon).

Dans le cas des graphes orientés, on distingue deux cas :

• $latex a_{ij}=1$ si et seulement si l’arête va du sommet $latex i$ au sommet $latex j$ ;
• $latex a_{ij}=-1$ si et seulement si l’arête va du sommet $latex j$ au sommet $latex i$

La matrice est donc anti-symétrique.

Fonctionnalités

L’implémentation proposée permet de numéroter automatiquement les arêtes (à partir de 1). De plus, aucune hypothèse de taille de matrice n’est nécessaire (la taille est gérée dynamiquement grâce à l’utilisation de vectors).

La figure suivante illustre un graphe composé de quatre sommets (entourés) et de quatre arêtes reliant ces sommets (flèches) :

La matrice d’adjacence vaut alors :
$latex
A=\begin{pmatrix}
0 & 1 &0 & 0\\
-1 & 0 & 2 & -4\\
0 & -2 & 0 & -3\\
0 & 4 & 3 & 0
\end{pmatrix}
$

Sources

L’intégralité des sources ainsi que le how to sont disponibles sur GitHub.

Utilisation

Création d’une matrice

adjacencyMatrix A;

Création d’une arête

entre les sommets 1 et 2 :

A.add(1,2);

On peut récupérer l’identifiant de l’arête créée :

int ide=A.add(1,2);

Si l’arête existe déjà, la matrice n’est pas modifiée et la fonction retourne l’identifiant de l’arête existante.

Vérifier si une arête existe

A.get(1,2);

va retourner true si l’arête existe, false sinon.

Obtenir l’identifiant d’une arête

int ide;
A.get(1,2,ide);

ide prendra la valeur de l’identifiant de l’arête (si elle existe).

Objectif initial

Cette classe a été créée pour la génération de fichiers Gmsh depuis les géométries issues de Voro++.