# Spécifications du module Operations sur les Graphes
###### tags: `specs`

[TOC]
## Introduction
Le module d'opération des graphes, présent dans la bibliothèque, permet à l'utilisateur tiers tout comme à notre application d'utiliser les différents algorithmes sur nos structures de graphes et de matrice. Les différentes fonctions utilisent des matrices ou l'objet Graphe, en fonction des besoins de l'algorithme et pour éviter un surplus de données inutile.
Le formalisme choisis du graphe (matrice, liste de voisin ou objet graphe), provient du module "gestion de graphe" auquel le module peut renvoyer un graphe modifié, principalement dans le cas d'utilisation de la biliothèque par un développeur tiers.
L'exécution des algorithmes est commandé par l'interface graphique sur des graphes qu'elle fournit sous forme d'objet. Le module d'opération sur les graphes lui renverra alors une liste de sommet (sous forme de vecteur), un sous graphe (sous forme d'objet), ou un message d'erreur.

## Calcul du plus court chemin
### Calcul du plus court chemin avec Ford-Bellman

pair <vector<vector<int>>, vector<int>> calc_pcc_Bellman(Matrice M, Sommet S){
/*      
    Entrée : Matrice d'adjacente graphe permettant d'avoir l'ensemble des sommets et des Arcs
    ainsi que le sommet S (le départ des plus courts chemins).
    Sortie : pair <vector<vector<int>>, vector<int>> qui est composé de deux vecteurs, le premier en position 0 est composé de vecteurs décrivant le chemin pour aller de S jusqu'au sommet i. 
    Le second c'est un vecteur indiquant la distance entre S et le sommet 
    d ID i.
    
    Permet de calculer le plus court chemin entre un sommet S et tous les 
    autres sommets du graphe et renvoie une pair avec les chemins et les
    distance de S à tous les autres sommets, pour ce faire on
    utilisera l algorithme de Ford Bellman.
*/
}

La pair retournée par calc_pcc_Bellman a une structure particulière, prenons un exemple le graphe nommé G₀ :

graph LR 
1 -->|1| 2
0 -->|1| 1
0 -->|1| 2
1 -->|1| 3
2 -->|1| 3
2 -->|1| 5
3 -->|1| 4

La fonction`calc_pcc_Bellman(G0, 0)` va donc renvoyer : `<<<0>, <0,1>, <0, 2>, <0, 1, 3>, <0, 1, 3, 4>, <0, 2, 5>>, <0, 1, 1, 2, 3, 2>>`.
Il est donc à découper en deux, la *première partie* (`<<0>, <0,1>, <0, 2>, <0, 1, 3>, <0, 1, 3, 4>, <0, 2, 5>>`) représente tous les chemins de 0 à chaque sommet i. Et la *seconde partie* (`<0, 1, 1, 2, 3, 2>`) qui permet d'avoir toutes les distances de 0 à tous les sommets i.
Cette pair, bien que compliqué à lire pour un humain, permet, même dans le cas d'un graphe avec baucoups de sommets de récupérer efficacement les valeurs intéressantes et simplifie donc l'exploitation des résultats.

### Calcul du plus court chemin avec Floyd-Warshall

pair<Matrice, Matrice> calc_pcc_Floyd_Warshall(Matrice M){
    /*
    Entrée : Matrice d adjacence M portant les poids des arcs d'un graphe G.
    Sortie : Deux matrices, une avec le de poids de chemin minimum et une matrice Parent qui
    Permet de renvoyer les chemins de tous les sommets vers tous les sommets sous forme de deux matrices. L'une Parent et l'autre de poids.

    */
}

Exemple le graphe G₀:

graph LR 
1 -->|1| 2
0 -->|1| 1
0 -->|1| 2
1 -->|1| 3
2 -->|1| 3
2 -->|1| 5
3 -->|1| 4

Ce graphe donnera les matrices suivantes :

Matrice de poids      Matrice Parent
  0 1 2 3 4 5          0 1 2 3 4 5 
0|0 1 1 2 3 2|       0|0 1 2 1 1 2| 
1|0 0 1 1 2 2|       1|0 0 2 3 3 2|
2|0 0 0 1 2 1|       2|0 0 0 3 3 5| 
3|0 0 0 0 1 0|       3|0 0 0 0 4 0| 
4|0 0 0 0 0 0|       4|0 0 0 0 0 0|
5|0 0 0 0 0 0|       5|0 0 0 0 0 0|

Ici le poids du plus court chemin entre 1 et 4 c'est 2,
le prochain sommet a atteindre sur le chemin entre 1 et 4 est le sommet 3,si l'on veut la suite du chemin on regarde le prochain sommet en partant de 3 pour aller vers 4 ici c'est 4 donc le chemin de 1 vers 4 est 1->3->4.

vector <int> liste_chemin(Matrice Parent, int deb, int fin);
//cette fonction va décrypter la matrice parent donné par la fonction de Floyd-Warshall.
//Il prend en entré la matrice ainsi que le sommet de depart et le sommet d'arrivé (ID) et renvoie un vecteur d'ID donnant la liste des sommets du plus court chemin entre le sommet de depart et le sommet d'arrivé.

## Calcul des degrés entrant et sortant d'un sommet

int calc_deg_ent(Matrice M, int ID ){
/*
Entrée : Récupère une Matrice M et un ID de Sommet dont on cherche à connaitre le nombre d'arcs entrants.
Sortie : Renvoie le nombre d'arc qui entre dans le sommet S en question.

Cette fonction permet de calculer le degré entrant d'un sommet S appartenant au graphe G.
*/

}

int calc_deg_sor(Sommet S){
/*
Entrée : Récupère un sommet d'un graphe dont on cherche à connaitre le
nombre de sommet sortant.
Sortie : Renvoie le nombre d'arc qui sorte du sommet S.

Cette fonction permet de calculer le degré sortant d'un 
sommet S appartenant au graphe G.
Pour cela il suffit de compter le nombre d'éléments dans S.vecArc
*/
}

pair<int, int> calc_deg_ent_sor(Matrice M, Sommet S){
/*
Entrée : Une Matrice M et un sommet S  
Sortie : Une paire de deux entiers, avec en première position le degrés entrant, 
et en seconde position le degrés sortants.

Cette fonction permet de calculer les degrés entrants et sortants du sommet S
en utilisant les deux fonctions décrites ci-dessus. 
L'utilisation d'une paire de deux entiers en valeur de retour permet de retourner simplement deux entiers.
*/
}

## Coloration de graphes

vector<int> color_graphe(Matrice M){
/*
Entrée : Prend en entrée un Matrice M

Sortie : Renvoie un vecteur, où pour chaque position de ce dernier, un numéro est attribué pour une coloration de sommets.

Cette fonction consiste à attribuer un numéro à chacun de ses sommets de manière à ce que deux sommets reliés par un arc aient un numéro différent.
L'utilisation d'un vecteur en valeur de retour s'explique ici par le besoin d'avoir une structure dynamique qui permet de renvoyer un nombre arbitraire d'entiers dans une structure utilisable. 
*/
}

int coul_adj (Sommet s){
/*
    Entrée: cette fonction prend en entrée un sommet
    Sortie: elle retourne le nombre de couleurs différentes dans les sommets adjacents de S
    
    Cette fonction sera utilisée pour la coloration de graphes
*/
}

## Détermination de stables

Vector<Vector<int>> stables_graphe(Matrice M) 
{
/*
Entrée : Récupère une Matrice M 

Sortie : Renvoie un vecteur contenant les listes des ID des sommets. Pour chacune des listes, les ID sélectionés forment un stable. Cela permet de renvoyer un nombre arbitraire de stable, eux-même composé d'un nombre arbitraire de sommets.

Cette fonction permet de retourner une liste avec tous les stables du graphe G. Pour rappel un stable est un ensemble de sommets deux à deux non adjacents. La taille d'un stable est égale au nombre de sommets qu'il contient. 

*/
}

## Détermination de cliques

Vector< Vector<int>> cliques_graphe(Matrice M)
{
/*

Entrée : Récupère un graphe G et inverse la matrice de ce graphe pour ainsi appeler la méthode : stables_graphe(Gaphe G)

Sortie : Renvoie un vecteur contenant les listes des ID des sommets. Pour chacune des listes, les ID sélectionés forment une clique. Cela permet de renvoyer un nombre arbitraire de clique, eux-même composé d'un nombre arbitraire de sommets.

Cette fonction permet de retourner une liste avec toutes les cliques du graphe G. Pour rappel une clique est un sous-graphe complet. 
*/

## Voisins de sommets

vector<int> voisin_sommet (Matrice M, int id) {
/*
Entrée: Cette fonction prend en entrée la matrice d'adjacence du graphe
auquel appartient le sommet S ainsi que d'id du sommet dont on cherche à
connaître la liste de voisins.
Sortie: Un vecteur contenant les id des sommets voisins de S est retourné.

Le paramètre id permet d'identifier le sommet S pour lequel on veux la 
liste de voisins. La fonction parcours la matrice M à la recherche d'arcs 
existants entre S et les autres sommets du graphe. Si un arc existe, son 
id est stocké dans un vecteur qui contiendra en sortie les id de tous 
les sommets voisins de S.

*/
}

## Gestion des flots

int Edmond_Karp(Graphe G, int ID_source, int ID_puit){
/*
Entrée: Cette fonction prend en entrée le graphe G sur lequel elle doit calculer le flot maximum. Ainsi que les Id des sommets source et puits qui guideront l'algorithme.

Sortie: Flot maximum sous forme d'entier

Explication : Cet algorithme repose sur la mise en place d'un graphe résiduel à partir des capacité des arcs. Grâce à un 
parcours en largeur, on effectuera une augmentation progressive du flot maximum. Si aucune augmentation n'est possible, on renvoie le flot 
maximum sous forme d'un entier. 
Il ajoutera les valeurs de flots à la charge utile de chaque arcs présent dans G.

*/
}

## Ordonnancement

typedef struct ROW{
/*
    Cette structure permet de stocker les informations propres à une tâche.
*/
    int tache; // identifiant de la tâche
    string nom_tache; //etiquette de la tâche
    int duree; //durée de la tâche
    vector <int> taches_anterieurs; //vecteur d'entiers qui contient les id de toutes les tâches anterieures 
    vector <int> taches_posterieures; //vecteur d'entiers qui contient les id de toutes les tâches posterieures. 
} pert_row;

vector<pert_row> calc_post (vector<pert_row>){
/*
Entrée: Cette fonction prend en entrée un vecteur de tâches.
Sortie: elle retourne ce même vecteur de tâches avec les contraintes de posteriorités mises à jour.
*/
}

Graphe pert (vector<pert_row>)
/*
Entrée: Cette fonction prend en entrée un vecteur de pert_row, c'est à dire l'ensemble des tâches.

Sortie: Le graphe construit est retourné.

La fonction créée pour chaque tâche un(des) sommet(s) et des arcs modélisants les contraîntes d'antériorités, le déroulement de la tâche et la fin de tâche.
*/

Exemple de tableau d'entrée:

| tâche | nom de la tâche | durée | tâches antérieures |
| ----- | ----------------------------------- | ----- | ------------------ |
| 1 | analyse du système | 5 | |
| 2 | Planification du projet | 9 | |
| 3 | Conception du système | 10 | 1,2 |
| 4 | Evaluation du materiel informatique | 2 | 3 |
| 5 | Developpement détaillé | 12 | 3 |
| 6 | Mise en oeuvre du système | 7 | 4 |

## Trouver une arborescence/anti-arborescence

Graphe arborescence (Graphe G){
/*
Pré-Algorithme: - Vérification qu'un seul et unique sommet ne possède aucun arcs entrant.
                - On vérifie que chaque sommet est atteignable en partant d'un sommet de départ S.
                
Entrée : Graphe G

Cette fonction prend en entrée le graphe courant, pour chaque sommet soustrait le plus petit poids d'arc entrant du sommet à tous ses arcs entrant.
Puis créé un nouveau graphe en ne gardant que les arcs ayant un poids de 0. Si plusieurs arcs entrant d'un sommet ont un poids de 0, le premier arc sera selectionné. 

Sortie : Renvoie un objet Graphe représentant l'arborescence du graphe G, ce choix est motivé par le besoin de décrire un graphe entier, une arborescence n'est pas qu'une suite de sommet, mais aussi des les relations entre ces derniers. Si aucune arborescence n'existe alors le graphe renvoyé aura comme nombre de sommet la valeur "-1".
*/
}

Graphe anti_arborescence (Graphe G){
/*
Entrée : Graphe G

Cette fonction prend en entrée le graphe courant et pour chaque sommet soustrait le plus petit poids d'arc sortant du sommet à tous ses arcs sortant.
Puis créé un nouveau graphe en ne gardant que les arcs ayant un poids de 0. Si plusieurs arcs sortant d'un sommet ont un poids de 0, le premier arc sera selectionné.

Sortie : Renvoie un objet Graphe représentant l'anti-arboresence du graphe G, ce choix est motivé par le besoin de décrire un graphe entier, une anti-arborescence n'est pas qu'une suite de sommet, mais aussi les relations entre ces derniers. Si aucune anti-arborescence n'existe alors le graphe renvoyé aura comme nombre de sommet la valeur "-1".
*/
}

## Recherche de connexité

 int connexite(Matrice M)
 {
 /*
     Entrée : Matrice d'adjacence M     
     Sortie : Nombre de graphe total (si le graphe est séparé en 2,3 graphe
     non connexe etc ...)
     
Cette fonction prend en entrée la matrice d'adjacence et recherche le nombre de sous
graphe grâce à l'arborescence et l'anti-arborescence de l'arbre du graphe.
 */
 }

## Trouver une chaîne eulérienne

vector<vector<int>> eulerien(Matrice M){
/*
    Entrée: Matrice du graphe courant
    Sortie: un vecteur contenant les listes de chemins eulériens possibles s'il y en a sinon vecteur de listes vides.

Cette fonction prend en entrée le graphe courant. Puis cherche tous les chemins eulériens du même graphe et les renvoie en sortie s'il en trouve.
*/

}

## Trouver une chaîne hamiltonienne

vector<vector<int>> hamiltonien(Matrice M){
/* 
    Entrée : la matrice du graphe courant
    Sortie : un vecteur contenant les listes de chemins  hamiltoniennes possibles s'il y en a sinon vecteur de listes vides.

Cette fonction prend en entrée le graphe courant, puis cherche tous les chemins  hamiltoniens possibles de ce même graphe et les renvoie si l'aglorithme en trouve.
*/

}

## Problème du Postier Chinois

vector<int> postier_chinois(Matrice M){

/*
Entrée : Récupère une matrice M et on vérié si aucun sommets n'est isolé.
Sortie : Renvoie un vecteur contenant les iD du cycle eulérien dans l'ordre de passage.

Cette fonction permet de résoudre le problème du Postier Chinois, en récupérant un cycle eulérien dans un graphe orientée.
  1ère étape :
      - calcul des degrés de chaque sommet O(V²)
  
  2ème étape :  
     si : tous les sommets ont un degré pair O(V)
        -> parcours eulérien pour trouver un cycle eulérien. O(V!)
     sinon 
        -> création d'un graphe G'(donc matrice M') composé uniquement des sommets de degrés impairs, création d'arcs entre chaque sommets (utilisation d'un algo de plus court chemin).
        -> recherche du couplage parfait entre les sommets.
        -> ajout du couplage dans le graphe
        -> parcours eulérien pour trouver le cycle eulérien.
*/

}

## Problème du voyageur de commerce

 vector<int> Voyageur_commerce(vector<int>, Matrice M){
 /*
Entrée: On prend en entrée la liste des sommets sur lequel va travailler l'algorithme et la matrice contenant le poids des arcs reliant ces sommets.
Sortie: Une liste des sommets entrés correspondant au plus court chemin passant par chacun de ces sommets.

Tout d'abord nous devons vérifier que le graphe choisi est complet, c'est à dire qu'il existe un arc entre chaque paire de sommet.
Cette fonction sera séparée en parties distinctes:
1 - Déclaration d'une matrice des regrets entre chacuns des sommets à partir de la liste des sommets entrés. Elle sera de taille n x n où n est le nombre de sommet s entré.
2 - Réduction de la matrice afin d'avoir une valeur à zéro sur chaque ligne et colonne
3 - Calcul du regret pour chaque paire de sommet dont la valeur est nulle (Somme des plus petites valeurs de la ligne et de la colonne)
4 - Recherche du regret maximal obtenue
5 - Ajout de la valeur du regret dans l'arbre
6 - Suppression de la paire de sommet de la matrice
On fait ces étapes autant de fois que la matrice n'est pas entièrement réduite.

-Creation d'arbre:
La racine contient la somme des valeurs retiré lors de la réduction de la matrice

Les feuilles récupéreront la somme du père avec le coût du regret choisi.

Nous regardons ensuite chaque feuille non empruntée par le chemin pour vérifier que la valeur associée soit plus grande que celle de notre feuille de référence.
Si ce n'est pas le cas, alors cela veut dire que le chemin trouvé n'est peut être pas le plus court chemin possible du graphe. On repart alors de la nouvelle plus petite feuille, tout en vérifiant que les valeurs trouvées de ces fils ne soient pas plus grande que celle de référence.


 */
 }
 

complexité de: O(v!)
où s est le nombre de sommets employés et N(s) le nombre de noeuds visités.
- De part la nature de cette formule, on en déduit que si le nombre de sommets analysé augmente, le nombre de noeud augmente exponentiellement. C'est pourquoi quand on dépasse un certain seul de sommets, l'algorithme peut mettre un temps important avant de donner un résultat.

## TESTS

TEST_CASE("Test de Bellman ", "[]"){
/*
    Ce test prendra en paramètre un graphe G dont on connait déjà le plus court chemin puis on vérifiera que le pair retournée par la fonction correspond bien à ce chemin.
*/
}

TEST_CASE("test de Floyd_Warshall", "[]"){
/*
    De la même façon que sur le test précédent, ici sera déclarée une Matrice décrivant un graphe dont on connait d'ores et déjà le plus court chemin.  
    Une paire de matrice décrivant ce résultat sera aussi déclarée permettant de la comparer avec le retour effectif du test.
*/
}

TEST-CASE("test des degres", "[]"){
/* 
    Dans ce test les trois fonctions liées au calcul de degrés seront testées en simultanées.
    Pour cela une matrice d'adjacence décrivant un graphe et un sommet S dudit graphe.
    Le degrès du sommet sera connu à l'avance et on vérifiera que calc_deg_ent et calc_deg_sor renvoient le bon degré chacun. Puis que calc_deg_ent_sor renvoie bien une paire avec ces deux degrés aux bonnes positions. (entrant en position 0 et sortant en position 1). 
*/
}

TEST_CASE("test coloration", "[]"){
/*
    Une matrice décrivant un graphe G dont la coloration est connue est déclarée.
    Le vecteur de retour est comparé avec la coloration de la matrice. Le test est validé s'il s'agit de la même.
*/
}

TEST_CASE("test des stables", "[]"){
/*
    Une matrice d'adjacence décrivant un graphe G dont on connait le nombre de stable est décalrée. 
    Un vecteur de vecteur d'entier décirvant le résultat déjà connu sera comparé avec celui renvoyé par la fonction.
    S'ils sont identiques le test est validé.
*/
}

TEST_CASE("test des cliques", "[]"){
/*
    Une matrice d'adjacence décrivant un graphe G dont on connait le nombre de clique est déclarée. 
    Un vecteur de vecteur d'entier décirvant le résultat déjà connu sera comparé avec celui renvoyé par la fonction.
    S'ils sont identiques le test est validé.
*/
}


TEST_CASE("test des voisins", "[]"){
/*
    Une matrice d'adjacence M est déclarée et l'ID d'un de ses sommets dont on connait les voisins est choisis.
    La liste des voisins du sommet est déclarée sous forme de vecteur d'entier (liste d'ID).
    La matrice M passe dans la fonction avec l'ID du sommet.
    Si la liste renvoyée par la fonction correspond à celle déclarée plus haut alors le test est validé.
*/
}

TEST_CASE("test de la gestion de flots", "[]"){
/*
    Un graphe G, et (les ID ? Les sommets ? ) puits et sources sont choisis sur ce dernier de façon à ce que le flot maximum de ce parcours soit connu.
    Si la fonction renvoie la même valeur que celle prévue plus haut, alors le test est validé.
*/
}

TEST_CASE("test de l'ordonnancement", "[]"){
/*
    Prend une entrée dont on connait déjà le graphe d'ordonnance. 
    Si l'objet graphe retourné est identique 
*/
}

TEST_CASE("test de l'arborescence", "[]"){
/*
    On créer un graphe dont on connait l'arboresence, arboresence qu'on va décrire dans un objet graphe.
    Si le graphe retourné par la fonction est identique à celui créer plus haut alors le test est validé.
*/
}

TEST_CASE("test de l'anti-arborescence", "[]"){
/*
    On créer un graphe dont on connait l'anti-arboresence, arboresence qu'on va décrire dans un objet graphe.
    Si le graphe retourné par la fonction est identique à celui créer plus haut alors le test est validé.
*/
}

TEST_CASE("test detection erreur arborescence", "[]"){
/*
    On va créer un graphe G qui ne remplit pas les conditions de "pré-algorithme" puis on va le passer dans la fonction.
    Si le retour de fonction est le graphe d'erreur (un graphe ayant -1 sommet) alors le test validé.
*/
}

TEST_CASE("test detection erreur anti-arborescence", "[]"){
/*
    On va créer un graphe G qui ne remplit pas les conditions de "pré-algorithme" puis on va le passer dans la fonction.
    Si le retour de fonction est le graphe d'erreur (un graphe ayant -1 sommet) alors le test validé.
*/
}

TEST_CASE("test de la connexite", "[]"){
/*
   Nous allons créer un graphe G connexe.
   Si le retour de la fonction est correct dans chaque cas, nous estimons que le test est validé.
*/
}

TEST_CASE("test des chaines ", "[]"){
/*
    test de la fonction eulerien.
    test de la fonction hamiltonien.
    
    Nous allons créer un Graphe G dont les chaînes hamiltonienne et eulérienne sont connues et vérifier les listes renvoyés par les deux fonctions. 
    Si les chaines renvoyées sont correct, le test est réussis.
   
    
*/
}

TEST_CASE("test detection erreur des chaines"){
/*
Nous ferons de même avec un graphe G' qui n'est ni Hamiltonien ni Eulérien. 
Si les listes renvoyés par les fonctions eulerien et hamiltonien sont vide, alors le test est validé.
*/
}

TEST_CASE("test du postier chinois", "[]"){
/*
    test de la fonction postier_chinois.
    
    On met un graphe dans lequel, on sait qu'on peut appliquer l'algorithme du postier chinois.
    
    On test, pour un degré total impair, la création d'un G' est bien effectué.
    On vérifie également, si l'algorithme renvois bien un vecteur de listes d'ID.
    
*/
}

TEST_CASE("test du voyageur de commerce", "[]"){
/*  
    On fait un test pour vérifier que la Matrice prise en entrée est complète (C'est à dire qu'il y a un arc entre chaque paires de sommets pris en entrée).
    On déclare une matrice décrivant un graphe sur lequel on connait le résultat du voyageur de commerce en fonction de certain sommets.
    Les ID de ces sommets seront passés dans un vecteur d'entiers.
    La liste des sommets décrivant le plus court chemin sera elle aussi déclarée.
    Si le résultat de la fonction correspond avec ce dernier alors le test est validé.
*/
}