Label Propagation Step

Problem

Perform one synchronous label propagation step. For each node with label -1, take the majority label among its labeled neighbors (ties go to the smallest label); labeled nodes keep their label.

neighbors[i] lists the neighbor indices of node i. Return the updated labels; empty input returns [].

Hint

All unlabeled nodes read the previous label vector, so the update is synchronous.

Test cases

case 1

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

expected: [0,0,-1,-1]

case 2

in: [[[1,2],[0,2],[0,1]],[-1,-1,1]]

expected: [1,1,1]

case 3

in: [[[1,2],[0],[0]],[-1,0,1]]

expected: [0,0,1]

case 4

in: [[],[]]

expected: []

Starter codePython

def label_propagation_step(neighbors, labels):
    # Your code here
    pass

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