Forest Fire Sampling Seeded

Problem

Sample a subgraph with the forest fire model starting from one seed.

Process a queue: for each visited node, burn each unvisited sorted neighbor independently with probability burn_prob using the seeded generator, adding burned nodes to the frontier. Return the sorted visited nodes. edges is a list of [u, v] pairs.

Hint

Forest fire sampling explores more broadly as the burning probability rises.

Test cases

case 1

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

expected: [0]

case 2

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

expected: [0,2,3]

case 3

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

expected: [0,1]

case 4

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

expected: [0]

Starter codePython

import random
def forest_fire_sampling(n, edges, start, burn_prob, seed):
    # Your code here
    pass

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