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
Les amis d'Eroll sont Dora, Gaby, Flynn et Billy.Les 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
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
reseau
représentant un tel réseau Immediam et une chaînes de caractèresmembre
qui 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 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 variablef
; -
f.est_vide()
: renvoie le booléen indiquant si la filef
est vide ; f.enfile(x)
: enfile l'élémentx
dans la filef
;f.defile()
: défile un élément de la filef
si 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)