Edge Sampling Probability

Problem

Sample a subgraph by keeping each edge independently with probability p.

Call random.seed(seed) first so the sample is reproducible, then scan the edges in input order and keep each when random.random() is below p. Return the kept edges normalized so u < v and sorted. edges is a list of [u, v] pairs.

Hint

Seeding the generator is what makes randomized graph experiments reproducible.

Test cases

case 1

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

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

case 2

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

expected: []

case 3

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

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

Starter codePython

import random
def edge_sampling_probability(edges, seed, p):
    # Your code here
    pass

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