Effective Resistance via Pseudoinverse

Problem

Compute the effective resistance between vertices i and j of an undirected graph given by adjacency matrix A.

Build the Laplacian L = D - A, compute its pseudoinverse with the formula L+ = inv(L + J/n) - J/n where J is the all-ones matrix, and return L+[i][i] + L+[j][j] - 2*L+[i][j]. Assume the graph is connected.

Hint

Effective resistance equals the voltage difference when a unit current is injected at i and extracted at j.

Test cases

case 1

in: [[[0,1],[1,0]],0,1]

expected: 1

case 2

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

expected: 2

case 3

in: [[[0,1,0],[1,0,1],[0,1,0]],0,1]

expected: 1

case 4

in: [[[0,1,1],[1,0,1],[1,1,0]],0,1]

expected: 0.6666666666666666

Starter codePython

def effective_resistance(A, i, j):
    # Your code here
    pass

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