Fiedler Rayleigh Quotient

Problem

Evaluate the Rayleigh quotient of a candidate Fiedler vector.

For the Laplacian L of an undirected graph, compute v^T L v / v^T v, which simplifies to the sum over edges of (v[u] - v[v])^2 divided by the squared norm of v. edges is a list of [u, v] pairs and vector is the candidate float vector. Return 0.0 when the vector is all zeros.

Hint

The Laplacian quadratic form measures how much the vector changes across edges.

Test cases

case 1

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

expected: 1

case 2

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

expected: 0

case 3

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

expected: 3

case 4

in: [1,[],[5]]

expected: 0

case 5

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

expected: 0

Starter codePython

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

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