Bipartite Projection

Problem

Project a bipartite graph with left_size and right_size nodes onto the left side.

Two left nodes become adjacent when they share at least one right neighbor. edges is a list of [left, right] pairs. Return the sorted adjacency lists of the left nodes.

Hint

Projection connects nodes through their shared neighbors on the other side.

Test cases

case 1

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

expected: [[1],[0,2],[1]]

case 2

in: [2,2,[]]

expected: [[],[]]

case 3

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

expected: [[1,2],[0,2],[0,1]]

Starter codePython

def bipartite_projection(left_size, right_size, edges):
    # Your code here
    pass

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