Newer
Older
# 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)
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 :
### 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.
Première réponse (incorrecte), [Réponse correcte](#E_(Correcte))
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());
```
Coupe minimale du graphe d'origine
Avec la première itération, on trouve:
`Best edge to improve : DH[D->H]`
`Flow arriving to the sink : 1400`
Coupe minimale après la première itération
Avec la deuxième itération:
`Best edge to improve : BD[B->D]`
`Flow arriving to the sink : 1500`
Coupe minimale après la deuxième itération
Chaque coupe minimale passe par des arêtes saturées, chaque unité de flot qui va de la source vers la destination (A -> I) n'a pas le choix que de passer par au moins une de ces arêtes.
De ce fait, en faisant la somme des capacités de ces arêtes, on déduit que notre flot est optimal car le flot reçu par la destination correspond à la somme des capacités des arêtes de la coupe minimale.
On arrive à un flot de 1500, c'est le flot qui est envoyé par la source, ce flot est donc optimal, nous n'avons pas besoin d'itérer plus que ça.
###E (Correcte)
Nous nous sommes rendu compte que nous devions uniquement modifier les arêtes entre les sommets A, C, D, H et I, nous avons donc modifié le programme pour correspondre à ce besoin.
On ajoute donc ce morceau de code pour limiter les arêtes à modifier:
```java
String idsToUpdate = "A,C,D,H,I";
List<String> nodesToUpdate = Arrays.asList(idsToUpdate.split(","));
Stream<Edge> edgesToUpdate = g.edges().filter(e -> nodesToUpdate.contains(e.getNode0().getId()) && nodesToUpdate.contains(e.getNode1().getId()));
```
Et on applique l'algorithme de la première réponse à la question uniquement sur ces arêtes.
On trouve en premier à améliorer le tronçon DH, ce qui ne change pas de notre première réponse.
Cependant on trouve en deuxième amélioration le tronçon A-C : `Best edge to improve : AC[A->C]`, `Flow arriving to the sink : 1400`
Cela ne change pas le flot qui arrive à destination mais ça va nous permettre de l'améliorer à la prochaine itération.
On peut garder la même coupe minimum qu'à notre première réponse.
Ensuite, on trouve que le meilleur tronçon est C-D : `Best edge to improve : CD[C->D]`, `Flow arriving to the sink : 1500`.
Cela amène le flot à 1500, comme coupe minimum, on peut prendre ce qu'on avait dans la première réponse mais uniquement la coupe de droite, les arêtes G-I et H-I.
Le dernier meilleur tronçon à améliorer est donc H-I.