def test_K4(self):
     """Betweenness centrality: K4"""
     G=networkx.complete_graph(4)
     b=networkx.current_flow_betweenness_centrality_subset(G,
                                                           list(G),
                                                           list(G),
                                                           normalized=True)
     b_answer=networkx.current_flow_betweenness_centrality(G,normalized=True)
     for n in sorted(G):
         assert_almost_equal(b[n],b_answer[n])
     # test weighted network
     G.add_edge(0,1,{'weight':0.5,'other':0.3})
     b=networkx.current_flow_betweenness_centrality_subset(G,
                                                           list(G),
                                                           list(G),
                                                           normalized=True,
                                                           weight=None)
     for n in sorted(G):
         assert_almost_equal(b[n],b_answer[n])
     b=networkx.current_flow_betweenness_centrality_subset(G,
                                                           list(G),
                                                           list(G),
                                                           normalized=True)
     b_answer=networkx.current_flow_betweenness_centrality(G,normalized=True)
     for n in sorted(G):
         assert_almost_equal(b[n],b_answer[n])
     b=networkx.current_flow_betweenness_centrality_subset(G,
                                                           list(G),
                                                           list(G),
                                                           normalized=True,
                                                           weight='other')
     b_answer=networkx.current_flow_betweenness_centrality(G,normalized=True,weight='other')
     for n in sorted(G):
         assert_almost_equal(b[n],b_answer[n])

 def test_P4_normalized(self):
     """Betweenness centrality: P4 normalized"""
     G=networkx.path_graph(4)
     b=networkx.current_flow_betweenness_centrality(G,normalized=True)
     b_answer={0: 0, 1: 2./3, 2: 2./3, 3:0}
     for n in sorted(G):
         assert_almost_equal(b[n],b_answer[n])

 def test_K4_normalized(self):
     """Betweenness centrality: K4"""
     G = networkx.complete_graph(4)
     b = networkx.current_flow_betweenness_centrality_subset(G, G.nodes(), G.nodes(), normalized=True)
     b_answer = networkx.current_flow_betweenness_centrality(G, normalized=True)
     for n in sorted(G):
         assert_almost_equal(b[n], b_answer[n])

def compute_centrality(star_dict, edge_dict):
    
    #build up a nx graph
    galaxy = networkx.Graph()
    for v, vertex in star_dict.iteritems():
        galaxy.add_node(v)
    
    for v, neighbors in edge_dict.iteritems():
        for n in neighbors:
            galaxy.add_edge(v,n)
            
    print "betweenness"
    betweenness_map = networkx.current_flow_betweenness_centrality(galaxy)
    betweenness_map = normalize(betweenness_map)
    
    for key, value in betweenness_map.iteritems():
        star_dict[key]['betweenness'] = value
        
    print "closeness"
    closeness_map = networkx.current_flow_closeness_centrality(galaxy)
    closeness_map = normalize(closeness_map)
    
    for key, value in closeness_map.iteritems():
        star_dict[key]['closeness'] = value
        

    print "pagerank"
    pagerank_map = networkx.pagerank_scipy(galaxy)
    pagerank_map = normalize(pagerank_map)
    
    for key, value in pagerank_map.iteritems():
        star_dict[key]['pagerank'] = value

def describe(G, ny_tri, chems):
	global describeNetwork
	'''
	Describe the network: degrees, clustering, and centrality measures
	'''	
	# Degree
	# The number of connections a node has to other nodes.
	degrees= nx.degree(G)
	degrees_df = pd.DataFrame(degrees.items(), columns=['Facility', 'Degrees'])
	values = sorted(set(degrees.values())) 
	hist = [degrees.values().count(x) for x in values]
	plt.figure()
	plt.plot(values, hist,'ro-') # degree
	plt.xlabel('Degree')
	plt.ylabel('Number of nodes')
	plt.title('Degree Distribution')
	plt.savefig('output/degree_distribution.png')

	# Clustering coefficients
	# The bipartie clustering coefficient is a measure of local density of connections.
	clust_coefficients = nx.clustering(G)
	clust_coefficients_df = pd.DataFrame(clust_coefficients.items(), columns=['Facility', 'Clustering Coefficient'])
	clust_coefficients_df = clust_coefficients_df.sort('Clustering Coefficient', ascending=False)
	#print clust_coefficients_df

	# Node centrality measures
	FCG=list(nx.connected_component_subgraphs(G, copy=True))[0]
	# Current flow betweenness centrality
	# Current-flow betweenness centrality uses an electrical current model for information spreading 
	# in contrast to betweenness centrality which uses shortest paths.
	betweeness = nx.current_flow_betweenness_centrality(FCG)
	betweeness_df = pd.DataFrame(betweeness.items(), columns=['Facility', 'Betweeness'])
	betweeness_df = betweeness_df.sort('Betweeness', ascending=False)
	# Closeness centrality
	# The closeness of a node is the distance to all other nodes in the graph 
	# or in the case that the graph is not connected to all other nodes in the connected component containing that node.
	closeness = nx.closeness_centrality(FCG)
	closeness_df = pd.DataFrame(closeness.items(), columns=['Facility', 'Closeness'])
	closeness_df = closeness_df.sort('Closeness', ascending=False)
	# Eigenvector centrality
	# Eigenvector centrality computes the centrality for a node based on the centrality of its neighbors.
	# In other words, how connected a node is to other highly connected nodes.
	eigenvector = nx.eigenvector_centrality(FCG)
	eigenvector_df = pd.DataFrame(eigenvector.items(), columns=['Facility', 'Eigenvector'])
	eigenvector_df = eigenvector_df.sort('Eigenvector', ascending=False)

	# Create dataframe of facility info
	fac_info = ny_tri[['tri_facility_id','facility_name', 'primary_naics', 'parent_company_name']].drop_duplicates()
	fac_info.rename(columns={'facility_name':'Facility'}, inplace=True)

	# Merge everything
	describeNetwork = degrees_df.merge(
		clust_coefficients_df,on='Facility').merge(
		betweeness_df,on='Facility').merge(
		closeness_df, on='Facility').merge(
		eigenvector_df, on='Facility').merge(
		fac_info, on='Facility', how='left').merge(
		chems, on='Facility', how='left')
	describeNetwork = describeNetwork.sort('Degrees', ascending=False)
	describeNetwork.to_csv('output/describeNetwork.csv')

 def test_P4(self):
     """Betweenness centrality: P4"""
     G = nx.path_graph(4)
     b = nx.current_flow_betweenness_centrality_subset(G, list(G), list(G), normalized=True)
     b_answer = nx.current_flow_betweenness_centrality(G, normalized=True)
     for n in sorted(G):
         assert_almost_equal(b[n], b_answer[n])

 def test_P4(self):
     """Betweenness centrality: P4"""
     G=nx.path_graph(4)
     b=nx.current_flow_betweenness_centrality(G,normalized=False)
     b_answer={0: 0, 1: 2, 2: 2, 3: 0}
     for n in sorted(G):
         assert_almost_equal(b[n],b_answer[n])

 def test_K4(self):
     """Betweenness centrality: K4"""
     G=networkx.complete_graph(4)
     b=networkx.current_flow_betweenness_centrality(G,normalized=False)
     b_answer={0: 0.75, 1: 0.75, 2: 0.75, 3: 0.75}
     for n in sorted(G):
         assert_almost_equal(b[n],b_answer[n])

def centrality(net):
    values ={}
    close = nx.closeness_centrality(net, normalized= True)
    eigen = nx.eigenvector_centrality_numpy(net)
    page = nx.pagerank(net)
    bet = nx.betweenness_centrality(net,normalized= True)
    flow_c = nx.current_flow_closeness_centrality(net,normalized= True)
    flow_b = nx.current_flow_betweenness_centrality(net,normalized= True)
    load = nx.load_centrality(net, normalized = True)
    com_c = nx.communicability_centrality(net)
    com_b = nx.communicability_betweenness_centrality(net, normalized= True)
    degree = net.degree()
    
    file3 = open("bl.csv",'w')
    for xt in [bet,load,degree,page,flow_b,com_c,com_b,eigen,close,flow_c]:#[impo,bet,flow_b,load,com_c,com_b] :
        for yt in [bet,load,degree,page,flow_b,com_c,com_b,eigen,close,flow_c]:#[impo,bet,flow_b,load,com_c,com_b] :
            corr(xt.values(),yt.values(),file3)
        print
        file3.write("\n")
    file3.close()
    #plt.plot(x,y, 'o')
    #plt.plot(x, m*x + c, 'r', label='Fitted line')
    #plt.show()
    #for key,item in close.iteritems() :
        #values[key] = [impo.get(key),bet.get(key),flow_b.get(key), load.get(key),com_c.get(key),com_b.get(key)]
        
    return values

 def test_grid(self):
     "Approximate current-flow betweenness centrality: 2d grid"
     G=nx.grid_2d_graph(4,4)
     b=nx.current_flow_betweenness_centrality(G,normalized=True)
     epsilon=0.1
     ba = approximate_cfbc(G,normalized=True, epsilon=0.5*epsilon)
     for n in sorted(G):
         assert_allclose(b[n],ba[n],atol=epsilon)

 def test_K4(self):
     "Approximate current-flow betweenness centrality: K4"
     G=nx.complete_graph(4)
     b=nx.current_flow_betweenness_centrality(G,normalized=False)
     epsilon=0.1
     ba = approximate_cfbc(G,normalized=False, epsilon=0.5*epsilon)
     for n in sorted(G):
         assert_allclose(b[n],ba[n],atol=epsilon*len(G)**2)

 def test_star(self):
     """Betweenness centrality: star """
     G = nx.Graph()
     nx.add_star(G, ["a", "b", "c", "d"])
     b = nx.current_flow_betweenness_centrality_subset(G, list(G), list(G), normalized=True)
     b_answer = nx.current_flow_betweenness_centrality(G, normalized=True)
     for n in sorted(G):
         assert_almost_equal(b[n], b_answer[n])

def current_flow_betweenness(G):
    """Current-flow betweenness centrality"""
    G = G.to_undirected()
    G = invert_edge_weights(G)
    if nx.is_connected(G):
        return nx.current_flow_betweenness_centrality(G)
    else:
        return _aggregate_for_components(G, nx.current_flow_betweenness_centrality)

 def test_star(self):
     """Betweenness centrality: star """
     G=nx.Graph()
     nx.add_star(G, ['a', 'b', 'c', 'd'])
     b=nx.current_flow_betweenness_centrality(G,normalized=True)
     b_answer={'a': 1.0, 'b': 0.0, 'c': 0.0, 'd':0.0}
     for n in sorted(G):
         assert_almost_equal(b[n],b_answer[n])

 def test_K4_normalized(self):
     "Approximate current-flow betweenness centrality: K4 normalized"
     G=networkx.complete_graph(4)
     b=networkx.current_flow_betweenness_centrality(G,normalized=True)
     epsilon=0.1
     ba = approximate_cfbc(G,normalized=True, epsilon=epsilon)
     for n in sorted(G):
         assert_allclose(b[n],ba[n],atol=epsilon)

 def test_solers(self):
     """Betweenness centrality: alternate solvers"""
     G=nx.complete_graph(4)
     for solver in ['full','lu','cg']:
         b=nx.current_flow_betweenness_centrality(G,normalized=False,
                                                        solver=solver)
         b_answer={0: 0.75, 1: 0.75, 2: 0.75, 3: 0.75}
         for n in sorted(G):
             assert_almost_equal(b[n],b_answer[n])

 def test_K4_normalized(self):
     """Betweenness centrality: K4"""
     G=nx.complete_graph(4)
     b=nx.current_flow_betweenness_centrality(G,normalized=True)
     b_answer={0: 0.25, 1: 0.25, 2: 0.25, 3: 0.25}
     for n in sorted(G):
         assert_almost_equal(b[n],b_answer[n])
     G.add_edge(0,1,{'weight':0.5,'other':0.3})
     b=nx.current_flow_betweenness_centrality(G,normalized=True,weight=None)
     for n in sorted(G):
         assert_almost_equal(b[n],b_answer[n])
     wb_answer={0: 0.2222222, 1: 0.2222222, 2: 0.30555555, 3: 0.30555555}
     b=nx.current_flow_betweenness_centrality(G,normalized=True)
     for n in sorted(G):
         assert_almost_equal(b[n],wb_answer[n])
     wb_answer={0: 0.2051282, 1: 0.2051282, 2: 0.33974358, 3: 0.33974358}
     b=nx.current_flow_betweenness_centrality(G,normalized=True,weight='other')
     for n in sorted(G):
         assert_almost_equal(b[n],wb_answer[n])

 def f30(self):
     return "ND"
     start = 0
     try:
         c_vals = nx.current_flow_betweenness_centrality(self.G).values()
         res = sum(c_vals)
     except nx.NetworkXError:
         res = "ND"
     stop = 0
     # self.feature_time.append(stop - start)
     return res

 def test_star(self):
     """Betweenness centrality: star """
     G=networkx.Graph()
     G.add_star(['a','b','c','d'])
     b=networkx.current_flow_betweenness_centrality_subset(G,
                                                           G.nodes(),
                                                           G.nodes(),
                                                           normalized=True)
     b_answer=networkx.current_flow_betweenness_centrality(G,normalized=True)
     for n in sorted(G):
         assert_almost_equal(b[n],b_answer[n])

 def DegreeOfInterestMIPs(self, user, obj, alpha=0.3, beta=0.7):
     #compute apriori importance of node obj (considers effective conductance)
     current_flow_betweeness = nx.current_flow_betweenness_centrality(True, 'weight');
     api_obj = current_flow_betweeness[obj]  #node centrality
 #    print 'obj'
 #    print obj
 #    print 'api_obj'
 #    print api_obj
     #compute proximity between user node and object node using Cycle-Free-Edge-Conductance from Koren et al. 2007
     cfec_user_obj = self.CFEC(user,obj)
 #    print 'cfec_user_obj'
 #    print cfec_user_obj
     return alpha*api_obj+beta*cfec_user_obj #TODO: check that scales work out for centrality and proximity, otherwise need some normalization