# Spécifications du module Gestion de Graphes
###### tags: `specs`
## Introduction
Le module de gestion de graphe est présent dans la bibliothèque, ce module est utile lors de la création des graphes ainsi que les différentes conversion nécessaires aux autres modules tel que celui sur les opération sur les graphes.
On suppose que l'on a défini les méthodes d'accès et de changement (getter et setter) pour chaque attributs d'une classe pour ne pas avoir de superflu.
## VectVal
```c++
typedef struct Valeur_Vecteur{
/*
Cette structure permet de stocker dans un même vecteur des int et des float.
C'est necessaire car les valeurs embarquées sur les sommets ou les arcs peuvent être indiférement des deux types.
*/
bool type; /* Permet de différencier plus efficacement les entiers et
les réels dans le vecteur. Cela sera utile pour l'analyse des données
stocké dans la liste des valeurs contenu par sommet donné.
type = 0 ( entier ), type = 1 ( réel ) */
int valeur_entiere; // valeur de type entier pour un sommet
float valeur_reel; // valeur de type réel pour un sommet
} VectVal;
```
## Sommet
```c++
class Sommet { // Sommet du graphe orientés
private:
int x; /* Coordonnées entiere x pour placer le sommet
sur l'axe des abscisses, c'est un entier car le plan
est representé par des pixels */
int y; /* Coordonnées entière y pour placer le sommet
sur l'axe des ordonnées, c'est un entier car le plan
est representé par des pixels */
int id; /* Identifiant du sommet c'est un entier car ils
sont facilement manipulables et qu'on peut les utiliser pour
representer les cases d'une matrice. Les identifiants iront de 0 a V- 1 */
String etiquette; /* Nom du sommet, c'est une string pour pouvoir
nommé le sommet explicitement. Par défaut elle est égale à l'id.
Utilisé lors de l'affichage pour montrer a l'utilisateur ce que
representent les sommets: une ville, une station de ski, une gare, etc... */
vector<int> vecArc // Liste des arcs sortants d'un sommet representés dans le vecteur par leur ID. on utilise un vecteur car c'est un type de tableau dynamique qui est primitif en C++
map<string,vectVal> SCharge_utile; // Vecteur d'entier ou de réels, il permet de stocker toutes les valeurs sur lesquelles on veut pouvoir travailler: des dates au plus tôt et au plus tard, etc
public:
bool operator==(const Sommet &s)
/* Surcharge de l'operateur de comparaison. On compare si deux sommets sont égaux c'est à dire si les id, les etiquettes, les coordonées sont identiques, ainsi que les arcs sortants et la map SCharge_utile */
bool operator=(const Sommet &s)
/* Surcharge de l'operateur d'affectation. Copie dans le sommet courant tous les attributs du sommet s */
/*Les constructeurs*/
Sommet(String etiq, int id, int posx, int posy, VectVal v) /*
Constructeur qui permet d'instancier un objet avec un nom de type
string "etiq", puis d'un Identifiant de type int "id" pour le manipuler
facilement, ainsi qu'une position de départ "posx" et "posy" et d'un
vecteur donné par l'utilisateur qui contiendra l'intégralité des
données réelles ou entières du sommet.*/
Sommet(String etiq, int id, int posx, int posy )
// Constructeur sans le vecteur de données
Sommet(String etiq, int id)
// constructeur sans coordonnés et sans vecteur
Sommet(int id) // constructeur d'un sommet seulement à partir de son identifiant.
Sommet(&Sommet S)
/* Constructeur d'un sommet à partir d'un autre sommet. C'est à dire
que pour la construction d'un sommet donné, on va affecter à ce
nouveau sommet toutes les valeurs contenu par les attributs du
sommet mis en paramètre de ce constructeur. */
~Sommet() /* Desctructeur de l'objet sommet. Il sera employé pour la
gestion de la mémoire et pour l'allocation dynamique des objets sommets.*/
get; // getter de tous les attributs privés
set; // setter de tous les attributs privés
};
```
- X et Y sont les positions du sommet dans le graphe
- numéro est un entier pour retouver le sommet que l'on veut
- étiquette est la meme chose que numero mais en chaine de caractères
- le vecteur est déjà defini en c++ avec la bibliotheque vector, il permet de stocker un nombre quelconque d'entiers ou de flottants dans un sommet
- map est un conteneur trié associatif. Les clées sont triées entre elles par comparaison grace à la fonction "compare" inclue dans la bibliotèque de base C++ std.
### Test_Sommet
```c++
TEST_CASE("Test de l'operateur =", "[Sommet]"){
/*
on va tester que le sommet renvoyé est bien égal au sommet passé en argument.
*/
}
TEST_CASE("Test de l'operateur ==", "[Sommet]"){
/*
on teste que si les deux sommets sont bien égaux la fonction renvoie 1, sinon 0.
*/
}
TEST_CASE("Test des constructeurs ", "[Sommet]"){
/*
test du premier constructeur avec les valeurs Sommet1("sommet1", 1,2,3,vec)
test du deuxieme constructeur avec les valeurs Sommet2("sommet2", 2,2,3)
test du troisieme constructeur avec les valeurs Sommet3("sommet3",3)
test du quatrième constructeur avec la valeur Sommet4(4)
test du constructeur copie avec les valeurs Sommet5(Sommet4)
*/
}
TEST_CASE("Test du destructeur", "[Sommet]"){
/*
Le destructeur va être testé avec un sommet construit avec tous les paramètres puis on va vérifier que le sommet est correctement détruit.
*/
}
TEST_CASE("Test des getters", "[Sommet]"){
/*
Les getters vont être testés, en vérfiant les donnés renvoyées par la méthode avec ceux qu'on estime recevoir.
*/
}
TEST_CASE("Test des setters", "[Sommet]"){
/*
Les setters vont être testés, en modifiant les données avec la méthode et en vérfiant ceux renvoyées.
*/
}
```
## Arc
```c++
class Arc { // arc entre 2 sommets
private:
int id; /* Id de l'arc c'est un entier car ils
sont facilement manipulables et qu'on peut les utiliser pour
representer les cases d'une matrice. Les identifiants iront de 0 a E- 1.
*/
string etiquette; /* Nom de l'arc, c'est un string pour
pouvoir nommer l'arc explicitement.
Par défaut elle est égale à l'id.
Utilisé lors de l'affichage pour montrer a l'utilisateur ce que
representent les arcs: une route, etc */
int IDdepart; // ID du sommet de départ. On utilise l'ID car ils sont plus facile a manipuler que l'objet complet.
int IDarrive; // ID du sommet d'arrivée. On utilise l'ID car ils sont plus facile a manipuler que l'objet complet.
map<string,vectVal> ACharge_utile; // Vecteur d'entier ou de réels, il permet de stocker toutes les valeurs sur lesquelles on veut pouvoir travailler: flots maximum, etc.
public:
bool operator==(Arc const& arc1);/*On compare si deux arcs sont égaux c'est à dire si le this.id == arc1.id et this.IDdepart == arc1.IDdepart et this.IDarrivee == arc1.IDarrivee et this.etiquette == arc1.etiquette et que this.ACharge_utile == arc1.ACharge_utile */
Arc & operator=(Arc const& arc0);/* Cette surcharge d'operateur permet de copier l'arc arc0 dans un nouvel Arc créer que l'on renvoit. On copie : id, IDdepart, IDarrivee, ACharge_utile, etiquette */
Arc (String etiq, int num, int Sdepart, int Sarrivee, vecteur Vect);
/* construit un arc avec son nom, numero, son sommet de départ et
d'arrivée et un vecteur comprennant les informations sur l'arc (son
poids, flot max ,etc ...) */
Arc (String etiq, int num, int Sdepart, int Sarrivee);
/* Constructeur permettant de créer un arc avec son étiquette
(qui est son nom affiché à l'écran pour permettre à l'utilisateur
d'avoir une représentation plus compréhensible), son numéro, son
sommet de départ et son sommet d'arrivée, la différence avec le
précédent constructeur est qu'il ne néscessite pas de vecteur pour
être créer et va mettre le vecteur par défaut.
Cela permet de créer
des arcs sans poids ou flot maximale. */
Arc (int num, int Sdepart, in Sarrivee); /* Permet de créer
un arc avec seulement son numéro et ses sommets de départ et
d'arrivée. Il permet de créer un arc en ne lui affectant pas
d'étiquette ni de vecteur. */
Arc (&Arc a) /* construit un arc en utilisant les même données que
l'arc en entrée (seul son numero d'identification sera différent) */
~Arc(); // destructeur
get; // getter de tous les attributs privés
set; // setter de tous les attributs privés
};
```
- numero est un entier pour retouver l'arc que l'on veut
- etiquette est la meme chose que numero mais en chaine de caractères
- un arc sera aussi composé des deux sommets, le premier est le sommet dont l'arc sort, le deuxieme est celui dont l'arc entre.
-
### test arc
```c++
TEST_CASE ("Test de l'operateur =", "[arc]")
/*
test si l'objet Arc passé en argument est bien égal à l'objet Arc renvoyé
*/
TEST_CASE ("Test de l'operateur ==", "[arc]")
/*
test si le booléen renvoyé est bien conforme à la comparaison de l'objet Arc en argument et celle de l'objet Arc this
*/
TEST_CASE("test des constructeurs", "[arc]")
/*
test du premier constructeur avec les valeurs Arc("arc1", 1,2,3,<0>)
test du deuxieme constructeur avec les valeurs Arc("arc2", 4,2,3)
test du troisieme constructeur avec les valeurs Arc(5,2,3)
test du constructeur copie avec les valeurs Arc(A3)
*/
TEST_CASE("test du destructeur", "[arc]")
/*
test du destructeur
*/
TEST_CASE("test des getters", "[arc]")
/*
test des getters avec les valeurs renvoyés.
*/
TEST_CASE("test des setters", "[arc]")
/*
test des setters grace au getters.
*/
```
## Graphe
```c++
class Graphe {
private :
par un entier */
string etiquette // nom du graphe
vector <Arc> list_arc // Liste des arcs du graphe
vector<Sommet> liste_de_sommet // Liste des sommets du graphe
string path //chemin de sauvegarde du graphe
public :
bool operator==(Graphe const& G)/*
teste l'égalité entre ce graphe et le graphe appelé en argument, comparaison complète(du nom au liste de sommets et d'arcs)*/
Graphe & operator=(Graphe const& G)/*
Cette surcharge d'opérateur permet de copier le graphe G dans une nouveeau graphe créé. Il copie tous les attributs privés de graphe. */
Graphe(string Nom, int nb_sommets, vector<Sommet> listeS, vector<Arc> listeA, string path) /*
Construit un graphe avec son nom,sa liste de sommets (qui peut être vide) et sa
liste d'arcs ainsi que son chemin (qui peut être vide).
Ce constructeur permet autant de créer de nouveaux graphes (dans le
cas où les listes d'arc et de sommets sont vides)
que des sous graphes (Avec des listes de sommets et d'arcs pré-
existants)
*/
Graphe(Graphe & G) /* Constructeur de copie. Ce constructeur est
utilisé lors de la duplication de graphes. */
Graphe(string Nom) /* Constructeur qui créé un graphe aleatoire.
Son nombre de sommets ainsi que la liste de sommets/arcs sera
produit aléatoirement. Ce constructeur est utilisé lors de la
création aléatoire d'un graphe. */
~Graphe(); // Destructeur
get; // getter de tous les attributs privés
set; // setter de tous les attributs privés
Matrice convert_to_matrice_adj(){
/* Utilise la liste de sommets et
d'arcs d'un graphe pour créer une matrice d'adjacence qui sera utilisée
dans certain algorithmes et qui peut être un formalisme choisit par un
développeur tier.
Retourne la matrice d'adjacence correspondant aux listes */
}
Matrice convert_to_matrice_inc(){
/* Utilise la liste de sommets et d'arcs d'un graphe pour créer une matrice d'incidence qui sera utilisée dans certains algorithmes et qui peut être un formalisme choisit par un développeur tier.
Retourne la matrice d'incidence correspondant aux listes */
}
int ajout_Sommet(int numero, int posX, int posY){
/*Ajout d'un sommets dans le graphe (son numéro se choisi par rapport
aux numéros des sommets déjà existants par le graphe) et les positions X
et Y sont déterminés par le clic du curseur de l'utilisateur dans le cas du dessin de graphe, si le graphe est généré par l'application (graphe
aléatoire/PERT) ces valeurs seront déterminés à l'aide de Force Atlas 2.
Retourne le numéro du sommet*/
}
int supprimer_Sommet(int numero){
/* Appelle destructeur + Supprime un sommet de la liste de sommet et
renvoie son numéro.
*/
}
vector<vector<int>> Convert_to_ldV(){
/* Utilise les listes de sommets et d'arcs pour
construire une liste de voisin qui sera utilisée dans certain
algorithmes et qui peut être un formalisme choisit par un développeur tier.
Retourne la liste de voisin correspondant au graphe */
}
int ajout_Arc(int ID_Sdepart, int ID_Sarrivee){
/*
Ajoute un nouvel arc allant de Sdepart vers Sarrivée
et renvoie son numero
*/
}
int supprimer_Arc(int ID){
/*
Appelle destructeur + Supprime l'arc des liste et renvoie
son numero
*/
}
};
```
### test graphe
```c++
TEST_CASE("Test de l'opérateur ==","[graphe]"){
}
TEST_CASE("Test de l'opérateur =","[graphe]"){
}
TEST_CASE("Test des constructeurs", "[graphe]"){
/*
test du constructeur complet avec la valeur Graphe(graphe1, 2, <S1, S2>, <A1>, "")
test du constructeur de copie avec la valeur Graphe(&graphe1)
test du constructeur de graphe aléatoire avec la valeur Graphe ("graphe2")
*/
}
TEST_CASE("Test du destructeur", "[graphe]"){
/*
test du destructeur de la classe graphe
vérifie que les sommets et les arcs ont bien été détruits grâce à leurs destructeurs respectifs
*/
}
TEST_CASE("Test des getters", "[graphe]"){
/*
test de l'ensemble des getters grâce aux valeurs de retour
*/
}
TEST_CASE("Test des setters", "[graphe]"){
/*
test de l'ensemble des setters, en modifiant les données avec la méthode par vérification des données renvoyées.
*/
}
TEST_CASE("Test des conversions en matrice d'incidence + adjacence", "[graphe]"){
/*
Pour vérifier ces deux méthodes nous allons créer un graphe G0 : 0 --> 1
et pré défninir ses deux matrices, d'adjacence et incidence.
M_adj : 0 1 M_inc : -1
0 0 0
On va vérifier que chacune de nos deux méthodes renvoie respectivement
la matrice d'adjacence et d'incidence que nous savons juste.
*/
}
TEST_CASE("Test d'ajout de sommets'", "[graphe]"){
On vérifie que le constructeur de sommet a bien été appelé en verifiant que ce sommet a bien été ajouté à la liste des sommets du graphe.
}
TEST_CASE("Test suppression de sommet", "[graphe]"){
/*
On ajoute un sommet à un graphe G, avec un id définit.
s_Test = Sommet(0)
Puis on utilise la méthode et puis on vérifie que le sommet n'est plus
dans la liste des sommets du graphe.
*/
}
TEST_CASE("Test d'ajout d'arcs", "[graphe]"){
On vérifie que le constructeur d'arc a bien été appelé en verifiant que cet arc a bien été ajouté à la liste des arcs du graphe.
}
TEST_CASE("Test de suppression d'arcs", "[graphe]"){
}
TEST_CASE("Test de la convertion en liste de voisins", "[graphe]"){
}
```
## Matrice
```c++
class Matrice {
private :
int taille_V; // nombre de sommets
int taille_E; // nombre d'arcs (dans le cas d'une matrice d'incidence)
bool type; // type de la matrice (0->adjacence,1->incidence)
int **tab; // matrice
public :
bool operator==(Matrice const& matrice1);/*On compare si deux matrices sont égales c'est à dire si le this.taille_V == matrice1.taille_V et this.taille_E == matrice1.taille_E et this.type == matrice1.type et this.tab[][] == matrice1.tab[][] */
Matrice & operator=(Matrice const& matrice1);/* Cette surcharge d'opérateur permet de copier la matrice matrice1 dans une nouvelle matrice créée. On copie : taille_V, taille_E, type, **tab */
Matrice (int taille_V, Graphe G); /* constructeur cas d'adjacence, met
le poids des arcs dans la matrice si il y en a sinon met des 1 et des 0.*/
Matrice (int taille_V, int taille_E, Graphe G); // constructeur cas incidence
~Matrice() // destructeur
get; // getter de tous les attributs privés
set; // setter de tous les attributs privés
Matrice convert_incidence (); /* conversion d'une matrice
d'adjacence en matrice d'incidence */
Matrice inverse_matrice (); /* Renvoie une copie de l'inverse une matrice en mettant des arcs là où il n'y en a pas et en supprimant les arcs présents */
int sommet_Non_Isole(M); /* Renvoie un 1 si la matrice d'un graphe G contient aucun sommet isolé. Renvoie 0 si la matrice contient 1 sommet ou plus sans arc. */
Graphe convertToGraphe();
/*
Permet de créer un graphe avec les informations stockés dans une matrice M.
*/
};
```
### test matrice
```c++
TEST_CASE ("Test de l'operateur =", "[arc]"
/*
test si l'objet Matrice passé en argument est bien égal à l'objet Matrice renvoyé
*/
TEST_CASE ("Test de l'operateur ==", "[arc]"
/*
test si le booléen renvoyé est bien conforme à la comparaison de l'objet Matrice en argument et celle de l'objet Matrice this
*/
TEST_CASE("Test des constructeurs", "[matrice]"){
/*
Test du constructeur de matrice d'adjacence avec les valeurs Matrice(V,G)
Test du constructeur de matrice d'incidence avec les valeurs Matrice(V,E,G)
Les constructeurs sont testés en vérifiant qu'ils ne soient pas null.
*/
}
TEST_CASE("Test du destructeur", "[matrice]"){
/*
Le destructeur est testé avec une matrice existante puis par vérification qu'elle est bien détruite.
*/
}
TEST_CASE("Test des getters", "[matrice]"){
/*
Les getters sont testés, par vérification des données renvoyées.
*/
}
TEST_CASE("Test des setters", "[matrice]"){
/*
Les setters sont testés, en modifiant les données avec la méthode par vérification des données renvoyées.
*/
}
TEST_CASE("Test de conversion en matrice d'incidence", "[matrice]"){
/*
La conversion de la matrice d'adjacence en matrice d'incidence est testée par comparaison des deux matrices.
*/
}
TEST_CASE("Test d'inversion de la matrice'", "[matrice]"){
/*
L'inversion de la matrice est testée.
Une matrice M et son inverse M_inverse sont créées, puis la méthode
d'inversion est appellée sur M. La matrice obtenue est ensuite comparée avec M_inverse.
M = 0 1 0 M_inverse = 0 0 1
1 0 0 0 0 1
0 0 0 1 1 0
*/
}
TEST_CASE("Test de la conversion en graphe", "[matrice]"){
/*
La conversion d'une matrice en graphe est testée. Pour cela une matrice
M et un graphe G_convert correspondant à cette matrice sont préalablement
créés. La méthode est appellée sur la matrice M puis le graphe obtenu
est vérifié par comparaison avec le graphe G_invert.
*/
TEST_CASE("Test de sommet isolé d'un graphe", "[matrice]"){
/*
On vérifie, si pour un resultat retourné, le bon test est effectué.
Pour 1 : Tous les sommets du graphes ont, au moins, un arc.
Pour 0 : le graphe a au moins un sommet sans arc.
*/
}
```
Sign in with Wallet
Connect another wallet