Implantation de Ford-Fulkerson

Recherche de chaîne augmentante

Exercice

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

Indication

Lorsque vous changez flow.py, il faut à minima reconstruire l’exemple ci-dessous pour qu’il utilise votre nouveau code. Dans le doute, redémarrez le noyau.

%load_ext autoreload
%autoreload 2
from flow import Flow
from flow_examples import flow_examples

F = flow_examples.example1()
F.show()

F.find_augmenting_path()

F.is_augmenting_path(F.find_augmenting_path())

from flow import Flow
from flow_examples import flow_examples
F = flow_examples.example1()
assert F.is_augmenting_path(F.find_augmenting_path())
F = flow_examples.empty_flow()
assert F.is_augmenting_path(F.find_augmenting_path())
F = flow_examples.small_example()
assert F.is_augmenting_path(F.find_augmenting_path())
F = flow_examples.small_example2()
assert F.find_augmenting_path() is None

Affichage du code pour correction :

from utils import show_source
show_source(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 du code pour correction:

from utils import show_source
show_source(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éé le flot vide correspondant à 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 du code pour correction:

from utils import show_source
show_source(maximal_flow)

from utils import code_checker
code_checker("ruff check --ignore E741 --exclude nbgrader_config.py")

Vérification statique de types :

code_checker("mypy .")

Conclusion

Après la description théorique de l’algorithme de Ford-Fulkerson dans la feuille précédente et son implantation dans cette feuille, vous allez, dans la feuille suivante, aborder une première application de cet algorithme.