Data structure used in covid-19 app
Data Structure for Contact Graph in covid-19 app:
We represent G using adjacency lists having two components, index file (G.) and close contact vectors file
(G.). The G stores q number of index records with two fields UserID and Pointer for each user. Here, q, the average degree of the G represents the average number of distinct persons coming in close contact with a person during D days. Moreover, we maintain one extra index record in G to move into the overflow area when contacts exceed the average value of q for an individual.
Algorithm for Process(G, ) while (Buffer() 6= φ) do if (.StartT ime 6= φ) then t, P ← .StartTime,.UID ν, λ, ρ,W ← Initialize(t) end if X ← GetNext( .Data) if (X = Gx) then ν, λ,W ← Update(ν, λ, x) else U ← GetUsers(X.Rec, t) U.̺ ← 1 W ← UpdateCounters(W,U) if (Size(W) = ρ) then W ← Delete(W,U′) for all (P′in U′) do if (P′.̺ = ρ) then G ← Install(G, P, P′, ν, λ) end if end for end if if λ = ρ then ν ← (ν + 1) mod n end if λ ← (λ + 1) mod ρ W ← Insert(W, U) end if end while return G
Algorithm for Contact Tracing:
Algorithm for TraceContacts(G, I′, L) Create χ, Q1, Q2, l for all P ∈ I′ do A ← P(q + 1) while G.[A].P ointer 6= NULL do P′← G. [A].UID if P′/∈ then P′.Level ← l ← ∪ P′ χ ← χ ∪ Edge(P, P′) Q1 ← Insert(Q1,A) end if A ← A + 1 end while end for l ← l + 1 while ((l ≤ L) and not (IsEmpty(Q1) and IsEmpty(Q2))) do while (not IsEmpty(Q1)) do Q1 ← Delete(Q1,A) P ← G. [A].UID A′← P(q + 1) while G. [A′].Pointer 6= NULL do P′← G. [A′].UID c1 ← G.[A] c2 ← G.[A′] if P′/∈ and T raceOperator(c1, c2) then P′.Level ← l← ∪ P′ χ ← χ ∪ Edge(P, P′) Q2 ← Insert(Q2, A′) A′← A′+ 1 end if end while end while Q1, Q2 ←→ Q2, Q1 end while return, χ