### Flot Maximum ###
# Le problème de l'autoroute #

Auteurs : Yoann EICHELBERGER & Vivien VAUDRY

A. Préambule :
    Récupérer sur Eureka l'archive maxflow. Elle contient le code d'un algorithme de flot max et celui du test de cet algorithme sur un exemple. Observez la construction du graphe dans GS. Résoudre le problème de flot max et vérifier la solution. Testez avec un second exemple (du cours ou construit par vous).

B.  Construire le graphe associé au réseau routier et le mettre sous forme d'un fichier DGS.

   >[Fichier highway.dgs](src/main/resources/highway.dgs)

C.  Donnez la solution du problème de flot max en utilisant l'algorithme mis à votre disposition. Vous afficherez le réseau, les valeurs du flot sur les arêtes, et vous mettrez en évidence les arêtes saturées.

   ![Flot Max du réseau](data/MaxFlow.png)

D.  AVANT de tester toutes les solutions pour la question 2), que pouvez-vous déduire du flot max sur le réseau routier ?

   > D'après le schéma ci dessus, on peut voir que ce réseau n'est pas du tout optimal, en effet l'arête [AB] n'est qu'à 40% de sa capacité, et toutes les arêtes qui partent de C ne sont pas suffisamment dimensionnées pour transmettre efficacemment le flux disponible depuis la source A.
   Enfin, la capacité de la source A n'est atteinte qu'à 50% tandis que la capacité du puit I n'est que d'environ 60%.\
   En conclusion, il n'y a donc que la moitié du flot disponible dans ce réseau routier qui est tranmis de A vers I.

E.  Donnez les flots successifs en justifiant qu'il s'agit bien à chaque fois du tronçon qui augmente le plus la valeur courante du flot. Commentez.

   >Dans un premier temps, on peut se dire que la première arête à augmenter est [CD], ce qui permettrait d'augmenter la capacité d'évacuation de C et ainsi augmenter le flot de [AC] de 500 à 700. Sauf que dans ce cas, [GI] est toujours saturé de même pour [DH], donc l'augmentation du flot ne peut pas passer entre [HI]. Notre réseau est toujours avec un flot max de 800.\
   En revanche, on remarque également que les segments [AB], [BD], [DG] sont très peu exploités du fait de la faible capacité de [DH]; Donc si nous augmentons la capacité de cette arête, nous pourrons profiter de la forte capacité inexploitée de [HI] et ainsi passer d'un flot max avant travaux de 800 voitures à lheure, à un nouveau flot max de 1200 voitures comme nous pouvons le voir sur la capture ci-dessous : 

![Flot Max du réseau S1](data/MaxFlow_s1.png)

   >Pour optimiser encore plus la circulation, nous constatons que l'arête [CF] est limitante pour que [FH] et [HI] soient maximales, mais ce segment ne faisant pas parti de nos options de modifications, nous devrons augmenter la capacité maximale de [CD], ainsi les 200 unités disponible de A vers C passerons par D puis par H pour finalement saturer l'arête [HI] comme nous pouvons le voir sur la capture ci-dessous :

![Flot Max du réseau S2](data/MaxFlow_s2.png)

   >Finalement, en augmentant la capacité de seulement 2 arêtes, nous avons réussi à atteindre la capacité optimale du puit I avec un flot de 1400 voiture/heure.


F.  Votre compte-rendu devra comporter : le fichier dgs initial et le graphe associé, les différents flots obtenus, et un texte répondant aux questions et expliquant comment vous avez obtenu ces réponses.