Laplacian Matrix Build

Problem

Build the Laplacian matrix L = D - A of an undirected simple graph with n nodes.

The diagonal holds the degree of each node and off-diagonal entry [i][j] is -1 when i and j are adjacent, else 0. edges is a list of [u, v] pairs. Return the n by n integer matrix.

Hint

Each edge adds 1 to both endpoint degrees and -1 to the two corresponding off-diagonal cells.

Test cases

case 1

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

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

case 2

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

expected: [[2,-1,-1],[-1,2,-1],[-1,-1,2]]

case 3

in: [2,[]]

expected: [[0,0],[0,0]]

case 4

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

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

Starter codePython

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

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