def _cliques_heuristic(G, H, k, min_density):
    h_cnumber = nx.core_number(H)
    for i, c_value in enumerate(sorted(set(h_cnumber.values()), reverse=True)):
        cands = set(n for n, c in h_cnumber.items() if c == c_value)
        # Skip checking for overlap for the highest core value
        if i == 0:
            overlap = False
        else:
            overlap = set.intersection(*[
                set(x for x in H[n] if x not in cands)
                for n in cands])
        if overlap and len(overlap) < k:
            SH = H.subgraph(cands | overlap)
        else:
            SH = H.subgraph(cands)
        sh_cnumber = nx.core_number(SH)
        SG = nx.k_core(G.subgraph(SH), k)
        while not (_same(sh_cnumber) and nx.density(SH) >= min_density):
            #!! This subgraph must be writable => .copy()
            SH = H.subgraph(SG).copy()
            if len(SH) <= k:
                break
            sh_cnumber = nx.core_number(SH)
            sh_deg = dict(SH.degree())
            min_deg = min(sh_deg.values())
            SH.remove_nodes_from(n for n, d in sh_deg.items() if d == min_deg)
            SG = nx.k_core(G.subgraph(SH), k)
        else:
            yield SG

 def test_k_core(self):
     # k=0
     k_core_subgraph = nx.k_core(self.H, k=0)
     assert_equal(sorted(k_core_subgraph.nodes()), sorted(self.H.nodes()))
     # k=1
     k_core_subgraph = nx.k_core(self.H, k=1)
     assert_equal(sorted(k_core_subgraph.nodes()), [1, 2, 3, 4, 5, 6])
     # k = 2
     k_core_subgraph = nx.k_core(self.H, k=2)
     assert_equal(sorted(k_core_subgraph.nodes()), [2, 4, 5, 6])

def get_k_core(reviews_path,k_val):
	# Report start of process
	print "=================================="
	print "EXTRACTING K-CORE OF PID GRAPH    "
	print "=================================="

	print "AT STEP #1: Determine which reviewer reviewed which products"
#	with ufora.remotely.downloadAll():
	(PID_to_lines,PID_to_reviewerID) = get_PID_facts(reviews_path)	

	print "At STEP #2: Created weighted edges"
#	with ufora.remotely.downloadAll():
	weighted_edges = get_weighted_edges(PID_to_reviewerID)

	print "AT STEP #3: Create PID graph structure"
#	with ufora.remotely.downloadAll():
	PID_graph = create_graph(PID_to_reviewerID,weighted_edges)	
	print nx.info(PID_graph)	

	print "AT STEP #4: Extracting K-core"
#	with ufora.remotely.downloadAll():
	k_core_graph = nx.k_core(PID_graph,k_val)
	print nx.info(k_core_graph)
	pickle.dump(graph,open("graph",'w'))
	
	print "DONE!"

def calculate_k_core(G, K):
    core_k = nx.k_core(G, k=K)
    nx.draw(core_k)
    plt.savefig("./images/kCore" + str(K) + ".png")
    if verbose:
        print "\r\nk-Core: " + str(K)
        print core_k.nodes()
        plt.show()
    write_csv_group('./data/results/kCore' + str(K) + '.csv', core_k.nodes())

def calculate_main_k_core(G):
    core_main = nx.k_core(G)
    nx.draw(core_main)
    plt.savefig("./images/kCoreMain.png")
    if verbose:
        print "\r\nk-Core: Main"
        print core_main.nodes()
        plt.show()
    write_csv_group('./data/results/mainKCore.csv', core_main.nodes())

def getKCore(undirectedGraph):
    pos = nx.spring_layout(undirectedGraph,k=0.15,iterations=20)
    nx.draw(undirectedGraph,pos,node_size=100,node_color = 'k')
    kCore = nx.k_core(undirectedGraph)
    kCore_edges = nx.edges(kCore)
    nx.draw_networkx_nodes(undirectedGraph,pos,nodelist=kCore,node_color='b',node_size = 100)    
    nx.draw_networkx_edges(undirectedGraph,pos,edgelist=kCore_edges,edge_color='b',width=3)
#    fig = plt.gcf()    
#    fig.set_size_inches((10, 10))
    plt.savefig('kcore.eps', format='eps', dpi=1000)
    plt.show()

 def find_k_cores(self, max_k):       
     current_graph = self.G
     if self.verbose:
         print 'K-CORES' 
     for i in range(max_k,0,-1):
         core_k = nx.k_core(current_graph, i)
         if len(core_k) > 0:
             self.k_cores.append(core_k.nodes())
             current_graph = nx.k_crust(current_graph, i)  
     if self.verbose:
         print 'Found %s k-cores' %(len(self.k_cores))
     return len(self.k_cores)

def detect_recover(filename,k):
    #Read Network files as gml file type, create a networkx graph and use the eisted graph file
	#Random graph may have poor performance, erdos renyi graph doesn't have true community structure
	G = nx.read_gml(filename)
	H = nx.k_core (G, int(k))
	#print len(H.nodes())
	#kcore_partition = kcore_partition(H)
	partition = community.best_partition(H)
	#print partition 
	sorted_recover_nodes = sort_by_neighbor(H, G)
	#print sorted_recover_nodes
	vote_for_node(partition, sorted_recover_nodes, G)
	new_partition = vote_for_node(partition, sorted_recover_nodes, G)
	return convert_partition_format(new_partition)

def getKCore(graph,worksheet):
    global name
    kCore = nx.k_core(graph)
    print 'KCore : '
    directory = "wordGraphs/top50/"+name
    directory = os.path.normpath(directory)
    if not os.path.exists(directory):
        os.makedirs(directory)    
    path = directory +"/KCore.png"
    fileName = os.path.normpath(path)
    nx.draw(kCore,node_size=100)
    plt.title(r'$\mathrm{K-Core\ for\ }' + name +'\ $',fontsize = 15)
    plt.savefig(fileName, format="PNG")
    plt.show()
    worksheet.insert_image(4,5,fileName, {'x_scale': 0.5, 'y_scale': 0.5})

def KCored(G):
	# Set k value
	k_values = []
	# k = 0.0
	nodes = G.nodes()
	for node in nodes:
		k_values.append(G.degree(node))
	k_values = sorted(k_values)
	k = k_values[len(k_values)/2]
	# print clusterFile, k
	# print min(k_values)
	# print max(k_values)	
	subG = nx.k_core(G, k=k) # Returns subgraph
	# print len(G.nodes()), '\t', len(subG.nodes())
	nx.write_weighted_edgelist(subG, outDirK + clusterFile, 'w')

def kcore_partition(k, FILE_PATH):
#Read Network files as gml file type, create a networkx graph and use the eisted graph file
#Random graph may have poor performance, erdos renyi graph doesn't have true community structure
	G = nx.read_gml(FILE_PATH)
	H = nx.k_core (G, k)
	partition = community.best_partition(H)
	communities = list(set(partition.values()))
	new_partition = {}
	for community_part in communities:
        	new_partition[community_part] = []
	#print new_partition
	for nodes in partition.keys():
        	new_partition[partition[nodes]].append(nodes)
	#print new_partition
	return new_partition
	'''

def SentimentAnalysis_RGO_Belief_Propagation(nxg):
	#Bayesian Pearl Belief Propagation is done by
	#assuming the senti scores as probabilities with positive
	#and negative signs and the Recursive Gloss Overlap
	#definition graph being the graphical model.
	#Sentiment as a belief potential is passed through 
	#the DFS tree of this graph.  
	dfs_positive_belief_propagated=1.0
	core_positive_belief_propagated=1.0
	dfs_negative_belief_propagated=1.0
	core_negative_belief_propagated=1.0
	core_xnegscore=core_xposscore=1.0
	dfs_knegscore=dfs_kposscore=dfs_vposscore=dfs_vnegscore=1.0
	sorted_core_nxg=sorted(nx.core_number(nxg).items(),key=operator.itemgetter(1), reverse=True)
	kcore_nxg=nx.k_core(nxg,6,nx.core_number(nxg))
	for x in sorted_core_nxg:
	      xsset = swn.senti_synsets(x[0])
	      if len(xsset) > 2:
	     		core_xnegscore = float(xsset[0].neg_score())*10.0
	      		core_xposscore = float(xsset[0].pos_score())*10.0
	      if core_xnegscore == 0.0:
			core_xnegscore = 1.0
	      if core_xposscore == 0.0:
			core_xposscore = 1.0
	      core_positive_belief_propagated *= float(core_xposscore)
	      core_negative_belief_propagated *= float(core_xnegscore)
	print "Core Number: RGO_sentiment_analysis_belief_propagation: %f, %f" % (float(core_positive_belief_propagated), float(core_negative_belief_propagated))
	#for k,v in nx.dfs_edges(nxg):
	for k,v in nx.dfs_edges(kcore_nxg):
	      ksynset = swn.senti_synsets(k)
	      vsynset = swn.senti_synsets(v)
	      if len(ksynset) > 2:
	     		dfs_knegscore = float(ksynset[0].neg_score())*10.0
	      		dfs_kposscore = float(ksynset[0].pos_score())*10.0
	      if len(vsynset) > 2:
			dfs_vnegscore = float(vsynset[0].neg_score())*10.0
			dfs_vposscore = float(vsynset[0].pos_score())*10.0
	      dfs_kposscore_vposscore = float(dfs_kposscore*dfs_vposscore)
	      dfs_knegscore_vnegscore = float(dfs_knegscore*dfs_vnegscore)
	      if dfs_kposscore_vposscore == 0.0:
		dfs_kposscore_vposscore = 1.0
	      if dfs_knegscore_vnegscore == 0.0:
		dfs_knegscore_vnegscore = 1.0
	      dfs_positive_belief_propagated *= float(dfs_kposscore_vposscore)
	      dfs_negative_belief_propagated *= float(dfs_knegscore_vnegscore)
	print "K-Core DFS: RGO_sentiment_analysis_belief_propagation: %f, %f" % (float(dfs_positive_belief_propagated),float(dfs_negative_belief_propagated))
	return (dfs_positive_belief_propagated, dfs_negative_belief_propagated, core_positive_belief_propagated, core_negative_belief_propagated)

def week4():
    path = "D:\Dropbox\PhD\My Work\Algorithms\@Machine Learning\Lectures\Social Network Analysis\Week 4_Community Structure\wikipedia.gml"
    wiki = nx.read_gml(path)
    wiki = wiki.to_undirected()
    
    # cliques
    cid, cls = max(nx.node_clique_number(wiki).iteritems(), key=operator.itemgetter(1))
    print 'clique', cid, ' size:', cls
    
    # k-cores
    kcs = nx.k_core(wiki)
    print 'k-core size:', len(kcs.node)
    
    # community 
    cs = list(nx.k_clique_communities(wiki, 2))
    ratio = (len(cs[0]) + 0.0) / len(wiki.node)
    print 'community ratio:', ratio

def core_topological_sort(vg_en_tn_prdct,threshold=1):
	invdistmerit=inverse_distance_intrinsic_merit(vg_en_tn_prdct)
	vg_en_tn_prdct_nxg=nx.DiGraph()
	rowframe=0
	columnframe=0
	for row in invdistmerit[0]:
		for column in row:
			print "column:",column
			if max(column) > threshold: 
				vg_en_tn_prdct_nxg.add_edge(rowframe, columnframe)	
			columnframe = columnframe + 1
		rowframe = rowframe + 1
	vg_en_tn_prdct_nxg.remove_edges_from(nx.selfloop_edges(vg_en_tn_prdct_nxg))
	video_core=nx.k_core(vg_en_tn_prdct_nxg.to_undirected())
	topsorted_video_core=nx.topological_sort(video_core)	
	print "Topological Sorted Core Summary of the Video - Edges:",topsorted_video_core
	return topsorted_video_core

    def rank(self,return_type='set'):
        entity = self.get_entity()
        
        graph = self.get_graph()
        if graph==None:
            graph = self.build_graph()

        sub_graphs = nx.connected_component_subgraphs(graph)

        result = set()
        
        result = set(nx.k_core(graph,k=3).nodes())
        
        if return_type == 'set':
            return result
        else:
            result = {ite:1 for ite in result}
            return result

def networkxOperations(graph):
    print "Computing in-Degree of the graph's nodes... \n "
    in_degree=nx.DiGraph.in_degree(graph)
    in_degree_sequence=sorted(in_degree.values(),reverse=True)
    plt.loglog(in_degree_sequence,'b-',marker='o', label="in-degree")
    print "Computing out-Degree of the graph's nodes... \n "
    out_degree=nx.DiGraph.out_degree(graph)
    out_degree_sequence=sorted(out_degree.values(),reverse=True)
    plt.loglog(out_degree_sequence,'b-',marker='*', label="out-degree")
    print "Computing Closeness of the graph's nodes... \n "
    closeness=nx.closeness_centrality(graph)
    closeness_sequence= sorted(closeness.values(),reverse=True)
    plt.loglog(closeness_sequence,'r-',marker='s', label="closeness")
    print "Computing Betweenness of the graph's nodes... \n "
    betweenness=nx.betweenness_centrality(graph)
    betweenness_sequence = sorted(betweenness.values(), reverse = True)
    plt.loglog(betweenness_sequence,'g-',marker='p', label="betweenness")    
    print "Computing Pagerank of the graph's nodes... \n "
    prank=nx.pagerank(graph, alpha=0.85)
    pagerank_sequence= sorted(prank.values(), reverse=True)
    plt.loglog(pagerank_sequence,'y-',marker='*', label="pagerank")
    print "Computing Clustering Coefficient of the graph..."
    cc=nx.clustering(graph.to_undirected())
    cc_sequence = sorted(cc.values(), reverse=True)
    plt.loglog(cc_sequence,'k-',marker='h', label="cc")
    print (sum(cc_sequence)*1.0)/len(graph), "\n"
    #plotting functions
    plt.title("Graph Properties Rank Plot")
    plt.ylabel("Properties")
    plt.xlabel("Rank")
    plt.legend(loc= 3, prop={"size": 8})
    plt.savefig(topic.replace(" ", "") +"_plot.png")
    plt.show()
    print "Computing Clusering coefficient of nodes... \n ", nx.clustering(graph.to_undirected(), nodes=[choice(graph.nodes()),choice(graph.nodes()),choice(graph.nodes())])
    print "Number of connected components: ", sum(1 for x in nx.connected_components(graph.to_undirected()))
    maxSubGraph = max(nx.connected_component_subgraphs(graph.to_undirected()), key=len)
    core = nx.k_core(maxSubGraph).nodes()
    print "k-core", core
    with open(topic.replace(" ", "")+"_results.csv", "w") as f:
        f.write("NODE"+","+"IN_DEGREE"+","+"OUT_DEGREE"+","+"CLOSENESS"+","+"BETWEENNESS"+","+"PAGERANK"+","+"CC \n")
        for node in graph.nodes():
            f.write(str(node)+","+str(in_degree[node])+","+str(out_degree[node])+","+str(closeness[node])+","+str(betweenness[node])+","+str(prank[node])+","+str(cc[node])+"\n")

	#Open the log file to write data
	wb = openpyxl.load_workbook(FILE_LOG_NAME)
	sheet = wb.get_sheet_by_name('Sheet1')
	

	Kcore_Value = int(sys.argv[2])
	sheet['A' + str(Kcore_Value + 3)] = Kcore_Value
	
	FILE_PATH = sys.argv[1]
	#start to read data from file 
	sheet['B' + str(Kcore_Value + 3)] = time.time()
	G = nx.read_edgelist(FILE_PATH)
	sheet['C' + str(Kcore_Value + 3)] = time.time()
	
	#perform kcore search
	H = nx.k_core (G, int(sys.argv[2]))
	if (not H.nodes()):
		sheet['J' + str(Kcore_Value + 3)] = "The community with K of value: " + sys.argv[2] + " is empty; execution stopped"
		sys.exit(0)
	#record time
	sheet['D' + str(Kcore_Value + 3)] = time.time()
	
	#perform partition on Kcore
	partition = community.best_partition(H)
	#record time
	sheet['E' + str(Kcore_Value + 3)] = time.time()
	
	
	sorted_recover_nodes = sort_by_neighbor(H, G)
	new_partition = vote_for_node(partition, sorted_recover_nodes, G)
	sheet['F' + str(Kcore_Value + 3)] = time.time()

 def test_main_core(self):
     main_core_subgraph = nx.k_core(self.H)
     assert_equal(sorted(main_core_subgraph.nodes()), [2, 4, 5, 6])

def kcores_cdf(graph):
    max_core_graph = nx.k_core(graph)
    print max_core_graph
    return

    print(">> Edges: {}".format(g.number_of_edges()))

if len(sys.argv) != 3:
    print("Error: Wrong number of arguments.")
    sys.exit(-1)

_, GRAPH_FILE, OUT_FILE = sys.argv

print("Opening {}...".format(GRAPH_FILE))
G = nx.read_gpickle(GRAPH_FILE)
print_graph_stats(G)

print("Computing k-cores...")
core_numbers = nx.core_number(G)
max_core = max(core_numbers.values())
max_core_communities = list(nx.connected_component_subgraphs(nx.k_core(G, k=max_core, core_number=core_numbers)))
print(">> max-core: {}".format(max_core))
four_cores_communities = list(nx.connected_component_subgraphs(nx.k_core(G, k=4, core_number=core_numbers)))
num_4_core = len(four_cores_communities)
print(">> num-4-cores: {}".format(num_4_core))

print("Computing modularities...")
print(">> max-core communities: {}".format(len(max_core_communities)))
modularity_max_core = cm.modularity(G, max_core_communities)
print(">> max-core modularity: {}".format(modularity_max_core))
print(">> 4-core communities: {}".format(len(four_cores_communities)))
modularity_four_core = cm.modularity(G, four_cores_communities)
print(">> 4-core modularity: {}".format(modularity_four_core))

print("Computing wcc...")
wcc_max_core = cm.wcc(max_core_communities[0], G)