Modelarea unui graf ca structura de date cu persoanele infectate – Contact-Tracing COVID-19 [Part-1]

Daca s-ar modela printr-o structura de date de tip graf ceea ce ar fi extrem de important e sa se stabilească data, ora ca un graf orientat sa prinda contur. Altfel ar exista unul neorientat doar cuprinzand persoanele ce au facut schimb de chei, alcatuind un graf initial complet.

Consideram P1 ca posibil infectat ce isi urca cheile sale dupa aflarea verdictului undeva Marti la 11:50pm.

Unde am avea urmatoarele muchii(legaturi-intalniri), P1->P2, P1->P3, P2->P3, P3->P4. Am putea stabili data si ora la care persoanele au intrat in contact astfel incat sa stabilim un timeline. Observam ca P1 schimba chei cu P2 luni la ora 7:55am, dar schimba si chei cu P3 la ora 9:30am. Insa fiind o structura de graf neorientat, nu se poate stabili cu precizie daca cumva P3 nu are o muchie bidirectionala cu P1 sau P2, adica dubla legatura in care sa se poata vedea daca s-au intalnit de multiple ori. Insa ceea ce se poate observa mai clar intr-o astfel de structura este ca ne apropiem de o solutie care cuprinde si un posibil ciclu de infectie. Infectia nu ar merge pe nivele de la o persoana spre alta cu un anumit numar precis de chei ci ar putea intra intr-o bucla unde 2 persoane pot schimba chei multiple in intalniri la timpi diferiti. Si oricare din cele 2 pot construi alte muchii in cadrul altor intalniri la o data diferita.

Ceea ce am vrut sa zic in ultima fraza ca se pot construi alte muchii tot in cadrul aceluiasi grup, care de exemplu uneori sa nu fie cu chei infectate dar cealalta muchie sa fie cea infectata. Adica timpi diferiti.

Spre exemplu se va prezenta urmatoarea modelare a unei infectii:

Unde se poate observa ca infectia porneste din P1. Daca se urmareste parcursul infectiei in functie de cadrul temporal vom avea ordinea P1->P5 , P1->P4 , P1->P2 restransa doar pentru P1 pentru a evidentia mai bine doar muchiile din P1. Prima muchie P1->P5 se stabileste marti la ora 09:20am, dar vedem ca P5 are o muchie cu P6 in aceeasi zi, dar la o ora diferita 07:20am care e inainte de a fi stabilita muchia P1-P5 deci reiese ca persoana P6 nu este infectata cu toate ca a avut o intalnire cu P5 chiar in aceeasi zi.

Trecand mai departe la muchii P1-P4 vedem ca infectarea se produce luni la ora 12:20pm, dar se constanta si faptul ca P4 are muchie cu P3 si viceversa P3->P4. Ora la care P4 se intalneste cu P3 este luni la 11:20 cand P4 nu era infectat, reiesind ca P3 nu e infectat pana cand apare muchia P2->P3 luni la ora 17:20pm. Iar a doua muchie P3->P4 produce dubla infectie a persoanei P4.

Muchia P1->P2 se produce luni la ora 15:20pm, iar infectia dintre P2->P3 luni la ora 17:20pm.

Prin acest exemplu se poate observa cum prin stabilirea orelor in care s-au schimbat chei intre doua persoane se poate alcatui cu precizie lantul infectarii. Foarte important este in acest exemplu intelegerea non infectarii a lui P6 si dubla infectie la ore diferite a lui P4, cat si non infectia temporala al lui P3 chiar daca exista un lant P1->P4->P3

Ordinea infectarilor pe muchii:

Un alt exemplu cu un subgraf “curat”:

Unde exista un ciclul P4->P5->P6 care e curat cu toate ca P3 e declarat ca infectat

P1 porneste infectia cu P2 luni la ora 12:20am si are o muchie cu P3 marti la ora 09:20am. Dar P3 deja are muchie cu P4 la ora 07:20am cu care a schimbat cateva chei. P4 are muchie cu P6 la ora 14:20pm si cu P5 la ora 17:20pm. P5 si P6 au muchie comuna la ora 20:20pm, cand P1 are cheile declarate ca infectate si se incepe procesul de fetching.

Iar acesta este un alt exemplu unde orele si zilele la care s-au schimbat cheile conteaza enorm de mult in analiza/modelarea tuturor intalnirilor si in stabilirea muchiilor. La fel precum modelarea pe un graf directional este un mod mult mai detaliat prin care se pot observa intalnirile pentru a se stabili ordinea lor.

In acelasi idee precum a fost explicat in modelarea pe un arbore, daca o persoana care a fost anuntata ca a schimbat chei infectate cu cineva nu isi urca automat cheile in timp util celelalte persoane ar putea sa continue sa faca muchii cu alte persoane.

Google+