Matrices d’adjacence orientées en C++

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 n sommets d’un graphe, l’élément a_{ij} de la matrice d’adjacence A indique si les sommets i et j sont reliés par une arête (1 si oui, 0 sinon).

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

  • a_{ij}=1 si et seulement si l’arête va du sommet i au sommet j ;
  • a_{ij}=-1 si et seulement si l’arête va du sommet j au sommet 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) :

Exemple de graphe
Exemple de graphe

La matrice d’adjacence vaut alors :
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++.

Matrices d’adjacence orientées en C++
Noter cet article
  • Chuck

    sed -i -e « s/arrête/arête/g » *