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) --> A
L'arête "Romane → Antoine" signifie que Romane est en relation avec Antoine et l'informe des rumeurs. Cette relation n'est pas symétrique : Antoine n'informe pas Romane des rumeurs (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. La relation va donc dans les deux directions.
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 avec qui elles sont en relation (et donc les personnes à qui elles transmettent les rumeurs).
Le graphe dessiné plus haut est ainsi représenté par le dictionnaire suivant :
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 :
qui prend en paramètres 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),
renvoie 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 garder trace des personnes au courant de la rumeur à l'aide d'un dictionnaire {personne: booléen}.
Aide (2)
On pourra utiliser un parcours particulier du graphe. À ce titre, on fournit une la classe File dont on donne l'interface ci-dessous.
Interface de la classe File
f = File() : crée une file vide et l'affecte à la variable f;
f.est_vide() : renvoie le booléen indiquant si la file f est vide ;
f.enfile(x) : enfile l'élément x dans la file f;
f.defile() : défile un élément de la file f si elle n'est pas vide et le renvoie. Provoque une erreur si la file est vide.
La classe File
fromcollectionsimportdequeclassFile:"""Classe définissant une structure de file"""def__init__(self):self.valeurs=deque([])defest_vide(self):"""Renvoie le booléen True si la file est vide, False sinon"""returnlen(self.valeurs)==0defenfile(self,x):"""Place x à la queue de la file"""self.valeurs.appendleft(x)defdefile(self):"""Retire et renvoie l'élément placé à la tête de la file. Provoque une erreur si la file est vide """ifself.est_vide():raiseValueError("La file est vide")returnself.valeurs.pop()def__repr__(self):"""Convertit la file en une chaîne de caractères"""ifself.est_vide():return"∅"returnf"(queue) {' -> '.join(str(x)forxinself.valeurs)} (tête)"
Aide (3)
On pourra gérer les personnes à qui transmettre la rumeur et du nombre de fois où celle-ci à été racontée en enfilant des tuples. Par exemple : file.enfile(('Romane',0)).
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)