Maximum distance

centrality_max.py

# Udacity, CS215, Homework 3.7 Centrality
# Write centrality_max to return the maximum distance
# from a node to all the other nodes it can reach
#

def centrality_max_BFS(G, v):
    # your code here
    distance = {}
    open_list = [v]
    distance[v] = 0
    while open_list:
        node = open_list[0]
        del open_list[0]
        for neighbor in G[node].keys():
            if neighbor not in distance: #same with the marked checking in 'make_component'
                distance[neighbor] = distance[node] + 1
                open_list.append(neighbor)
    return max(distance.values())


def centrality_max_DFS(G, v):
    # DFE works as well, which one is more efficient?
    distance = {}
    open_list = [v]
    distance[v] = 0
    while open_list:
        node = open_list.pop()
        #del open_list[0]
        for neighbor in G[node].keys():
            if neighbor not in distance:
                distance[neighbor] = distance[node] + 1
                open_list.append(neighbor)
    return max(distance.values())

#################
# Testing code
#
def make_link(G, node1, node2):
    if node1 not in G:
        G[node1] = {}
    (G[node1])[node2] = 1
    if node2 not in G:
        G[node2] = {}
    (G[node2])[node1] = 1
    return G

def test():
    chain = ((1,2), (2,3), (3,4), (4,5), (5,6))
    G = {}
    for n1, n2 in chain:
        make_link(G, n1, n2)
    print G
    assert centrality_max(G, 1) == 5
    assert centrality_max(G, 3) == 3
    tree = ((1, 2), (1, 3),
            (2, 4), (2, 5),
            (3, 6), (3, 7),
            (4, 8), (4, 9),
            (6, 10), (6, 11))
    G = {}
    for n1, n2 in tree:
        make_link(G, n1, n2)
    print G
    assert centrality_max(G, 1) == 3
    assert centrality_max(G, 11) == 6

test()

Print_results.py

Chain graph:
{1: {2: 1}, 2: {1: 1, 3: 1}, 3: {2: 1, 4: 1}, 4: {3: 1, 5: 1}, 5: {4: 1, 6: 1}, 6: {5: 1}}

Tree graph:
{1: {2: 1, 3: 1}, 2: {1: 1, 4: 1, 5: 1}, 3: {1: 1, 6: 1, 7: 1}, 4: {8: 1, 9: 1, 2: 1}, 5: {2: 1}, 6: {11: 1, 10: 1, 3: 1}, 7: {3: 1}, 8: {4: 1}, 9: {4: 1}, 10: {6: 1}, 11: {6: 1}}

Distance:
{1: 0, 2: 1, 3: 2, 4: 3, 5: 4, 6: 5}

{1: 2, 2: 1, 3: 0, 4: 1, 5: 2, 6: 3}

{1: 0, 2: 1, 3: 1, 4: 2, 5: 2, 6: 2, 7: 2, 8: 3, 9: 3, 10: 3, 11: 3}

{1: 3, 2: 4, 3: 2, 4: 5, 5: 5, 6: 1, 7: 3, 8: 6, 9: 6, 10: 2, 11: 0}