Degré de séparation
On considère le schéma suivant où une flèche allant d'une personne Α vers une personne B indique que la personne A « suit » la personne B sur son compte Immediam. On dit alors que B est un ami de A.
Voici un exemple de réseau Immediam
flowchart LR
A([Anna]) --> B([Billy])
B --> A
B --> E([Eroll])
C([Carl]) --> B
D([Dora]) --> G([Gaby])
E --> B
E --> D
E --> G
E --> F([Flynn])
F --> G
G --> ELes amis des amis d'Eroll sont donc Gaby (amie à la fois de Dora et Flynn) et Anna (amie de Billy).
Degré de séparation
Dans un réseau social, le degré de séparation est le nombre de relations entre deux individus du réseau.
Ainsi, il y a \(1\) degré de séparation entre Billy et Eroll, et \(3\) degrés entre Carl et Flynn.
On représente ce réseau Immediam en machine par un dictionnaire dans lequel :
-
les clés sont les chaînes de caractères correspondant aux noms des personnes inscrites,
-
les valeurs associées sont des listes de chaînes de caractères représentant les personnes suivies.
Écrire une fonction degres_separation qui :
-
prend en argument un dictionnaire
reseaureprésentant un tel réseau Immediam et une chaîne de caractèresmembrequi désigne un membre du réseau ; -
renvoie un dictionnaire qui associe à chaque membre du réseau un entier indiquant le degré de séparation entre les deux membres.
Aide (1)
On pourra utiliser un parcours particulier du graphe. À ce titre, on fournit une 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 variablef; -
f.est_vide(): renvoie le booléen indiquant si la filefest vide ; f.enfile(x): enfile l'élémentxdans la filef;f.defile(): défile un élément de la filefsi elle n'est pas vide et le renvoie. Provoque une erreur si la file est vide.
La classe File
from collections import deque
class File:
"""Classe définissant une structure de file"""
def __init__(self):
self.valeurs = deque([])
def est_vide(self):
"""Renvoie le booléen True si la file est vide, False sinon"""
return len(self.valeurs) == 0
def enfile(self, x):
"""Place x à la queue de la file"""
self.valeurs.appendleft(x)
def defile(self):
"""Retire et renvoie l'élément placé à la tête de la file.
Provoque une erreur si la file est vide
"""
if self.est_vide():
raise ValueError("La file est vide")
return self.valeurs.pop()
def __repr__(self):
"""Convertit la file en une chaîne de caractères"""
if self.est_vide():
return "∅"
return f"(queue) {' -> '.join(str(x) for x in self.valeurs)} (tête)"
Aide (2)
On pourra stocker des couples (membre, degre_de_separation).
Exemples
>>> immediam = {
"Anna": ["Billy"],
"Billy": ["Anna", "Eroll"],
"Carl": ["Billy"],
"Dora": ["Gaby"],
"Eroll": ["Billy", "Dora", "Flynn", "Gaby"],
"Flynn": ["Gaby"],
"Gaby": ["Eroll"],
}
>>> degres_separation(immediam, 'Billy')
{'Billy': 0, 'Anna': 1, 'Eroll': 1, 'Dora': 2, 'Flynn': 2, 'Gaby': 2}
>>> degres_separation(immediam, 'Flynn')
{'Eroll': 0, 'Billy': 1, 'Dora': 1, 'Flynn': 1, 'Gaby': 1, 'Anna': 2}
>>> degres_separation(immediam, 'Eroll')
{'Flynn': 0, 'Gaby': 1, 'Eroll': 2, 'Billy': 3, 'Dora': 3, 'Anna': 4}
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)