====== TP4 ======
Le but de ce TP est d'appliquer la théorie des flots dans les graphes à des problèmes concrets.
Le fait de tester toutes vos créations n'est plus explicitement demandé car cela doit **encore & toujours** être fait.
Les graphes seront représentés "mathématiquement" par des listes d'adjacence, & plus précisément/concrètement par des dictionnaires de dictionnaires de dictionnaires. Par exemple :
CAPACITE = "capacite"
FLUX = "flux"
the_graph = {1: {2: {CAPACITE: 5, FLUX: 2}, 3:{CAPACITE: 6, FLUX: 1}},
2: {3: {CAPACITE: 7, FLUX: 1}, 4: {CAPACITE: 8, FLUX: 1}},
3: {5: {CAPACITE: 4, FLUX: 2}},
4: {6: {CAPACITE: 3, FLUX: 2}},
5: {4: {CAPACITE: 6, FLUX: 1}, 6: {CAPACITE: 8, FLUX: 1}},
6: {}
}
Dessinez le graphe ci-dessus.
Implémentez l'Algorithme de Ford & Fulkerson. On pourra utiliser les fonctions suivantes :
import math
INFINI = math.inf
CAPACITE = "capacite"
FLUX = "flux"
def mise_a_zero_flot(graph):
for sommet in graph:
for voisin in graph[sommet]:
graph[sommet][voisin][FLUX] = 0
def construction_graphe_ecart(graphe_antisymetrique):
graphe_ecart = {}
for sommet in graphe_antisymetrique:
graphe_ecart[sommet] = {}
for sommet in graphe_antisymetrique:
for voisin in graphe_antisymetrique[sommet]:
capacite = graphe_antisymetrique[sommet][voisin][CAPACITE]
flux = graphe_antisymetrique[sommet][voisin][FLUX]
if capacite > flux:
graphe_ecart[sommet][voisin] = capacite - flux
if flux > 0:
graphe_ecart[voisin][sommet] = flux
return graphe_ecart
def construction_chemin_via_dfs(graphe_ecart, source, puits):
sommets_marques = {}
antecedents = {}
pile = [source]
for sommet in graphe_ecart:
antecedents[sommet] = None
while pile != []:
sommet = pile.pop()
if sommet not in sommets_marques:
sommets_marques[sommet] = True
for voisin in graphe_ecart[sommet]:
if voisin not in sommets_marques:
antecedents[voisin] = sommet
pile.append(voisin)
if sommet == puits:
return construction_effective_chemin(sommet, antecedents)
def construction_effective_chemin(sommet, antecedents):
chemin = []
while sommet is not None:
chemin.append(sommet)
sommet = antecedents[sommet]
chemin.reverse()
return chemin
def min_sur_chemin(chemin, graphe_ecart):
minimum = INFINI
for i in range(len(chemin) - 1):
courant = chemin[i]
suivant = chemin[i + 1]
if graphe_ecart[courant][suivant] < minimum:
minimum = graphe_ecart[courant][suivant]
return minimum
def ajout_flot(valeur, chemin, graphe_antisymetrique):
for i in range(len(chemin) - 1):
courant = chemin[i]
suivant = chemin[i + 1]
if suivant in graphe_antisymetrique[courant]:
graphe_antisymetrique[courant][suivant][FLUX] += valeur
else:
graphe_antisymetrique[suivant][courant][FLUX] -= valeur
Dans la fonction construction_graphe_ecart, le résultat graphe_ecart est-il représenté comme the_graph. Pourquoi ?
Dans un deuxième temps, on l'appliquera au problème du mariage avec les données suivantes :
CLEOPATRE = "Cleopatre"
IPHIGENIE = "Iphigenie"
JULIETTE = "Juliette"
FANNY = "Fanny"
CHIMENE = "Chimene"
ACHILLE = "Achille"
CESAR = "Cesar"
RODRIGUE = "Rodrigue"
ROMEO = "Romeo"
MARIUS = "Marius"
LES_COUPLES = [(CLEOPATRE, ACHILLE), (CLEOPATRE, CESAR), (CLEOPATRE, ROMEO),
(IPHIGENIE, ACHILLE), (JULIETTE, CESAR), (JULIETTE, RODRIGUE), (JULIETTE, ROMEO),
(FANNY, CESAR), (FANNY, MARIUS), (CHIMENE, RODRIGUE), (CHIMENE, ROMEO)]
On résoudra après le problème de "la bataille de la Marne", en supposant que,
* Au temps 0, on a autant de taxis que nécessaire dans la ville 14 ("Paris").
* Au temps 50, il faut qu'il y en ait le plus possible dans la ville 0 ("La Marne").
* Chaque ville (intermédiaire) a 10 places de parking (Paris en a autant que nécessaire).
* Les routes sont données dans le tableau suivant :
LES_ROUTES = [{'depart': 0, 'capacite': 2, 'arrivee': 1, 'longueur': 5},
{'depart': 0, 'capacite': 3, 'arrivee': 2, 'longueur': 3},
{'depart': 0, 'capacite': 6, 'arrivee': 1, 'longueur': 6},
{'depart': 1, 'capacite': 3, 'arrivee': 2, 'longueur': 6},
{'depart': 1, 'capacite': 7, 'arrivee': 4, 'longueur': 7},
{'depart': 1, 'capacite': 6, 'arrivee': 2, 'longueur': 7},
{'depart': 2, 'capacite': 7, 'arrivee': 4, 'longueur': 4},
{'depart': 2, 'capacite': 6, 'arrivee': 4, 'longueur': 8},
{'depart': 2, 'capacite': 2, 'arrivee': 5, 'longueur': 5},
{'depart': 3, 'capacite': 7, 'arrivee': 5, 'longueur': 5},
{'depart': 3, 'capacite': 3, 'arrivee': 5, 'longueur': 4},
{'depart': 3, 'capacite': 7, 'arrivee': 6, 'longueur': 4},
{'depart': 4, 'capacite': 7, 'arrivee': 5, 'longueur': 8},
{'depart': 4, 'capacite': 8, 'arrivee': 7, 'longueur': 3},
{'depart': 4, 'capacite': 4, 'arrivee': 7, 'longueur': 3},
{'depart': 5, 'capacite': 8, 'arrivee': 6, 'longueur': 8},
{'depart': 5, 'capacite': 4, 'arrivee': 7, 'longueur': 7},
{'depart': 5, 'capacite': 4, 'arrivee': 6, 'longueur': 5},
{'depart': 6, 'capacite': 5, 'arrivee': 9, 'longueur': 3},
{'depart': 6, 'capacite': 5, 'arrivee': 7, 'longueur': 3},
{'depart': 6, 'capacite': 7, 'arrivee': 8, 'longueur': 3},
{'depart': 7, 'capacite': 2, 'arrivee': 8, 'longueur': 8},
{'depart': 7, 'capacite': 2, 'arrivee': 10, 'longueur': 5},
{'depart': 7, 'capacite': 7, 'arrivee': 10, 'longueur': 4},
{'depart': 8, 'capacite': 3, 'arrivee': 11, 'longueur': 4},
{'depart': 8, 'capacite': 5, 'arrivee': 9, 'longueur': 3},
{'depart': 8, 'capacite': 8, 'arrivee': 10, 'longueur': 3},
{'depart': 9, 'capacite': 1, 'arrivee': 11, 'longueur': 8},
{'depart': 9, 'capacite': 4, 'arrivee': 12, 'longueur': 3},
{'depart': 9, 'capacite': 1, 'arrivee': 11, 'longueur': 7},
{'depart': 10, 'capacite': 5, 'arrivee': 12, 'longueur': 7},
{'depart': 10, 'capacite': 3, 'arrivee': 13, 'longueur': 3},
{'depart': 10, 'capacite': 7, 'arrivee': 11, 'longueur': 4},
{'depart': 11, 'capacite': 4, 'arrivee': 14, 'longueur': 8},
{'depart': 11, 'capacite': 2, 'arrivee': 12, 'longueur': 3},
{'depart': 11, 'capacite': 6, 'arrivee': 14, 'longueur': 6},
{'depart': 12, 'capacite': 5, 'arrivee': 13, 'longueur': 6},
{'depart': 12, 'capacite': 2, 'arrivee': 14, 'longueur': 7},
{'depart': 12, 'capacite': 2, 'arrivee': 14, 'longueur': 6},
{'depart': 13, 'capacite': 2, 'arrivee': 14, 'longueur': 5},
{'depart': 13, 'capacite': 2, 'arrivee': 14, 'longueur': 3},
{'depart': 13, 'capacite': 8, 'arrivee': 14, 'longueur': 6}]
Les routes sont à double sens (il ne faut pas se fier aux appellations "départ" & "arrivée").
On pourra commencer par une instance plus petite, par exemple en ne considérant que les villes jusqu'à 9, avec un borne max pour le temps de 15, c'est à dire avec :
LES_ROUTES = [{'depart': 0, 'capacite': 2, 'arrivee': 1, 'longueur': 5},
{'depart': 0, 'capacite': 3, 'arrivee': 2, 'longueur': 3},
{'depart': 0, 'capacite': 6, 'arrivee': 1, 'longueur': 6},
{'depart': 1, 'capacite': 3, 'arrivee': 2, 'longueur': 6},
{'depart': 1, 'capacite': 7, 'arrivee': 4, 'longueur': 7},
{'depart': 1, 'capacite': 6, 'arrivee': 2, 'longueur': 7},
{'depart': 2, 'capacite': 7, 'arrivee': 4, 'longueur': 4},
{'depart': 2, 'capacite': 6, 'arrivee': 4, 'longueur': 8},
{'depart': 2, 'capacite': 2, 'arrivee': 5, 'longueur': 5},
{'depart': 3, 'capacite': 7, 'arrivee': 5, 'longueur': 5},
{'depart': 3, 'capacite': 3, 'arrivee': 5, 'longueur': 4},
{'depart': 3, 'capacite': 7, 'arrivee': 6, 'longueur': 4},
{'depart': 4, 'capacite': 7, 'arrivee': 5, 'longueur': 8},
{'depart': 4, 'capacite': 8, 'arrivee': 7, 'longueur': 3},
{'depart': 4, 'capacite': 4, 'arrivee': 7, 'longueur': 3},
{'depart': 5, 'capacite': 8, 'arrivee': 6, 'longueur': 8},
{'depart': 5, 'capacite': 4, 'arrivee': 7, 'longueur': 7},
{'depart': 5, 'capacite': 4, 'arrivee': 6, 'longueur': 5},
{'depart': 6, 'capacite': 5, 'arrivee': 9, 'longueur': 3},
{'depart': 6, 'capacite': 5, 'arrivee': 7, 'longueur': 3},
{'depart': 6, 'capacite': 7, 'arrivee': 8, 'longueur': 3},
{'depart': 7, 'capacite': 2, 'arrivee': 8, 'longueur': 8},
{'depart': 7, 'capacite': 2, 'arrivee': 10, 'longueur': 5},
{'depart': 7, 'capacite': 7, 'arrivee': 10, 'longueur': 4},
{'depart': 8, 'capacite': 3, 'arrivee': 11, 'longueur': 4},
{'depart': 8, 'capacite': 5, 'arrivee': 9, 'longueur': 3}]
voire même plus petit.