WL Hash Colors One Round

Problem

Perform one round of Weisfeiler-Lehman color refinement on an undirected graph.

Each node's new color is the string formed by its old color, a vertical bar, and the sorted comma-separated colors of its neighbors. labels is the initial color list. Return the upgraded color list; isolated nodes keep only their old color after the bar.

Hint

Sorted neighbor multisets make the refinement independent of node ordering.

Test cases

case 1

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

expected: ["0|1","1|0,0","0|1"]

case 2

in: [4,[[0,1],[0,2],[0,3]],["c","l","l","l"]]

expected: ["c|l,l,l","l|c","l|c","l|c"]

case 3

in: [2,[],["x","y"]]

expected: ["x|","y|"]

Starter codePython

def wl_hash_colors_one_round(n, edges, labels):
    # Your code here
    pass

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