Temporal Centrality Lite

Problem

Compute temporal reachability for every node of an evolving undirected graph.

A temporal path from v starts at time 0 and may traverse at most one snapshot per time step in order, using edges from the current snapshot only. For each node count how many nodes are temporally reachable (including itself). snapshots is a list of edge lists.

Hint

Missing a snapshot window can make a temporally central node unreachable.

Test cases

case 1

in: [4,[[[0,1]],[[1,2]],[[2,3]]]]

expected: [4,4,3,2]

case 2

in: [4,[[[0,1],[2,3]],[[1,2]]]]

expected: [3,3,3,3]

case 3

in: [3,[]]

expected: [1,1,1]

Starter codePython

def temporal_centrality(n, snapshots):
    # Your code here
    pass

3 test cases · run your code against them in the editor