"""
Compare an In-degree distribution for a graph generated by the ER algorithm
to that of the physics paper citation graph.
"""
import random
import matplotlib.pyplot as plt


def er_algorithm(num_nodes, prob_edge):
    """
    Returns a random digraph with number of nodes 'num_nodes' and
    the probability of an edge 'prob_edge'
    """
    node_list = [node for node in range(num_nodes)]
    digraph = {}
    for node_tail in node_list:
        digraph[node_tail] = set([])
        for node_head in node_list:
            if node_tail != node_head:
                a = random.random()
                if a < prob_edge:
                    digraph[node_tail].add(node_head)
    return digraph

# print er_algorithm(5, 0.5)
# print er_algorithm(5, 0)
# print er_algorithm(5, 1)
# print er_algorithm(5, 0.1)


def in_degree_distribution(digraph):
    """
    Takes a digraph as input and returns a dictionary with
    keys correspond to #in-degrees of nodes in the graph.
    The value associated with each particular in-degree is
    the number of nodes with that in-degree.
    """
    # Compute the in-degree dictionary.
    indeg_dict = {}
    for node in digraph:
        indeg_dict[node] = 0
        for adjacent_node in digraph:
            if node != adjacent_node:
                out_deg_nodes_set = digraph[adjacent_node]
                for elem in out_deg_nodes_set:
                    if elem == node:
                        indeg_dict[node] += 1

    # Compute the distribution from the in-degree dictionary.
    in_deg_dist = {}
    for node in indeg_dict:
        num_in_deg = indeg_dict[node]
        if in_deg_dist.has_key(num_in_deg):
            in_deg_dist[num_in_deg] += 1
        else:
            in_deg_dist[num_in_deg] = 1

    return in_deg_dist


def draw_log_log_plot(in_deg_dist):
    x = in_deg_dist.keys()
    y = in_deg_dist.values()
    if 0 in x:
        x.remove(0)
        y.pop()
    plt.figure(figsize=(10, 8), dpi = 80)
    #plt.loglog(x, y, basex=2, basey=2)
    #plt.bar(x, y)
    plt.plot(x, y, 'r--', lw=2)
    plt.grid(True)
    plt.xlabel('Value of in-degree')
    plt.ylabel('Number of nodes')
    plt.text(0.5, 115, "n = 1000")
    plt.text(0.5, 110, "p = 0.013")
    plt.title('Linear plot of the normalized in-degree distribution of the ER digraph')
    plt.show()


def run_example():
    digraph = er_algorithm(1000, 0.013)
    in_deg_dist = in_degree_distribution(digraph)
    print in_deg_dist
    draw_log_log_plot(in_deg_dist)

run_example()