cs215 ยป

# CS215 Final-6: Distance Oracle II

Here are some test cases that might be useful:

``````import math

def max_labels(labels):
return max(len(labels[u]) for u in labels)

def labels_needed(G):
return 1 + int(math.ceil(math.log(len(G))/math.log(2)))

def test():
# binary tree
edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7),
(4, 8), (4, 9), (5, 10), (5, 11), (6, 12), (6, 13)]
tree = {}
for n1, n2 in edges:
labels = create_labels(tree)
assert labels_needed(tree) >= max_labels(labels)
distances = get_distances(tree, labels)
assert distances[1][2] == 1
assert distances[1][4] == 2
assert distances[4][1] == 2
assert distances[1][4] == 2
assert distances[2][1] == 1
assert distances[1][2] == 1
assert distances[1][1] == 0
assert distances[2][2] == 0
assert distances[9][9] == 0
assert distances[2][3] == 2
assert distances[12][13] == 2
assert distances[13][8] == 6
assert distances[11][12] == 6
assert distances[1][12] == 3
print 'test1 passes'

# chain graph
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7),
(7, 8), (8, 9), (9, 10), (10, 11), (11, 12), (12, 13)]
tree = {}
for n1, n2 in edges:
labels = create_labels(tree)
assert labels_needed(tree) >= max_labels(labels)
distances = get_distances(tree, labels)
assert distances[1][2] == 1
assert distances[1][3] == 2
assert distances[1][13] == 12
assert distances[6][1] == 5
assert distances[6][13] == 7
assert distances[8][3] == 5
assert distances[10][4] == 6
print 'test2 passes'

# "star-chain" graph
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (1, 6), (6, 7),
(7, 8), (8, 9), (1, 10), (10, 11), (11, 12), (12, 13)]
tree = {}
for n1, n2 in edges:
labels = create_labels(tree)
assert labels_needed(tree) >= max_labels(labels)
distances = get_distances(tree, labels)
assert distances[1][1] == 0
assert distances[5][5] == 0
assert distances[1][2] == 1
assert distances[1][3] == 2
assert distances[1][4] == 3
assert distances[1][5] == 4
assert distances[5][6] == 5
assert distances[5][7] == 6
assert distances[5][8] == 7
assert distances[5][9] == 8
print 'test3 passes'
``````

``````from collections import deque

def distance(tree, w, u):
if w==u: return 0

distances = {w: 0}
frontier = deque([w])
while frontier:
n = frontier.popleft()
for s in tree[n]:
if s not in distances:
distances[s] = distances[n] + tree[n][s]
frontier.append(s)
if s==u:
return distances[u]

return None

from math import log, ceil
from random import randint

def random_test():
N = 100
n0 = 20
n1 = 100

for _ in range(N):
tree = {}
for w in range(1, n0):

for w in range(n0+1, n1+1):
make_link(tree, randint(1, w-1), w, randint(1, 1))

labels = create_labels(tree)
distances = get_distances(tree, labels)

assert max([len(labels[n]) for n in tree]) <= int(ceil(log(len(tree)+1, 2)))

for _ in range(N):
w = randint(1, n1)
u = randint(1, n1)
assert distance(tree, w, u) == distances[w][u]

print 'random_test() passed'
``````