# Implantation de Ford Fulkerson¶

## Recherche de chaîne augmentante¶

Dans le fichier `flots.py`, implantez les méthodes `find_augmenting_path` et `increase_augmenting_path`. Testez vos fonctions ci-dessous.

N’oubliez pas de redémarrer le noyau quand vous changez les fichiers importés

```from flow import Flow
from flow_examples import flow_examples
```
```F = flow_examples.example1()
F.show()
```
```F.find_augmenting_path()
```
```def is_augmenting_path(F, path):
source = path[0][0]
if not source == F.source():
print("Mauvaise source")
return False
target = path[-1][1] if path[-1][1] > 0 else path[-1][0]
if not target == F.target():
print("Mauvaise cible")
return False
for a,b,c in path:
if c > 0:
if not F.flow(a,b) + c == F.capacity(a,b):
print("Mauvais potentiel sur", a,b,c)
return False
elif c < 0:
if not -c == F.flow(a,b):
print("Mauvais potentiel sur",a,b,c)
return False
else:
print("Potentiel nul sur",a,b,c)
return False
return True
```
```is_augmenting_path(F, F.find_augmenting_path())
```
```from flow import Flow
from flow_examples import flow_examples
F = flow_examples.example1()
assert is_augmenting_path(F, F.find_augmenting_path())
F = flow_examples.empty_flow()
assert is_augmenting_path(F, F.find_augmenting_path())
F = flow_examples.small_example()
assert is_augmenting_path(F, F.find_augmenting_path())
F = flow_examples.small_example2()
assert F.find_augmenting_path() is None
```
```# affichage de la source pour correction
import inspect
print(inspect.getsource(Flow.find_augmenting_path))
```
```F = flow_examples.example1()
F.show()
```
```F.increase_augmenting_path([(0, 2, 1), (5, 2, -1), (5, 6, 3)])
F.show()
```
```from flow import Flow
from flow_examples import flow_examples
F = flow_examples.example1()
F.increase_augmenting_path([(0, 2, 1), (5, 2, -1), (5, 6, 3)])
assert F.flow(0,2) == 2
assert F.flow(5,2) == 0
assert F.flow(5,6) == 2
F = flow_examples.empty_flow()
F.increase_augmenting_path(F.find_augmenting_path())
assert F.check_in_out()
assert F.check_capacity()
```
```# affichage de la source pour correction
import inspect
print(inspect.getsource(Flow.increase_augmenting_path))
```

## Algorithme de Ford-Fulkerson¶

En utilisant les méthodes précédentes, implantez l’algorithme de Ford-Fulkerson dans le fichier `ford_fulkerson.py`.

La fonction prend en paramètre un réseau, crée le flot vide corresponant à ce réseau puis applique l’algorithme pour maximiser le flot.

Testez ci-dessous.

N’oubliez pas de redémarrer le noyau quand vous changez les fichiers importés

```from flow import Flow
from flow_examples import flow_examples
from network import Network
from network import examples
from ford_fulkerson import maximal_flow
```
```N = examples.example1()
F = maximal_flow(N,0,6)
```
```F.show()
```
```F.global_value()
```
```from flow import Flow
from flow_examples import flow_examples
from network import Network
from network import examples
from ford_fulkerson import maximal_flow
F = maximal_flow(examples.example1(),0,6)
assert F.check_in_out()
assert F.check_capacity()
assert F.global_value() == 4
F = maximal_flow(examples.small_example(),0,3)
assert F.check_in_out()
assert F.check_capacity()
assert F.global_value() == 6
F = maximal_flow(examples.small_example2(),0,3)
assert F.check_in_out()
assert F.check_capacity()
assert F.global_value() == 9
```
```# affichage de la source pour correction
import inspect
print(inspect.getsource(maximal_flow))
```