Tainting / Infection

A tainting/infection algorithm for a directed graph. Given the start node(s) and time this algorithm will spread taint/infect any node which has received an edge after this time. The following node will then infect any of its neighbours that receive an edge after the time it was first infected. This repeats until the latest timestamp/iterations are met.

Parameters

  • startTime (Long) : Time to start spreading taint
  • infectedNodes (Set[Long]) : List of nodes that will start as tainted
  • stopNodes (Set[Long]) : If set, any nodes that will not propogate taint
  • output (String) : Path where the output will be written

Returns

  • Infected ID (Long) : ID of the infected vertex
  • Edge ID (Long) : Edge that propogated the infection
  • Time (Long) : Time of infection
  • Infector ID (Long) : Node that spread the infection