Conductance of a Cut

Problem

Compute the conductance of a two-way partition of an undirected graph.

Let A be the community containing node 0 and B all other nodes. The conductance is cut / min(vol(A), vol(B)), where vol is the sum of degrees in a side; return 0.0 when either volume is zero. edges is a list of [u, v] pairs and community maps nodes to labels.

Hint

Normalizing by the smaller volume exposes bottlenecks even in unbalanced cuts.

Test cases

case 1

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

expected: 0.3333333333333333

case 2

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

expected: 0.6666666666666666

case 3

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

expected: 0

case 4

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

expected: 1

case 5

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

expected: 0.14285714285714285

Starter codePython

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

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