Network Reliability by Enumeration

Problem

Compute the probability that every node of a small graph stays connected when each edge survives independently with probability p.

Enumerate all 2^m edge subsets, keep the ones whose union-find structure joins all n nodes into one component, and sum p^k * (1 - p)^(m - k) for k surviving edges. edges is a list of [u, v] pairs. Return the reliability as a float; for n at most 1 return 1.0.

Hint

Only subsets spanning all nodes contribute, weighted by the number of surviving edges.

Test cases

case 1

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

expected: 0.5

case 2

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

expected: 0.25

case 3

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

expected: 0.5

case 4

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

expected: 0.3125

case 5

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

expected: 1

Starter codePython

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

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