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 interface PadZoeker¹ in een klasse genaamd BesmettingsPadZoeker. Schrijf hiervoor een methode double besmettingskans(UndirectedGraph graph, Node patient0, Node doel, double 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.

Met behulp van de klasse SimpleTest² kan je jouw oplossing lokaal testen. De graafklassen kan je terugvinden in onze grafenbibliotheek³ (javadoc⁴).