Een sociale-afstandsgraaf \(G\) is een gewogen graaf. Elke top stelt een persoon voor. Een boog tussen twee toppen \(i\) en \(j\) is gewogen met de sociale afstand \(G_{i,j} \geq 1\) tussen de twee personen voorgesteld door die toppen. Bogen met gewicht oneindig (de personen zullen elkaar niet ontmoeten) worden weggelaten.

In geval van een (hypotetische) uitbraak van een besmettelijke ziekte, kan je in zo’n sociale-afstandsgraaf besmettingspaden zoeken. Een besmettingspad is een sequentie van (niet-herhaalde) toppen in een sociale-afstandsgraaf.

De kans dat een twee personen elkaar rechtstreeks besmetten, is omgekeerd evenredig met de sociale afstand tussen die personen. De rechtstreekse besmettingskans tussen \(i\) en \(j\) in \(G\) is dus \(1/G_{i,j}\). Daaruit volgt volgende formule voor de besmettingskans van een besmettingspad \(P[A = i_0, i_1, ..., B = i_n]\) tussen \(A\) en \(B\):

\[P[A = i_0, i_1, ..., B = i_n] = \prod_{i = 1}^{n}\frac{1}{G_{i-1,i}}\]

Om tenslotte de totale besmettingskans van persoon \(B\) door persoon \(A\) te berekenen, moeten we omgekeerd te werk gaan. Je berekent de kans dat persoon \(B\) niet via geen enkel pad vanuit \(A\) besmet werd:

\[P_{A, B} = 1 - \prod_{p \leftarrow A \cdots B}^{P[p] \geq P_{min}}{\left( 1 - P[p] \right)}\]

Dit product gaat dus over alle besmettingspaden van \(A\) naar \(B\) met een niet-verwaarloosbare besmettingskans (bijvoorbeeld \(P_{min} = 10^{-6}\)).

Implementeer de functie besmettingskans(graph, patient0, doel, minimumkans) die, gegeven een sociale-afstandsgraaf graph, een persoon patient0, een persoon doel en een minimum besmettingskans per pad minimumkans, de totale besmettingskans van doel door patient0 teruggeeft. Omdat het doorlopen van alle paden in de graaf iets te lang zal duren, hou je slim rekening met deze minimumkans.

We maken bij deze oefening gebruik van een eenvoudige grafenbibliotheek graphlib. De API van de deze bibliotheek vind je hier¹. Neem eerst en vooral eens de API en de bibliotheek zelf door en stel eventueel vragen hierover voor je begint te programmeren.

Als je denkt een prioriteitswachtlijn nodig te hebben, dan kun je die hier² vinden. De andere datastructuren die je nodig hebt vind je in de standaardbibliotheek van Python.

Belangrijke opmerking: om met de grafenbibliotheek te kunnen werken in PyCharm moet je het bestand graph_library.py³ toevoegen aan dezelfde directory als waarin je ze gebruikt. Dan kun je ze gebruiken door ze te importeren met

from graph_library import *

Dit import statement mag wel niet mee ingediend worden op dodona.

Voorbeeld:

>>> graph01 = undirected_graph_from_dict({'Bob': ['Alice'], 'Alice': ['Bob']}, weights={('Alice', 'Bob'): 10.0})
>>> alice = graph01.get_node_from_name('Alice')
>>> bob = graph01.get_node_from_name('Bob')
>>> besmettingskans(graph01, alice, bob, 1e-6)
0.1

>>> graph02 = undirected_graph_from_dict({'Bob': ['Alice', 'Carol'], 'Alice': ['Bob', 'Carol'], 'Carol': ['Bob', 'Alice']}, weights={('Carol', 'Alice'): 2.0, ('Alice', 'Bob'): 10.0, ('Bob', 'Carol'): 5.0})
>>> alice = graph02.get_node_from_name('Alice')
>>> bob = graph02.get_node_from_name('Bob')
>>> carol = graph02.get_node_from_name('Carol')
>>> besmettingskans(graph02, alice, bob, 1e-6) # 0.1 + 0.5*0.2
0.2
>>> besmettingskans(graph02, bob, carol, 1e-6) # 0.2 + 0.1*0.5
0.25
>>> besmettingskans(graph02, carol, alice, 1e-6) # 0.5 + 0.1*0.2
0.52

>>> graph03 = undirected_graph_from_dict({'Bob': ['Rupert'], 'Umar': ['Rupert', 'Lizzie'], 'Alice': ['Lizzie'], 'Lizzie': ['David', 'Alice', 'Umar'], 'David': ['Rupert', 'Lizzie'], 'Rupert': ['David', 'Bob', 'Umar']}, weights={('David', 'Rupert'): 7.0, ('Lizzie', 'Umar'): 2.0, ('Rupert', 'Bob'): 11.0, ('Umar', 'Rupert'): 3.0, ('Alice', 'Lizzie'): 1.0, ('Lizzie', 'David'): 5.0})
>>> alice = graph03.get_node_from_name('Alice')
>>> bob = graph03.get_node_from_name('Bob')
>>> besmettingskans(graph03, alice, bob, 1e-6)
0.01774891774891775