머리가 굳는 느낌이라 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