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)