Mini projet en C++

Objectifs
Manipuler des graphes et des sous-graphes orientés.
Utiliser des structures de données d'une bibliothèque normalisée (les conteneurs de la Bibliothèque standard de C++).
Implémenter un algorithme de parcours d'un graphe.
Appliquer les graphes à une problématique.
Problématique
Dans ce travail, on va s'intéresser à un système financier où plusieurs institutions sont liées entre elles par des prêts et/ou des dettes. On va notamment chercher les dettes ou les prêts circulaires qui peuvent être réduits. Pour ce faire, on va d'abord modiliser un système financier avec un graphe orienté, en suivant les étapes de construction suivantes,
Chaque institution sera représentée par un sommet dans le graphe.
Si une institution u a prêté une somme d'argent X à une institution v, alors on ajoutera un arc (u,v) avec le poids X au graphe.
La somme X doit être strictement positive.
Un arc (u,v) peut être vu comme une dette pour v et un prêt pour u.
On pourra donc modéliser un graphe on représentant chacun de ces sommets et tous ses arcs sortants (une liste d'adjacence) ce qui donne un fichier texte comme celui-ci,
ATB (BIC,1700) (BNP,3050) (CIC,7622)
AXA (BNP,9200)
BEA (ATB,2100) (AXA,1100) (BOC,3900) (ING,9390)
BIC (BMO,3012) (BNP,3220)
BMO (AXA,3440) (BOA,2410) (NBG,3240)
BNC (BEA,4500) (NBG,4710)
BNP (BEA,5000) (BMO,4000)
BNS (BIC,5320) (BOA,6370) (CIC,2313)
BOA (NBG,7400) (RBC,5100)
BOC (AXA,2200) (NBG,1740)
CIC (ING,4200) (LCL,5500)
ING (ATB,1700) (BNC,1302)
LCL (BNS,8010) (BOA,3900) (RBC,4420)
NBG (AXA,1500) (LCL,5320)
RBC (NBG,3800)
Qu'on peut représenter par le graphe suivant,

Dette circulaire
Dans un tel graphe on peut trouver des dettes circulaires comme par exemple,
l'institution BNP qui a prêté à BEA
  l'institution BEA qui a prêté à ATB
    l'institution ATB qui a prêté à BIC
      l'institution BIC qui a prêté à BMO
        l'institution BMO qui a prêté à AXA
          l'institution AXA qui a prêté à BNP
On part donc de l'institution BNP et on revient à cette même institution. Par conséquent, il est possible de réduire l'ensemble de ces dettes circulaires en les réduisant toutes en fonction de la plus basse. On peut donc représenter cette dette circulaire de l'institution BNP par le graphe suivant,

Et on pourra réduire toutes ces dettes cirulaires de 1700 (la plus petite dette dans le circuit décrit plus haut), ce qui donnera,

Évidemment, comme la dette entre l'institution ATB et BIC tombe à 0 l'arc (ATB,BIC) sera supprimé.

Remarque. Dans ce qui suit, on considère que des chemins (et par extention les circuits) simples et élémentaires. C'est-à-dire qu'un chemin ne passe pas deux fois par le même sommet ou le même arc.
Réduction
On va donc s'intéresser à implémenter cette réduction pour une institution donnée autant de fois que c'est possible (jusqu'à ce que ça ne soit plus possible). En résumé, pour une institution donnée
Il faut trouver toutes les dettes circulaires qui partent d'une institution donnée, donc un circuit de dettes dans le graphe qui commence à l'institution donnée en paramètre.
Diminuer toutes les dettes du circuit par la plus petite dette, un arc sera donc supprimé à la fin.
On refait la même chose autant de fois que possible.
On procédera par ordre alphabétique si plusieurs institutions sont accessibles en même temps.
Exemple de réduction complète pour l'institution BNP
Réduction de groupe
Plusieurs institutions peuvent s'entendre pour former une coopérative et se partager les dettes entre elles. Une réduction de groupe va faire la même chose qu'une réduction pour une institution, à l'exception qu'on ne cherche par forcément un circuit, mais plutôt un chemin qui part de n'importe quelle institution de la coopérative et se termine dès qu'une institution de la coopérative a été atteinte (pas nécessairement la même institution de départ). Une fois qu'un tel chemin est trouvé, on réduit les dettes qui y figurent de la même manière que la réduction précédente, en plus d'un traitement particulier si l'institution de départ du chemin n'est pas la même que l'institution d'arrivée. Dans ce cas, on devra mettre à jour l'arc entre ces deux institutions s'il existe, ou en créé un nouveau.
On suivra donc les étapes suivantes pour une réduction de groupe ou de coopérative,
Il faut trouver tous les chemins qui partent de n'importe quelle institution de la coopérative et qui reviennent vers n'importe quelle institution de la coopérative.
Attention ces chemins doivent quitter la coopérative dès le départ, la réduction ne traite pas les chemins internes à la coopérative. Donc au départ, il faut absulument qu'on sort de la coopérative et dès qu'on y retourne on s'arrête.
Diminuer toutes les dettes du chemin par la plus petite dette min, un arc sera donc supprimé à la fin.
Si on suppose que l'institution de départ est u et l'institution d'arrivée est v, on aura le traitement suivant qui suivra l'étape précédente,
Si u = v rien ne sera fait (on a affaire à un circuit et la diminution est identique à la précédente).
Si non, on vérifie les cas suivants,
si un arc (u,v) existe, alors son poids sera augmenté de min.
si non, si un arc (v,u) existe, alors son poids sera diminué de min.
si aucun arc n'existe entre u et v, alors un nouvel arc (u,v) sera créé avec le poids min.
On refait la même chose autant de fois que possible.
On procédera par ordre alphabétique si plusieurs institutions sont accessibles en même temps.
Exemple de réduction complète pour la coopération d'institutions ATB,AXA,BEA,BIC,BMO,BNP
Tâches
Le TP3 consiste à terminer l'implémentation de la classe générique Digraph (fichier digraph.hpp) qui implémente la structure de données représentant un graphe orienté. Vous devez notamment implémenter,

les fonctions pour les caractéristiques de graphe;
les fonctions modificatrices;
les fonctions financières;
les réductions.
Structure du programme
Un squelette de départ est disponible dans tp3.zip.

Ce squelette vous est fourni pour vous aider à vous concentrer sur l'essentiel du TP3.
Vous êtes tenu de respecter ce squelette et notamment,
vous n'avez pas le droit de changer l'interface publique de la classe Digraph (donc aucune nouvelle fonction publique);
vous ne pouvez pas changer les signatures de ces fonctions publiques;
vous ne pouvez pas changer la représentation d'un graphe (vous ne pouvez donc pas ajouter de nouveaux attributs/variables privés ou publics);
vous ne pouvez ajouter aucune directive #include, vous devez tout implémenter avec les include déjà fournis.
À l'exception des conteneurs présent sur cette page, c'est les seuls include que vous pouvez ajouter (vous pouvez par exemple décommenter #include <vector> et utiliser les fonctions de ce conteneur du moment que c'est disponible dans le standard C++11).
vous devez implémenter toutes les fonctions citées.
Ceci dit, vous pouvez y ajouter toutes les fonctions privées que vous souhaitez ou jugez nécessaires.
N'oubliez pas de commenter les fonctions que vous ajoutées.
Ce squelette vise d'abord la simplicité pour obtenir rapidement un programme fonctionnel.
Les tests unitaires de ce travail sont basés sur les fonctions de ce squelette.
Performances à satisfaire pour la classe Digraph
Faites très attention à vos implémentations. Les graphes sont des structures qui grandissent très vites et les algorithmes deviennent très vite exponentiels en temps d'exécution par rapport aux nombre de sommets ou nombre d'arcs.
Faites donc attention aux compléxités grand-O de vos implémentations.
⚠️ Attention, tout test qui dépasse les 8 secondes de temps d'exécution sera considéré comme un échec. ⚠️

Travail à faire
Vous devez compléter le fichier digraph.h. Il contient la classe Digraph<T> dont vous devez implémenter les fonctions déclarées. Rappel que vous ne devez pas changer les signatures et les valeurs retournées des fonctions à implémenter dans cette classe.