def dumpjson_graph(self):
     assert self.COMM.rank==0        
     import json
     import networkx as nx
     from networkx.readwrite import json_graph
     h=self.h
     #import pickle
     #json_graph.node_link_graph
     #Create a whole network of both transmitter types.
     self.global_whole_net=nx.compose(self.global_ecg, self.global_icg)
     self.global_whole_net.remove_nodes_from(nx.isolates(self.global_whole_net))
     self.global_icg.remove_nodes_from(nx.isolates(self.global_icg))
     self.global_ecg.remove_nodes_from(nx.isolates(self.global_ecg))
     
     d =[]
     whole=nx.to_numpy_matrix(self.global_whole_net)  
     #TODO sort whole (network) here in Python, as Python is arguably easier to understand than JS. 
     d.append(whole.tolist()) 
     #d.append(self.global_whole_net.tolist())
     #d.append(json_graph.node_link_data(self.global_whole_net))                 
     d.append(self.global_namedict)
     json.dump(d, open('web/js/global_whole_network.json','w'))
     d=json.load(open('web/js/global_whole_network.json','r'))
     #read the object just to prove that is readable.
     d=None #destroy the object.    
     print('Wrote JSON data to web/js/network.json')
 
     print('Wrote node-link JSON data to web/js/network.json')

def create_3comms_bipartite(n,m,p,No_isolates=True):
    
    import community as comm

    from networkx.algorithms import bipartite as bip
    u=0
    while  True:
        G=nx.bipartite_random_graph(n,m,p)
        list_of_isolates=nx.isolates(G)
        if No_isolates:
            G.remove_nodes_from(nx.isolates(G))
        partition=comm.best_partition(G)
        sel=max(partition.values())
        if sel==2 and nx.is_connected(G):
            break
        u+=1
        print u,sel
    ndlss=bip.sets(G)
    ndls=[list(i) for i in ndlss]
    slayer1=ndls[0]
    slayer2=ndls[1]
    layer1=[i for i,v in partition.items() if v==0]
    layer2=[i for i,v in partition.items() if v==1]
    layer3=[i for i,v in partition.items() if v==2]
    edgeList=[]
    for e in G.edges():
        if (e[0] in slayer1 and e[1] in slayer2) or (e[0] in slayer2 and e[1] in slayer1):
            edgeList.append(e)
    return G,layer1,layer2,layer3,slayer1,slayer2,edgeList,partition

def synthetic_three_level(n,p1,p2,p3,J_isolates=False,F_isolates=False,D_isolates=False):#,isolate_up=True,isolate_down=True):
    
    k=n

    J=nx.erdos_renyi_graph(n,p1) #The first layer graph
    Jis = nx.isolates(J)
    F=nx.erdos_renyi_graph(n,p2) #The second layer graph
    Fis = nx.isolates(F)
    D=nx.erdos_renyi_graph(n,p3) #The third layer graph
    Dis = nx.isolates(D)

    def translation_graph(J,F,D):
        H1=nx.Graph()
        H2=nx.Graph()
        for i in range(n):
            H1.add_edges_from([(J.nodes()[i],F.nodes()[i])])
            H2.add_edges_from([(F.nodes()[i],D.nodes()[i])])
        return H1, H2

    Jed = set(J.edges())
    Fed = set(F.edges())
    Ded = set(D.edges())
    l=[Jed,Fed,Ded]
    lu = list(set.union(*l))
    JFD=nx.Graph()
    JFD.add_edges_from(lu)

    G=nx.Graph()  #The synthetic two-layer graph
    
    # Relabing nodes maps
    
    mappingF={}
    for i in range(2*n):
        mappingF[i]=n+i
    FF=nx.relabel_nodes(F,mappingF,copy=True)
    
    mappingD={}
    for i in range(2*n):
        if i >n-1:
            mappingD[i]=i-n
        else:
            mappingD[i]=2*n+i
    DD=nx.relabel_nodes(D,mappingD,copy=True)
    
    H1, HH2 = translation_graph(J,FF,DD)
    
    G.add_edges_from(J.edges())
    G.add_edges_from(H1.edges())
    G.add_edges_from(DD.edges())
    G.add_edges_from(HH2.edges())
    G.add_edges_from(FF.edges())

    edgeList = []
    for e in H1.edges():
        edgeList.append(e)
    for e in HH2.edges():
        edgeList.append(e)
    
    return G, J, FF, DD, JFD, edgeList  

def whole_graph_metrics(graph, weighted=False):
    graph_metrics = {}

    # Shortest average path length
    graph_metrics['avg_shortest_path'] = \
        nx.average_shortest_path_length(graph, weight=weighted)

    # Average eccentricity
    ecc_dict = nx.eccentricity(graph)
    graph_metrics['avg_eccentricity'] = np.mean(np.array(ecc_dict.values()))

    # Average clustering coefficient
    # NOTE: Option to include or exclude zeros
    graph_metrics['avg_ccoeff'] = \
        nx.average_clustering(graph, weight=weighted, count_zeros=True)

    # Average node betweeness
    avg_node_btwn_dict = nx.betweenness_centrality(graph, normalized=True)
    graph_metrics['avg_node_btwn'] = \
        np.mean(np.array(avg_node_btwn_dict.values()))

    # Average edge betweeness
    avg_edge_btwn_dict = nx.edge_betweenness_centrality(graph, normalized=True)
    graph_metrics['avg_edge_btwn'] = \
        np.mean(np.array(avg_edge_btwn_dict.values()))

    # Number of isolates
    graph_metrics['isolates'] = len(nx.isolates(graph))

    return graph_metrics

def test_dim_error():
    import sys
    authority_dict={}
    graph_file = '/home/michal/SALSA_files/tmp/real_run/middle_graph_authority'
    G_new = gm.read_graph_from_file(graph_file)
    isolates = nx.isolates(G_new)
    print 'num of isolates: '+str(len(isolates)); sys.stdout.flush()
    num_of_not_isolates = G_new.number_of_nodes() - len(isolates)
    authority_dict = {}
    classes = nx.strongly_connected_component_subgraphs(G_new)
    print 'num of classes including isolates: '+str(len(classes)); sys.stdout.flush()
    #remove classes of isolated nodes:   
    classes[:] = [ c for idx,c in enumerate(classes) if c.nodes()[0] not in isolates ]
    
    print 'num of classes NOT including isolates: '+str(len(classes)); sys.stdout.flush()
    for subG in classes:
        #print type(subG)
        out_file = ''.join(['/home/michal/SALSA_files/tmp/real_run/graph_',str(classes.index(subG))])
        gm.write_graph_to_file(subG, out_file)
        tmp_d = salsa.eig_calc(subG, normalize=num_of_not_isolates)    #power_iteration(subG)
    '''    
        for k,v in tmp_d.items():
            authority_dict[G.nodes()[k]] = v
        #print power_iteration(subG, tol=1.0e-10)
    for i in isolates:
        authority_dict[G.nodes()[i]] = 0
    #print authority_dict
    print '\n--- calc_salsa_per_class took: '+str(datetime.now()-startTime); sys.stdout.flush()'''
    return

def graph_preprocessing_with_counts(G_input=None, save_file=None):

    if not G_input:
        graph_file = os.path.join(work_dir, "adj_graph.p")
        G = nx.read_gpickle(graph_file)
    else:
        G = G_input.copy()

    print "Raw graph size:", G.size()
    print "Raw graph nodes", G.number_of_nodes()

    profile2prob = {l.split()[0]: float(l.split()[1]) for l in open(os.path.join(work_dir, 'profile_weight.txt'))}

    for edge in G.edges(data=True):
        nodes = edge[:2]
        _weight = edge[2]['weight']
        _count = edge[2]['count']
        
        if _count < 3:
            G.remove_edge(*nodes)

    print "Pre-processed graph size", G.size()
    print "Pre-processed graph nodes", G.number_of_nodes()

    G.remove_nodes_from(nx.isolates(G))

    print "Pre-processed graph size", G.size()
    print "Pre-processed graph nodes", G.number_of_nodes()
    
    if save_file:
        print "Saving to", save_file
        nx.write_gpickle(G,save_file)

    return G

def residual_graph(G,v):
    # Input, G, the original graph
    # v, the vertex added to the vertex cover
    # degreeQ, the priority queue with node degrees
    #    from the original graph
    # Output: G', the graph consisting of edges not
    #    convered by C and the nodes not in C

    G1 = nx.Graph()
    for node in G.nodes():
        G1.add_node(node)
    for edge in G.edges():
        G1.add_edge(edge[0],edge[1])
    
    # Remove all edges in G that are covered by v
    neighbors = G1.neighbors(v)
    for u in neighbors:
        G1.remove_edge(v,u)
    # Remove v from G
    G1.remove_node(v)
        
    # Remove isolated nodes from G (this will include v)
    isolates = nx.isolates(G1)
    for node in isolates:
        G1.remove_node(node)
    #    degreeQ.remove_node(node)  
    return G1 

def make_shared_page_editing_network(alter_revisions_dict,threshold):
    
    inverted_alter_revisions_dict = invert_alter_revisions(alter_revisions_dict)
    
    # Make the graph
    g = nx.DiGraph()
    for page,users in inverted_alter_revisions_dict.iteritems():
        user_list = users.keys()
        for num,user in enumerate(user_list[:-1]):
            next_user = user_list[num+1]
            if g.has_edge(user,next_user):
                g[user][next_user]['weight'] += 1
            else:
                g.add_edge(user,next_user,weight=1)
                
    # If edge is below threshold, remove it            
    for i,j,d in g.edges_iter(data=True):
        if d['weight'] < threshold:
            g.remove_edge(i,j)
            
    # Remove self-loops
    for i,j,d in g.edges_iter(data=True):
        if i == j:
            g.remove_edge(i,j)
    
    # Remove resulting isolates
    isolates = nx.isolates(g)
    for isolate in isolates:
        g.remove_node(isolate)
    
    return g

    def _proba(self, G):
        """
        [TO BE TESTED]
        Compute transition probabilities. Only available when feature_type is 'fisher'.
        Parameters
        -------
        :param G: DAG of Fisher features.
            Attribute 'proba_': edge attribute, float
            Transition probability that one node transfers to another.
        :return: G, DAG with edge attribute 'proba_' assigned.
        """
        for node in G.nodes():
            s = (np.sum(G[node][x]['kern_unnorm_']) for x in G.successors(node))
            s = sum(s)
            for successor_ in G.successors(node):
                if s == 0:
                    G[node][successor_]['proba_'] = 0.
                else:
                    G[node][successor_]['proba_'] = np.sum(G[node][successor_]['kern_unnorm_'])/s
                if G[node][successor_]['proba_'] < self.proba_threshold:
                    G.remove_edge(node, successor_)

        isolated_ = nx.isolates(G)
        G.remove_nodes_from(isolated_)

        return G

def correlation_betweenness_degree_on_ErdosNetwork():
    G = nx.read_pajek("dataset/Erdos971.net")
    isolated_nodes = nx.isolates(G)
    G.remove_nodes_from(isolated_nodes)

    print nx.info(G)
    ND, ND_lambda = ECT.get_number_of_driver_nodes(G)
    print "ND = ", ND
    print "ND lambda:", ND_lambda
    ND, driverNodes = ECT.get_driver_nodes(G)
    print "ND =", ND

    degrees = []
    betweenness = []
    tot_degree = nx.degree_centrality(G)
    tot_betweenness = nx.betweenness_centrality(G,weight=None)

    for node in driverNodes:
        degrees.append(tot_degree[node])
        betweenness.append(tot_betweenness[node])

    with open("results/driver_degree_Erdos.txt", "w") as f:
        for x in degrees:
            print >> f, x
    with open("results/driver_betweenness_Erdos.txt", "w") as f:
        for x in betweenness:
            print >> f, x
    with open("results/tot_degree_Erdos.txt", "w") as f:
        for key, value in tot_degree.iteritems():
            print >> f, value

    with open("results/tot_betweenness_Erdos.txt", "w") as f:
        for key, value in tot_betweenness.iteritems():
            print >> f, value

def getRandomPageRanks(filename):
	Ga=nx.read_graphml(sys.argv[1])

	# create a copy of the graph and extract giant component
	# get component size distribution
	cc=nx.connected_components(Ga)
	cc_dict={}
	for x in range(0,len(cc)):
		try:
			cc_dict[len(cc[x])].append(x)
		except KeyError:
			cc_dict[len(cc[x])]=[]
			cc_dict[len(cc[x])].append(x)

	isolates=nx.isolates(Ga)

	rg=nx.fast_gnp_random_graph(Ga.number_of_nodes(),2.0*Ga.number_of_edges()/(Ga.number_of_nodes()*(Ga.number_of_nodes()-1)))
	c_rg=nx.average_clustering(rg)
	rg_cc=nx.connected_component_subgraphs(rg)[0]
	rg_asp=nx.algorithms.shortest_paths.generic.average_shortest_path_length(rg_cc)

	p_rg=community.best_partition(rg_cc)
	m_rg=community.modularity(p_rg,rg_cc)

	pageranks = nx.pagerank_numpy(rg)
	return pageranks

def rand_delete(G, num_nodes):
    G=nx.convert_node_labels_to_integers(G,first_label=0)
    nodes_to_delete=list(random_integers(low=0,high=len(G.nodes()),size=num_nodes))
    G.remove_nodes_from(nodes_to_delete)
    isos=nx.isolates(G)
    G.remove_nodes_from(isos)
    return(G)

def make_shared_user_editing_network(alter_revisions_dict,threshold):
    # Make the graph
    net = nx.DiGraph()
    for editor,revisions in alter_revisions_dict.iteritems():
        articles = [r['title'] for r in revisions]
        for num,article in enumerate(articles[:-1]):
            if net.has_edge(article,articles[num+1]):
                net[article][articles[num+1]]['weight'] += 1
            else:
                net.add_edge(article,articles[num+1],weight=1)
                
    # If edge is below threshold, remove it            
    for i,j,d in net.edges_iter(data=True):
        if d['weight'] < threshold:
            net.remove_edge(i,j)
            
    # Remove self-loops
    for i,j,d in net.edges_iter(data=True):
        if i == j:
            net.remove_edge(i,j)
    
    # Remove resulting isolates
    isolates = nx.isolates(net)
    for isolate in isolates:
        net.remove_node(isolate)
    
    return net

def reciprocated_graph(D):
	G=D.to_undirected() # copy 
	for (u,v) in D.edges(): 
		if not D.has_edge(v,u): 
			G.remove_edge(u,v)
	G.remove_nodes_from(nx.isolates(G))
	return G

def vehicle_accusation_graph(n, p, seed=None, directed=True):
    """Return a random vehicle accusation graph G_{n,p}.
    Chooses each of the possible edges with accusation probability p.
    Parameters
    ----------
    n : int
        The number of vehicles.
    p : float
        Probability for accusation.
    seed : int, optional
        Seed for random number generator (default=None).
    directed : bool, optional (default=True)
        If True return a directed graph
    """

    if directed:
        G=nx.DiGraph()
    else:
        G=nx.Graph()
    G.add_nodes_from(range(n))
    G.name='Vehicle_accusation_graph({}, {})'.format(n, p)
    if p<=0:
        return G
    if p>=1:
        return complete_graph(n,create_using=G)

    if not seed is None:
        random.seed(seed)

    if G.is_directed():
        edges=itertools.permutations(range(n),2)
    else:
        edges=itertools.combinations(range(n),2)

    for e in edges:
        if random.random() < p:
            G.add_edge(*e)

    """
    Remove all isolates in the graph & relabel the nodes of the graph
    """
    if nx.isolates(G):
        G.remove_nodes_from(nx.isolates(G))
        mapping = dict(zip(G.nodes(), range(G.number_of_nodes())))
        G = nx.relabel_nodes(G, mapping)

    return G

def set_isolated(nodes_list, mdg):
    ts = int(time.mktime(datetime.now().timetuple()))   # Windows-compatible
    dsg = extract_dpsg(mdg, ts, True)
    usg = dsg.to_undirected()
    isolated_nodes = set(nx.isolates(usg))
    for node in nodes_list:
        if node['id'] in isolated_nodes:
            node['isolated'] = True

def create_conn_random_graph(nodes,p):
    while  True:
        # G=nx.connected_watts_strogatz_graph(25, 2, 0.8, tries=100)
        G=nx.erdos_renyi_graph(nodes,p)
        if nx.is_connected(G):
            break
    G.remove_nodes_from(nx.isolates(G))
    return G

def set_isolated(nodes_list, mdg):
    ts = int(datetime.now().strftime("%s"))
    dsg = extract_dpsg(mdg, ts, True)
    usg = dsg.to_undirected()
    isolated_nodes = set(nx.isolates(usg))
    for node in nodes_list:
        if node['id'] in isolated_nodes:
            node['isolated'] = True

 def _generate_nlist():
     G = self.graph
     # TODO: imaginative, but shit. revise.
     isolates = set(nx.isolates(G))
     independent = set(nx.maximal_independent_set(G)) - isolates
     dominating = set(nx.dominating_set(G)) - independent - isolates
     rest = set(G.nodes()) - dominating - independent - isolates
     nlist = list(map(sorted, filter(None, (isolates, independent, dominating, rest))))
     return nlist

def create_conn_random_graph(nodes,p):
    while  True:
        # G=nx.connected_watts_strogatz_graph(25, 2, 0.8, tries=100)
        G=nx.erdos_renyi_graph(nodes,p)
        if nx.is_connected(G):
            break
    G.remove_nodes_from(nx.isolates(G))
    sstt="Erdos-Renyi Random Graph with %i nodes and probability %.02f" %(nodes,p)
    return G, sstt