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,

  1. A contacts B
  2. 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?

4

Comments

You must log in or register to comment.

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.

3

hollyhoppet wrote

Replying to hollyhoppet (#3,910)

If you really wanted, you could also record a history of each graph at each step. You could get even more granular and have a history of each graph traversal step as well.

I don't really know if there's a way to model the whole thing as a single graph because you're basically describing with each "x contacts y" a different set of relationships, and thus a different graph.

3

musou wrote

i feel like this might be a really good use case for prolog

3