cs215 ยป

CS215 Final-6: Distance Oracle II

Here are some test cases that might be useful:

Courtesy of ked4r: http://forums.udacity.com/cs215/questions/5080/grader-for-distance-oracle-ii-updated/5095

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:
        make_link(tree, n1, n2)
    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:
        make_link(tree, n1, n2)
    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:
        make_link(tree, n1, n2)
    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'

Courtesy of D Kulakovsky http://forums.udacity.com/cs215/questions/5080/grader-for-distance-oracle-ii-updated/5101

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):
            make_link(tree, w, w+1, randint(1, 1))

        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'