def compareGraphs(g1, g2):
    
    """#Compares the quantitative properties of two graph. So I can check the coarse graining. """

    
    #Nodes and edges
    print 'Graph1: #(Nodes, Edges) = (' + str(len(g1.nodes())) + ', ' + str(len(g1.edges())) + ')'
    print 'Graph2: #(Nodes, Edges) = (' + str(len(g2.nodes())) + ', ' + str(len(g2.edges())) + ')'

    #Connected Components
    #print '\n#CCs for graph 1: ' + str(len(nx.connected_components(g1)))
    #print '#CCs for graph 2: ' + str(len(nx.connected_components(g2)))
    
    plt.hist([len(i) for i in nx.connected_components(g1)])
    plt.hist([len(i) for i in nx.connected_components(g2)])
    plt.title('Cluster Size')
    plt.xlabel('Cluster Size')
    plt.ylabel('#Cluster')
    show()
    
    #Degree Distribution
    plt.hist(nx.degree_histogram(g1))
    plt.hist(nx.degree_histogram(g2))
    plt.title('Degree Distribution' )
    plt.xlabel('Degree')
    plt.ylabel('#Nodes')
    show()
    
    #Betweeness --- this is by far the most compuationally demanding.
    plt.hist(nx.betweenness_centrality(g1, normalized = False).values())
    plt.hist(nx.betweenness_centrality(g2, normalized = False).values())
    plt.title('Distribution of Betweenness' )
    plt.xlabel('Betweenness')
    plt.ylabel('#Nodes')
    show()        

def degree_stats(graph_ref_list, graph_pred_list, is_parallel=False):
    ''' Compute the distance between the degree distributions of two unordered sets of graphs.
    Args:
      graph_ref_list, graph_target_list: two lists of networkx graphs to be evaluated
    '''
    sample_ref = []
    sample_pred = []
    # in case an empty graph is generated
    graph_pred_list_remove_empty = [G for G in graph_pred_list if not G.number_of_nodes() == 0]

    prev = datetime.now()
    if is_parallel:
        with concurrent.futures.ProcessPoolExecutor() as executor:
            for deg_hist in executor.map(degree_worker, graph_ref_list):
                sample_ref.append(deg_hist)
        with concurrent.futures.ProcessPoolExecutor() as executor:
            for deg_hist in executor.map(degree_worker, graph_pred_list_remove_empty):
                sample_pred.append(deg_hist)

    else:
        for i in range(len(graph_ref_list)):
            degree_temp = np.array(nx.degree_histogram(graph_ref_list[i]))
            sample_ref.append(degree_temp)
        for i in range(len(graph_pred_list_remove_empty)):
            degree_temp = np.array(nx.degree_histogram(graph_pred_list_remove_empty[i]))
            sample_pred.append(degree_temp)
    print(len(sample_ref),len(sample_pred))
    mmd_dist = mmd.compute_mmd(sample_ref, sample_pred, kernel=mmd.gaussian_emd)
    elapsed = datetime.now() - prev
    if PRINT_TIME:
        print('Time computing degree mmd: ', elapsed)
    return mmd_dist

def main():
	global g
	global expanded
	set_g()
	degree_dict = get_degree_dict()
	print len(g.nodes())
	label_ordered_list = get_ordered_label_list(degree_dict)
	for item in label_ordered_list:
		print item
		print len(item[1])
	print nx.degree_histogram(g)
	draw(g)

def degree_distribution_comparison(g, g1, title, model_name):
    # get the degree histogram
    hist = nx.degree_histogram(g)
    hist1 = nx.degree_histogram(g1)
    plt.plot(range(0, len(hist)), hist, ".", markersize=10, label="Actor Network")
    plt.plot(range(0, len(hist1)), hist1, "r.", markersize=10, label=model_name)
    plt.title(title, fontsize=15)
    plt.xlabel("Degree", fontsize=10, labelpad=-2)
    plt.ylabel("#Nodes", fontsize=10, labelpad=-2)
    plt.tick_params(axis='x', labelsize=9)
    plt.tick_params(axis='y', labelsize=9)
    plt.loglog()
    plt.legend(numpoints=1, loc=0, fontsize="x-small")
    plt.show()

    def plot_degree_histogram(graph):
        plt.rcParams['text.usetex'] = False
        plt.loglog(nx.degree_histogram(graph),'b-', marker='o')

        n = graph.number_of_nodes()
        er = nx.erdos_renyi_graph(n, 0.05)
        ba = nx.barabasi_albert_graph(n, 5)

        plt.loglog(nx.degree_histogram(er), 'r-', marker='o')
        plt.loglog(nx.degree_histogram(ba), 'k-', marker='o')

        plt.xlabel("degree")
        plt.ylabel("rank")
        plt.savefig('degree_histogram.png', dpi=75, transparent=False)

def P_k(DiG,T,WalkerNum):
	#WalkerNum = 10
	#T = 100000
	final = final_state(DiG,T,WalkerNum)
	degree_Num = {}
	kin = DiG.in_degree().values()
	k = DiG.degree().values()
	degree_Num_k = {}
	degree_histogram,_ = np.histogram(kin,np.arange(0,max(kin)+2,1))
	degree_histogram2 = nx.degree_histogram(DiG)
	#degree_histogram = nx.degree_histogram(DiG)
	for node in final:
		k = DiG.in_degree(node)
		if k in degree_Num:
			degree_Num[k]+=1
		else:
			degree_Num[k] = 1
	for node in final:
		k = DiG.degree(node)
		if k in degree_Num_k:
			degree_Num_k[k]+=1
		else:
			degree_Num_k[k] = 1

	degree_Probability = {}
	for degree in degree_Num:
		degree_Probability[degree] = 1.0/degree_histogram[degree]*degree_Num[degree]/WalkerNum
	degree_Probability_k = {}
	for degree in degree_Num_k:
		degree_Probability_k[degree] = 1.0/degree_histogram2[degree]*degree_Num_k[degree]/WalkerNum
	return degree_Probability, degree_Probability_k

 def test_approx_coloring(self):
     
     KR = kapoor_rizzi()
     
     degree = 40
     partition_n_nodes = 15
     
     # generate random graph
     g = graph_util().generate_random_regular_bipartite(partition_n_nodes, degree)
     
     # generate arbitrary partitions for approximation algo
     arbitrary = [graph_util().generate_random_regular_bipartite(partition_n_nodes, 1) for i in xrange((degree % 2) + 1)]
     
     # algorithm is destructive so save these for later comparisons
     original_nodes = g.nodes()
     arbitrary_edges = reduce(lambda x,y: x+y, (m.edges() for m in arbitrary))
     original_edges = g.edges() + arbitrary_edges
     
     solution = KR.solve(degree, g, arbitrary)
     
     # check the amount of matchings
     self.assertEqual(len(solution), degree + len(arbitrary), "Didn't get enough matchings")
     # check each matching:
     for matching in solution:
         # matching preserves nodes
         self.assertEquals(matching.nodes(), original_nodes)
         # every node has degree 1
         self.assertEquals(nx.degree_histogram(matching), [0, 2*partition_n_nodes])
     # matchings preserve edges
     matching_edges = reduce(lambda x,y: x+y, (m.edges() for m in solution))
     self.assertEquals(sorted(matching_edges), sorted(original_edges))#, "Mismatch between input and output edges")

  def hist_Graph(self): # sauvegarde les données de l'individu ayant la plus basse fitness
    individu_min=self.pop[pop1.f[0][1]]
    distri = nx.degree_histogram(individu_min.graphe)
    liste = []
    #print "distri"+ str(distri)
    for i in range(0,len(distri)) :
      for j in range(0,distri[i]) :
        liste.append(i)
    plt.hist(liste)
    plt.xlabel("degree")
    plt.ylabel("nombre de noeud")
    plt.show()
    plt.savefig("data/histogram.png")
    plt.close()
    
    # Affichage des distributions de clustering
    distrib=individu_min.loi_clustering_best()
    plt.plot(distrib[0],distrib[1],'bo')
    plt.plot(distrib[0],distrib[2],'r')
    plt.xlabel("k")
    plt.ylabel("C(k)")
    plt.show()
    plt.savefig("data/distrib_clique.png")
    plt.close()

     # Affichage des distributions de clustering
    distribp=individu_min.loi_puissance_best()
    plt.loglog()
    plt.plot(distribp[0],distribp[1],'bo')
    plt.plot(distribp[0],distribp[2],'r')
    plt.xlabel("k")
    plt.ylabel("P(k)")
    plt.show()
    plt.savefig("data/distrib_puissance.png")
    plt.close()

def getGraphStats(threshold=0.5, sector=None, lib="nx"):
	th = re.sub(r'([0-9]*)\.([0-9]*)',r'\1\2',str(threshold))
	if sector != None:
		filename = PROCESSED_FILE_LOC + PREFIX + CRITERIA + "stock_graph_"+lib+"_"+sector+"_th"+th+".xml"
		outFilename = PROCESSED_FILE_LOC + PREFIX + CRITERIA + "stock_graph_stats_"+lib+"_"+sector+"_th"+th
	else:
		filename = PROCESSED_FILE_LOC + PREFIX + CRITERIA + "stock_graph_"+lib+"_th"+th+".xml"
		outFilename = PROCESSED_FILE_LOC + PREFIX + CRITERIA + "stock_graph_stats_"+lib+"_th"+th

	stats = dict()
	if lib == "nx":
		stats = dict()
		g = nx.read_graphml(filename)
		stats['num_nodes'] = g.number_of_nodes()
		stats['num_edges'] = g.number_of_edges()
		#stats['diameter'] = nx.diameter(g)
		stats['clustering_coeff'] = nx.average_clustering(g)
		stats['avg_degree'] = np.average(nx.degree(g).values())
		stats['degree_hist'] = nx.degree_histogram(g)

		y = stats['degree_hist']
		x = range(len(y))
		
	
	f = open(outFilename + ".txt", "wb")
	f.write(str(stats))
	f.close()

	plt.plot(x, y)
	plt.savefig(outFilename + ".png")
	plt.show()

	return stats

def drawNetwork(graph,k):
    pl.figure(k)
    pl.subplot(211)
    #pos = nx.shell_layout(graph) # positions for all nodes
    pos = nx.spring_layout(graph) # positions for all nodes

    # nodes
    nx.draw_networkx_nodes(graph,pos,node_size=200)

    # edges
    nx.draw_networkx_edges(graph,pos,
                        width=3)

    # labels
    # nx.draw_networkx_labels(graph,pos,font_size=20,font_family='sans-serif')

    plt.axis('off')

    # plot degree distribution
    dd = nx.degree_histogram(graph)
    fig = pl.figure(k)
    ax = pl.subplot(212)
    plt.bar(np.arange(len(dd)), dd, width = 0.1)
    plt.axis([0,len(dd),0,max(dd)])
    plt.title("Degree distribution")
    plt.xlabel("degree")
    plt.ylabel("number of nodes")
    #plt.figtext(2, 6, stats, fontsize=15)
    
    plt.draw() # display
    
    return

def calGraph(infile, mode = 1):
	#init Parameter
	inputpath = 'edge_list/'
	outputpath = 'network_output/'
	n = mode
	Data_G = inputpath+infile+'_'+str(n)+'.edgelist'
	
	#init Graph
	G = nx.read_edgelist(Data_G, create_using=nx.DiGraph())
	GU = nx.read_edgelist(Data_G)
	#basci info
	print nx.info(G),'\n', nx.info(GU) 
	average_degree = float(sum(nx.degree(G).values()))/len(G.nodes())
	print 'average degree :', average_degree 
	degree_histogram = nx.degree_histogram(G)
	print 'degree histogram max :', degree_histogram[1]
	desity = nx.density(G)
	print 'desity :', desity

	#Approximation
	#Centrality
	degree_centrality = nx.degree_centrality(G)
	print 'degree centrality top 10 !', sorted_dict(degree_centrality)[:2]
	out_degree_centrality = nx.out_degree_centrality(G)
	print 'out degree centrality top 10 !', sorted_dict(out_degree_centrality)[:2]

def analyse_data(data, threshold=0.66):
    """ perform graph theory analysis on data

    Parameters
    ----------
    data:   dict
        the keys are the names of the datasets
        and the values are dicts that include 'corr' which represents
        the corr matrix from which to derive the graph

    Returns
    -------
    result: dict of graph theory results
        the keys are the names of the datasets
        the values are another dict containing
        'L' - the average shortest path length
        'CC' - the average clustering coefficient
        'DD' - the degree histogram
        'Nodes' - the number of nodes in the graph
        'Edges' - the number of edges in the graph
    """
    result = dict()
    for label, dataset in data.items():
        summary = dict()
        corr = dataset['corr']
        graph, _ = corr_matrix_to_graph(corr, threshold=threshold)
        summary['L'] = nx.average_shortest_path_length(graph)
        summary['CC'] = nx.average_clustering(graph)
        summary['DD'] = nx.degree_histogram(graph)
        summary['Nodes'] = graph.number_of_nodes()
        summary['Edges'] = graph.number_of_edges()
        result[label] = summary

    return result

def pic(c,n):
    G = nx.Graph()
    if c=='gsm':
        with open('E:/data/degree-distribution/'+c+'/305-7-level'+str(n)+'.txt', 'r') as f:
            for position, line in enumerate(f):
                if line.strip().split(' ')[0]!=line.strip().split(' ')[1]:
                    u= line.strip().split(' ')[0]
                    n=line.strip().split(' ')[1]
                    G.add_edge(u, n)
    else:
        with open('E:/data/degree-distribution/'+c+'/49-24-level'+str(n)+'.txt', 'r') as f:
            for position, line in enumerate(f):
                if line.strip().split(' ')[0]!=line.strip().split(' ')[1]:
                    u= line.strip().split(' ')[0]
                    n=line.strip().split(' ')[1]
                    G.add_edge(u, n)
    degree_hist = nx.degree_histogram(G)
    x = range(len(degree_hist))[1:]
    # print(x)
    y = [float(i+1) / float(sum(degree_hist)) for i in degree_hist[1:]]
    bin_x, bin_y = bining_data(x, y, 8)

    d = []
    pd =[]
    for i in range(0, len(bin_x)):
        d.append(np.median(bin_x[i]))
        pd.append(np.median(bin_y[i]))
    return d, pd

    def __init__(self, graph, slow_stuff = False):
        graph.info()

        # paolo - 20070919 - computing also the strongly connected
        # components directly on the directed graph. Changing a
        # directed graph into an undirected usually destroys a lot of
        # its structure and meaning. Let see.  while in the published
        # API there is a method
        # strongly_connected_component_subgraphs(graph), I don't have it
        # on my machine (probably I have an older networkx version),
        # so for now I commented the following code.  the method
        # strongly_connected_component_subgraphs(graph) was added on
        # 07/21/07. See https://networkx.lanl.gov/changeset/640 . On
        # my machine I have "python-networkx/feisty uptodate 0.32-2"
        # while on networkx svn there is already version 0.35.1

        if False:
            self.strongconcom_subgraphs = component.strongly_connected_component_subgraphs(graph)
            strongconcom_subgraph_size = map(len, self.strongconcom_subgraphs)     

            print "size of largest strongly connected components:",
            print ", ".join(map(str, strongconcom_subgraph_size[:10])), "..."
            print "%nodes in largest strongly connected component:",
            print 1.0 * strongconcom_subgraph_size[0] / len(graph)
        
        undir_graph = graph.to_undirected()
        self.concom_subgraphs = component.connected_component_subgraphs(undir_graph)
        concom_subgraph_size = map(len, self.concom_subgraphs)
        print "size of largest connected components:",
        print ", ".join(map(str, concom_subgraph_size[:10])), "..."
        
        print "%nodes in largest connected component:",
        print 1.0 * concom_subgraph_size[0] / len(graph)

        #only work on connected graphs, maybe we could run it on the
        #largest strongly connected component.

        #print "diameter:", distance.diameter(G)
        #print "radius:", distance.radius(graph)

        print "density:", networkx.density(graph)

        print "degree histogram:", networkx.degree_histogram(graph)[:15]

        print "average_clustering:", cluster.average_clustering(graph)

        print "transitivity:", cluster.transitivity(graph)

        if slow_stuff:
            #not yet in my networkx revision  -- try try except
            print "number_of_cliques", cliques.number_of_cliques(graph)

            """this returns a dict with the betweenness centrality of
            every node, maybe we want to compute the average
            betweenness centrality but before it is important to
            understand which measures usually are usually reported in
            papers as peculiar for capturing the characteristics and
            structure of a directed graph."""
            print "betweenness_centrality:",
            print centrality.betweenness_centrality(graph)

def _compute_rc(G):
    """Returns the rich-club coefficient for each degree in the graph
    `G`.

    `G` is an undirected graph without multiedges.

    Returns a dictionary mapping degree to rich-club coefficient for
    that degree.

    """
    deghist = nx.degree_histogram(G)
    total = sum(deghist)
    # Compute the number of nodes with degree greater than `k`, for each
    # degree `k` (omitting the last entry, which is zero).
    nks = (total - cs for cs in accumulate(deghist) if total - cs > 1)
    # Create a sorted list of pairs of edge endpoint degrees.
    #
    # The list is sorted in reverse order so that we can pop from the
    # right side of the list later, instead of popping from the left
    # side of the list, which would have a linear time cost.
    edge_degrees = sorted((sorted(map(G.degree, e)) for e in G.edges()),
                          reverse=True)
    ek = G.number_of_edges()
    k1, k2 = edge_degrees.pop()
    rc = {}
    for d, nk in enumerate(nks):
        while k1 <= d:
            if len(edge_degrees) == 0:
                ek = 0
                break
            k1, k2 = edge_degrees.pop()
            ek -= 1
        rc[d] = 2 * ek / (nk * (nk - 1))
    return rc

def pic(c,n):
    G = nx.Graph()
    if c=='gsm':
        with open('E:/data/degree-distribution/'+c+'/305-7-level'+str(n)+'.txt', 'r') as f:
            for position, line in enumerate(f):
                if line.strip().split(' ')[0]!=line.strip().split(' ')[1]:
                    u= line.strip().split(' ')[0]
                    n=line.strip().split(' ')[1]
                    G.add_edge(u, n)
    else:
        with open('E:/data/degree-distribution/'+c+'/49-24-level'+str(n)+'.txt', 'r') as f:
            for position, line in enumerate(f):
                if line.strip().split(' ')[0]!=line.strip().split(' ')[1]:
                    u= line.strip().split(' ')[0]
                    n=line.strip().split(' ')[1]
                    G.add_edge(u, n)
    degree_hist = nx.degree_histogram(G)
    x = range(len(degree_hist))[1:]
    print(degree_hist)

    y = [float(i+1) / float(sum(degree_hist)) for i in degree_hist[1:]]
    plt.loglog(x, y, 'bo', linewidth = 2)
    plt.title('Degree Distribution')
    plt.ylabel('Probability')
    plt.xlabel('Degree')
    return x, y

def degreeAnalysis(G):
    '''
    Analyze the degree distribution
    '''
    print('--------Node Degree Analysis:--------')
    tempY=nx.degree_histogram(G)
    tempX=list(range(len(tempY))) # isolated node's degree = 0
    X=[];Y=[]
    print('Number of Isolated Node: ',tempY[0])
    for i in range(1,len(tempY)):# here I discard all isolated nodes.
        if tempY[i]!=0:
            Y.append(np.log(tempY[i]))
            X.append(np.log(tempX[i]))
    A=np.array([X,np.ones(len(X))])
    k=np.linalg.lstsq(A.T,Y)[0]
    X=np.array(X)
    regressionLine=k[0]*X+k[1]
    print('Slope of regression line: ',k[0])
    #plt.plot(X,Y,'o',X,regressionLine,label='$Y = %dx$'% k[0])
    plt.plot(X,Y,'o')
    plt.plot(X,regressionLine,'r',label='$Y = %fx+%f$'% (k[0], k[1]))
    plt.legend()
    plt.xlabel('log(k)')
    plt.ylabel('logN(k)')
    plt.title('Node degree analysis')
    plt.show()       

def analyze_graph(G):
	print nx.info(G)
	degree_freq = nx.degree_histogram(G)
	diameter = nx.diameter(G)
	print "Diameter: {0}".format(diameter)
	triangles = nx.triangles(G)
	triangles_values = sorted(triangles.values(), reverse=True)
	print "Triangles: {0}".format(triangles_values)

def cum_deg_histogram(G):
    """Cumulative degree histogram."""
    from numpy import cumsum
    from networkx import degree_histogram
    deg_hist = degree_histogram(G)
    deg_hist.reverse()
    cum_deg_hist = list(cumsum(deg_hist))
    cum_deg_hist.reverse()
    return cum_deg_hist

def make_histogram(aGraph):     
    fig = pylab.figure()
    pylab.title(aGraph.name)
    hist = nx.degree_histogram(aGraph)
    pylab.bar(range(len(hist)), hist, align = 'center')
    pylab.xlim((0, len(hist)))
    pylab.xlabel("Degree of node")
    pylab.ylabel("Number of nodes")
    return fig