# TP Flots max RI
### Drouard Anne-Laure - Quentin Vauthier

## Introduction
Pour commencer, nous avons modifié le programme MaxFlow qui n'était pas à jour avec la version 2.0 de graphstream.

Nous avons testé que le programme fonctionne correctement, et ce fût le cas.

[Fichier DGS initial du réseau routier](resources/autoroute.dgs)

### C)

#### Graphe avec les arètes saturées

![graphe](resources/graphe.png)

Le flot que l'on obtient est maximum car on peut voir sur le graphe résiduel obtenu avec l'algorithme de Ford et Fulkerson que les noeuds H et I sont isolés du reste (aucune arète les rejoint) donc pas de chemin entre A et I :

![graphe](resources/grapheResiduel.png)

### D)
On peut en déduire que le flot n'est pas optimal car le flotmax avec les capacités actuelles nous donne uniquement 900 à l'arrivée.
En augmentant les capacités de certains arcs, on devrait arriver à augmenter le flotmax pour que avoir un flot optimal.

### E)
On va calculer quels sont les meilleures arêtes sur lesquelles il est optimal d'augmenter la capacité grâce à ce code:
```java
// Calcul de l'arête à augmenter pour améliorer le flot
AtomicReference<Edge> improveEdge = new AtomicReference<>();
AtomicReference<Integer> flowToSink = new AtomicReference<>(0);
g.edges().forEach((Edge e) -> { // Pour chaque arête du graphe
    int cap = (int) e.getAttribute("cap"); // On stocke la capacité
    // On augmente la capacité à 2500 (valeur arbitraire basée sur le sujet scané)
    e.setAttribute("cap", 2500); 
    MaxFlow maxFlow = new MaxFlow(); // On reconfigure un maxflow
    maxFlow.setCapacityAttribute("cap");
    maxFlow.init(g);
    maxFlow.setSource(source);
    maxFlow.setSink(sink);
    maxFlow.compute();
    // On calcule le flot arrivant au sink
    Double tempFlowToSink = sink.enteringEdges().reduce(0.0, (acc, entering) -> {
        return acc + maxFlow.getFlow(entering);
    }, Double::sum);
    // Si le flot est plus élevé que précédemment calculé, alors on stocke l'arête augmentée 
    // et la valeur du flot entrant dans la destination
    if(tempFlowToSink > flowToSink.get()) {
        improveEdge.set(e);
        flowToSink.set(tempFlowToSink.intValue());
    }
    // On n'oublie pa de remettre la capacité initiale de l'arête pour les prochains calculs
    e.setAttribute("cap", cap);
});
System.out.println("Best edge to improve : " + improveEdge.get());
System.out.println("Flow arriving to the sink : " + flowToSink.get());
```

Avec la première itération, on trouve:
`Best edge to improve : DH[D->H]`
`Flow arriving to the sink : 1400`

Avec la deuxième itération:
`Best edge to improve : BD[B->D]`
`Flow arriving to the sink : 1500`