alg_load_graph.py

"""
Provided code for Application portion of Module 1

Imports physics citation graph 
"""

# general imports
import urllib2
import matplotlib.pyplot as plt

# Set timeout for CodeSkulptor if necessary
#import codeskulptor
#codeskulptor.set_timeout(20)


###################################
# Code for loading citation graph

CITATION_URL = "http://storage.googleapis.com/codeskulptor-alg/alg_phys-cite.txt"

def load_graph(graph_url):
    """
    Function that loads a graph given the URL
    for a text representation of the graph
    
    Returns a dictionary that models a graph
    """
    graph_file = urllib2.urlopen(graph_url)
    graph_text = graph_file.read()
    graph_lines = graph_text.split('\n')
    graph_lines = graph_lines[ : -1]
    
    print "Loaded graph with", len(graph_lines), "nodes"
    
    answer_graph = {}
    for line in graph_lines:
        neighbors = line.split(' ')
        node = int(neighbors[0])
        answer_graph[node] = set([])
        for neighbor in neighbors[1 : -1]:
            answer_graph[node].add(int(neighbor))

    return answer_graph



def compute_in_degrees(digraph):
    """
    Takes a directed graph and returns a dictionary with the same set of keys
    whose corresponding values are the number of edges whose head matches a
    particular node.
    """
    result = {}
    for node in digraph:
        result[node] = 0
        for other in digraph:
            if node != other and node in digraph[other]:
                result[node] = result[node] + 1

    return result

def in_degree_distribution(digraph):
    """
    Takes a directed graph and computes the unnormalized distribution of the
    in-degrees of the graph. Returns a dictionary whose keys correspond to
    in-degrees of nodes in the graph.
    """
    graph_size = len(digraph)
    in_degrees = compute_in_degrees(digraph)
    result = {}
    total = 0
    for val in in_degrees:
        result[val] = 0
        for node in in_degrees:
            if in_degrees[node] == val:
                result[val] += 1.0 / graph_size
                total += 1.0 / graph_size
    result[0] = 1 - total
    return result



citation_graph = load_graph(CITATION_URL)
print in_degree_distribution(citation_graph)