#!/usr/bin/env python
import networkx as nx
import math
import csv
import random as rand
import sys
_DEBUG_ = True
def main():
    graph_fn = "D:/00-SUNYSBU/00-Courses/2-2016SPRING/CSE523-Project/CODE/finalV2/WeightedEdgeBetweenessGraph.txt"
    G = nx.Graph()  #let's create the graph first
    #buildG(G, graph_fn, ',')
    ###########################################################################################################
    reader = csv.reader(open(graph_fn), delimiter=",")
    for line in reader:
        if len(line) > 2:
            if float(line[2]) != 0.0:
                #line format: u,v,w
                G.add_edge(int(line[0]),int(line[1]),weight=float(line[2]))
        else:
            #line format: u,v
            G.add_edge(int(line[0]),int(line[1]),weight=1.0)

    ############################################################################################################
    if _DEBUG_:
        print 'G nodes:', G.nodes()
        print 'G no of nodes:', G.number_of_nodes()
    
    n = G.number_of_nodes()    #|V|
    A = nx.adj_matrix(G)    #adjacenct matrix
    
   
    m_ = 0.0    #the weighted version for number of edges
    for i in range(0,n):
        for j in range(0,n):
            m_ += A[i,j]
    m_ = m_/2.0
    if _DEBUG_:
        print "m: %f" % m_

    #calculate the weighted degree for each node
    Orig_deg = {}
    #Orig_deg = UpdateDeg(A, G.nodes())
    ############################################################################################################
    nodes = G.nodes()
    deg_dict = {}
    n = len(nodes)  #len(A) ---> some ppl get issues when trying len() on sparse matrixes!
    B = A.sum(axis = 1)
    for i in range(n):
        deg_dict[nodes[i]] = B[i, 0]
    Orig_deg = deg_dict
    ############################################################################################################
    #run Newman alg
    #runGirvanNewman(G, Orig_deg, m_)
    #############################################################################################################
    #run GirvanNewman algorithm and find the best community split by maximizing modularity measure
    #let's find the best split of the graph
    BestQ = 0.0
    Q = 0.0
    while True:    
        #CmtyGirvanNewmanStep(G)
        ###############################################################
        
        if _DEBUG_:
            print "Calling CmtyGirvanNewmanStep"
        init_ncomp = nx.number_connected_components(G)    #no of components
        ncomp = init_ncomp
        while ncomp <= init_ncomp:
            bw = nx.edge_betweenness_centrality(G, weight='weight')    #edge betweenness for G
            #find the edge with max centrality
            max_ = max(bw.values())
            #find the edge with the highest centrality and remove all of them if there is more than one!
            for k, v in bw.iteritems():
                if float(v) == max_:
                    G.remove_edge(k[0],k[1])    #remove the central edge
            ncomp = nx.number_connected_components(G)    #recalculate the no of components

        
        ###############################################################
        #Q = _GirvanNewmanGetModularity(G, Orig_deg, m_);
        ##############################################################
        deg_ = Orig_deg
        New_A = nx.adj_matrix(G)
        New_deg = {}
        #New_deg = UpdateDeg(New_A, G.nodes())
        ###################################################
        nodes = G.nodes()
        deg_dict = {}
        n = len(nodes)  #len(A) ---> some ppl get issues when trying len() on sparse matrixes!
        B = New_A.sum(axis = 1)
        for i in range(n):
            deg_dict[nodes[i]] = B[i, 0]
        New_deg = deg_dict
        ###################################################
        #Let's compute the Q
        comps = nx.connected_components(G)    #list of components    
        print 'No of communities in decomposed G: %d' % nx.number_connected_components(G)
        Mod = 0    #Modularity of a given partitionning
        for c in comps:
            EWC = 0    #no of edges within a community
            RE = 0    #no of random edges
            for u in c:
                EWC += New_deg[u]
                RE += deg_[u]        #count the probability of a random edge
            Mod += ( float(EWC) - float(RE*RE)/float(2*m_) )
        Mod = Mod/float(2*m_)
        if _DEBUG_:
            print "Modularity: %f" % Mod
        Q = Mod

        
        ##############################################################
        print "Modularity of decomposed G: %f" % Q
        if Q > BestQ:
            BestQ = Q
            Bestcomps = nx.connected_components(G)    #Best Split
            print "Components:", Bestcomps
        if G.number_of_edges() == 0:
            break
    if BestQ > 0.0:
        print "Max modularity (Q): %f" % BestQ
        print "Graph communities:", Bestcomps
    else:
        print "Max modularity (Q): %f" % BestQ
    #############################################################################################################
    

if __name__ == "__main__":
    sys.exit(main())