Is there a directed graph data structure for calculating risk of exposure? (Like a directed graph, but with time.)
Submitted by twovests in programming
E.g. consider three entities, A, B, C and D. In this order,
- A contacts B
- B contacts C and D
If A were infected in the beginning, then A, B, C, and D are all potentially infected.
If D were infected, then only B and D are potentially infected.
I imagine it'd be like some weird kinda graph. Does this exist?
hollyhoppet wrote (edited )
I'd say the best way to model this would be to decouple the entities from the graph from the contact and infection steps. Each step could be an object that holds information on node contact and/or infection.
Iterate through each of the steps (represented in an array perhaps), constructing a new graph with each of the entities as nodes. Each "x contacts y" would represent a vertex in this graph.
Have a bit on each entity object representing whether it's infected that persists across iterations. For each step iteration mentioned above, after constructing the graph for that step, do a graph traversal starting from each node that has been infected at the start of this iteration, infecting each traversed node along the way*. At the end, you'll have a set of nodes that all have infected bits set if they were to have been infected.
*You can optimize this a bit by treating any vertex that points to an already-infected node as not needing to be traversed.