This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def mst(graph): | |
''' | |
mst retuns the minimum spanning tree of `graph`, which must be a symmetric NxN array, where | |
element (i,j) is the weight of the connection from node i to node j. The diagonal should be all | |
zeros (because i and j are the same point), and unconnected nodes are `None`. | |
The nth position of the array returned contains the parent node of node n. The order always | |
starts from node 0 as the root of the tree, so order[0] is always None. | |
''' | |
order = [None] * len(graph) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def sample(weights, size=1): | |
beta = 0 | |
samples = [] | |
w_max = max(weights) | |
index = random.randint(1, N) | |
while len(samples) < size: | |
beta += random.uniform(0, 2 * w_max) | |
while w[index] < beta: | |
beta -= weights[index] | |
index += 1 |