La rumeur qui court...⚓︎
On modélise la circulation de rumeurs dans un groupe de personnes à l'aide d'un graphe orienté comme ci-dessous.
flowchart LR
C(Camille) --> R(Romane)
C <--> M(Marion)
M --> R
C --> P(Paul)
R --> N(Nicolas)
R --> A(Antoine)
R <--> P
P --> A
A <--> N
N --> C
S(Stéphane) --> AL'arête "Romane → Antoine" signifie que Romane informe Antoine des rumeurs. Par contre Antoine n'informe mais pas Romane (observer l'orientation de la flèche).
L'arête "Antoine ↔ Nicolas" signifie quant à elle que Antoine et Nicolas s'informent l'un l'autre des rumeurs.
Lorsqu'une personne apprend une rumeur elle s'empresse de la raconter à toutes ses relations.
Ce graphe est représenté en machine par un dictionnaire dans lequel :
-
les clés sont les chaînes de caractères correspondant aux noms des personnes du groupe,
-
les valeurs associées sont des listes de chaînes de caractères représentant les noms des personnes à qui elles transmettent la rumeur.
Le graphe dessiné plus haut est ainsi représenté par le dictionnaire suivant :
graphe = {'Camille': ['Romane', 'Marion', 'Paul'],
'Romane': ['Nicolas', 'Antoine', 'Paul'],
'Marion': ['Camille', 'Romane'],
'Paul': ['Antoine', 'Romane'],
'Antoine': ['Nicolas'],
'Nicolas': ['Camille', 'Antoine'],
'Stéphane': ['Antoine']}
Lors de sa circulation une rumeur est déformée... Connaissant la structure du graphe et l'origine de la rumeur (la première personne informée), on cherche à savoir combien de fois celle-ci a été racontée avant d'atteindre une personne donnée.
Par exemple, si la rumeur part de Romane, elle sera racontée 1 seule fois avant qu'Antoine ne l'apprenne, 3 fois avant que Marion ne l'apprenne.
Écrire la fonction distance :
-
prenant en argument le graphe sous forme d'un dictionnaire (
graphe), le nom de la personne à l'origine de la rumeur (origine) ainsi que le nom d'une personne (destination), -
renvoyant le nombre de fois minimal où la rumeur a été racontée entre l'origine et la destination.
Si la rumeur n'atteint pas la destination, la fonction renverra None.
Aide (1)
On pourra utiliser un parcours particulier du graphe. À ce titre, la classe File ci-dessous est donnée :
class File:
"""Classe implémentant une file"""
def __init__(self, valeurs=None):
if valeurs is None:
self.valeurs = []
else:
self.valeurs = valeurs
def est_vide(self):
return len(self.valeurs) == 0
def enfiler(self, valeur):
self.valeurs.append(valeur)
def defiler(self):
return self.valeurs.pop(0)
Aide (2)
On pourra garder trace des personnes à qui transmettre la rumeur et du nombre de fois où celle-ci à été racontée en enfilant des tuples. Par exemple : file.enfiler(('Romane', 0)).
Exemples
On utilise le graphe ci-dessous :
>>> graphe = {"Camille": ["Romane", "Marion", "Paul"],
... "Romane": ["Nicolas", "Antoine", "Paul"],
... "Marion": ["Camille", "Romane"],
... "Paul": ["Antoine", "Romane"],
... "Antoine": ["Nicolas"],
... "Nicolas": ["Camille", "Antoine"],
... "Stéphane": ["Antoine"]}
On a alors :
>>> distance(graphe, 'Romane', 'Romane')
0
>>> distance(graphe, 'Romane', 'Antoine')
1
>>> distance(graphe, 'Romane', 'Marion')
3
>>> distance(graphe, 'Romane', 'Stéphane') is None
True
#--- HDR ---#bksl-nlclass File:bksl-nl """Classe implémentant une file"""bksl-nl def py-undpy-undinitpy-undpy-und(self, valeurs=None):bksl-nl if valeurs is None:bksl-nl self.valeurs = []bksl-nl else:bksl-nl self.valeurs = valeursbksl-nlbksl-nl def estpy-undvide(self):bksl-nl return len(self.valeurs) == 0bksl-nlbksl-nl def enfiler(self, valeur):bksl-nl self.valeurs.append(valeur)bksl-nlbksl-nl def defiler(self):bksl-nl return self.valeurs.pop(0)bksl-nl#--- HDR ---#bksl-nlbksl-nlbksl-nldef distance(graphe, origine, arrivee):bksl-nl file = File()bksl-nl aupy-undcourant = []bksl-nl file.enfiler((origine, 0))bksl-nl while not file....:bksl-nl actuel, nbpy-undetapes = file....bksl-nl aupy-undcourant.append(...)bksl-nl if actuel == arrivee:bksl-nl return ...bksl-nl for voisin in graphe[...]:bksl-nl if voisin not in ...:bksl-nl file.enfiler((..., ...))bksl-nlbksl-nl # La destination n'est pas atteinte...bksl-nl return ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlgraphe = {'Camille': ['Romane', 'Marion', 'Paul'],bksl-nl 'Romane': ['Nicolas', 'Antoine', 'Paul'],bksl-nl 'Marion': ['Camille', 'Romane'],bksl-nl 'Paul': ['Antoine', 'Romane'],bksl-nl 'Antoine': ['Nicolas'],bksl-nl 'Nicolas': ['Camille', 'Antoine'],bksl-nl 'Stéphane': ['Antoine']}bksl-nlbksl-nlassert distance(graphe, 'Romane', 'Romane') == 0bksl-nlassert distance(graphe, 'Romane', 'Antoine') == 1bksl-nlassert distance(graphe, 'Romane', 'Marion') == 3bksl-nlassert distance(graphe, 'Romane', 'Stéphane') is Nonebksl-nlbksl-nldef distance(graphe, origine, arrivee):bksl-nl file = File()bksl-nl aupy-undcourant = []bksl-nl file.enfiler((origine, 0))bksl-nl while not file.estpy-undvide():bksl-nl actuel, nbpy-undetapes = file.defiler()bksl-nl aupy-undcourant.append(actuel)bksl-nl if actuel == arrivee:bksl-nl return nbpy-undetapesbksl-nl for voisin in graphe[actuel]:bksl-nl if voisin not in aupy-undcourant:bksl-nl file.enfiler((voisin, nbpy-undetapes + 1))bksl-nl return Nonebksl-nlbksl-nlbksl-nlclass File:bksl-nl def py-undpy-undinitpy-undpy-und(self, valeurs=None):bksl-nl if valeurs is None:bksl-nl self.valeurs = []bksl-nl else:bksl-nl self.valeurs = valeursbksl-nlbksl-nl def estpy-undvide(self):bksl-nl return len(self.valeurs) == 0bksl-nlbksl-nl def enfiler(self, valeur):bksl-nl self.valeurs.append(valeur)bksl-nlbksl-nl def defiler(self):bksl-nl return self.valeurs.pop(0)bksl-nlbksl-nlbksl-nl# Testsbksl-nlgraphe = {'Camille': ['Romane', 'Marion', 'Paul'],bksl-nl 'Romane': ['Nicolas', 'Antoine', 'Paul'],bksl-nl 'Marion': ['Camille', 'Romane'],bksl-nl 'Paul': ['Antoine', 'Romane'],bksl-nl 'Antoine': ['Nicolas'],bksl-nl 'Nicolas': ['Camille', 'Antoine'],bksl-nl 'Stéphane': ['Antoine']}bksl-nlbksl-nlassert distance(graphe, 'Romane', 'Romane') == 0bksl-nlassert distance(graphe, 'Romane', 'Antoine') == 1bksl-nlassert distance(graphe, 'Romane', 'Marion') == 3bksl-nlassert distance(graphe, 'Romane', 'Stéphane') is Nonebksl-nlbksl-nl
A
On utilise un parcours en largeur d'abord. Le stockage des sommets à visiter est effectué à l'aide d'une file (modèle premier entré, premier sorti).
Chaque sommet à traiter est empilé avec sa "distance" à l'origine sous la forme d'un tuple. Ainsi, pour l'origine on enfile (origine, 0).
Le parcours continue tant que la file est non-vide et que l'on a pas visité la destination :
- on défile le sommet à traiter et sa distance à l'origine (le nombre d'étapes),
- on ajoute le nom du sommet à la liste des personnes au courant,
- on teste si ce nom est la destination (auquel cas on renvoie la distance),
- si ce n'est pas le cas, on ajoute ses voisins pas encore visités à la file en incrémentant la distance
Si le parcours se termine sans sortie prématurée, cela signifie que la destination n'est toujours pas au courant de la rumeur. L'énoncé demande de renvoyer None.
Z