Implantation de Ford Fulkerson#
Recherche de chaîne augmentante#
Dans le fichier flow.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][2] > 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 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é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 du code pour correction:
from utils import show_source
show_source(maximal_flow)