[Algorithmic Thinking] Project 1

머리가 굳는 느낌이라 COURSERA를 통해서 RICE university의 Algorithmic Thinking 이라는 강의를 수강하고 있음..

알고리즘 공부하면서 고생했던 것도 생각나고, 몇 년만에 python으로 짜다 보니 옛날 생각도 나고 하네.

오늘 module 1 숙제로 제출한 소스 기념으로 저장. ㅋㅋ

# Project 1 - Degree distribution for graphs

EX_GRAPH0 = {
             0 : set([1, 2]),
             1 : set([]),
             2 : set([])
             }

EX_GRAPH1 = {
             0 : set([1, 4, 5]),
             1 : set([2, 6]),
             2 : set([3]),
             3 : set([0]),
             4 : set([1]),
             5 : set([2]),
             6 : set([])
             }

EX_GRAPH2 = {
             0 : set([1, 4, 5]),
             1 : set([2, 6]),
             2 : set([3, 7]),
             3 : set([7]),
             4 : set([1]),
             5 : set([2]),
             6 : set([]),
             7 : set([3]),
             8 : set([1, 2]),
             9 : set([0,3,4,5,6,7])
             }

def make_complete_graph(num_nodes) :
# returns complete directed graph(dictionary) with {num_nodes} nodes
    result = {}
    for i in range(num_nodes):
        result[i] = set()
        for j in range(num_nodes):
            if (i <> j):
                result[i].add(j)
    return result

def compute_in_degrees(digraph) :
# returns in_degrees of each nodes in digraph
    result = {}
    for head in digraph:
        result[head] = 0
        for tail in digraph:
            if (head <> tail):	# no self-loop
                if head in digraph[tail] :
                    result[head] += 1
    return result

def in_degree_distribution(digraph) :
# returns unnormalized distribution table of the in-degrees of digraph
    result = {}
    in_degree_table = compute_in_degrees(digraph)
    print in_degree_table
    for key in in_degree_table :
        if result.has_key(in_degree_table[key]):
            result[in_degree_table[key]] += 1
        else:
            result[in_degree_table[key]] = 1
            
    return result