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 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 reseau représentant un tel réseau Immediam et une chaînes de caractères membre 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 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
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}
def degres_separation(reseau, membre1):
...
# Tests
immediam = {
"Anna": ["Billy"],
"Billy": ["Anna", "Eroll"],
"Carl": ["Billy"],
"Dora": ["Gaby"],
"Eroll": ["Billy", "Dora", "Flynn", "Gaby"],
"Flynn": ["Gaby"],
"Gaby": ["Eroll"],
}
assert degres_separation(immediam, "Billy") == {'Billy': 0, 'Anna': 1, 'Eroll': 1, 'Dora': 2, 'Flynn': 2, 'Gaby': 2}
assert degres_separation(immediam, "Eroll") == {'Eroll': 0, 'Billy': 1, 'Dora': 1, 'Flynn': 1, 'Gaby': 1, 'Anna': 2}
assert degres_separation(immediam, "Flynn") == {'Flynn': 0, 'Gaby': 1, 'Eroll': 2, 'Billy': 3, 'Dora': 3, 'Anna': 4}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
rounded
>>> 
 
x
x
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5
.128013_c.ms7a1}e[0kPSgpf5/(uF)8rbl]o4w=+ vhd,9t2{63y:in050M0k0P0h0W0C0f0J0c0C0h0f0f0H010P0W0r010406050f0w0e0e0h0A0U040p0E0C0w0=0E0X050u0|0~10120`0r04051i1b1l0u1i0`0M0W0K0*0,0.0:0L0W0q0L0C1z0L0P0^050#0B0C0k1u0-0/011y1A1C1A0P1I1K1G0P0A1j0P0L0*150f0r0h0X0:0Q011M1w010s0%0k0X0h0e0k1G1)1+1:1O1?1K1_1{0^0a0J0o0A0E0r0E0f0W180X0J0Z1%0A0A0k0c2g1b1~0X1j0u1#2t1Y1!1Z1H0M200:1C0X1^2d1G1r1t0+1N2D0W2F0X0E2J1G0r2m1j2r2t2X0{1*2h2L1;2Q0A0 0C0^0J0i2q2#0_2!1 2%1O2)2+2-0Q2:1+2=2r2C012`0h2,040J0T2~2s0`312^0:34360J0F3a302#323g2-0t3k3c3m3e330E2*352-0S3r2?2$1v2_3w2{370g3B3d3E3f3G3y370z3K3t3M3v3x3h0O3S2@3U3o040i0m3Z3D2M3V3H0i2/1c2;1m2V1b2J2w0M1!2B3u0c2R1|1j3_1k3@2Z3;2 053 0Z2W3T3,0n0^0Z0s3k3C320G2-4j3L3,0X0s4g0k0q2m0f0b0f0k1*0A0h2p472s4k3u0@040v4o4d2(0^4w0k0h0w4M3!3,4J0N3k0J4H3#0^1{0e0B2m3:2Z4p1;4J0y0V3r0J4@4!4.2_0^220k4Z4#3,0E0^0H4 4`3f0^0x1@4U3+4/0^0v0y4?4^504O044}5b3252040d5n3u0X0^1^5m4F4c4V5d4K4L5y5j4{044(4*0k4,3=56014X5s3U0e0W0^3)5E5N4:5g5y064^4_4N5G0Z4v0k0f555(0:5p545y5%5A1O4J0R5Q4q4%0k4)4+5.5^0:4J4=5?5F0:5S5U5|5B0j5h4@68014f040G1y1K625c1O0E4m042Q0P6o3n4|5a5W5/015p5r6A63335v0f0P0b0K0W0Z6c5_5e4;6f5$5@6p575H5 5J6P640^4Y675N5u045*2m6w3u5;6/4$5l6z4-6B6D6#6H6,0k5x6_6G4J5f6T5$6h6j0s3w6=5}041`0W7b1;6r0^2O7g5G4Q4S6|4J0l6|6+5I6.6F6W5O0^0D662X5#6U7E777j4i6)6B6+7e7l5:6s6u7N6C6s7k7J6G6+6-5,7p0^7B2;7D7E7)6V6x6~5+5-7w327q7s0^7M7:4I7z7R6;7V7x7X4u7v717x5p0I6|6a3%757*5i6*6y6n7_3U6{8g7c5w6^5M6B735D837,7^8r7`046(2X7+5t4t5+6|85875T898j5B0y5Z7C765N6j2m0P0w0A1a7~7,7Y7/7C1b4a0k2t2U8$3^1s3`2w2z2u0h1J8)0u3_0`8?0!0$0(04.