#?-*-?coding:?UTF-8?-*-
import?networkx?as?nx
import?time


def?calculateQ（IN?TOT?m）:
????Q?=IN/m-（（TOT/（2*m））**2）
????return?Q



def?phases_one（G）:
????##用來存社區編號和其節點
????community_dict={}
????##用來存節點所對應的社區編號
????community_node_in_dict={}
????##用來保存邊兩頭節點所在社區
????edge_dict={}
????##存Tot和In
????Tot={}
????In={}

????##初始化上述指標
????for?node?in?G.nodes（）:
????????community_dict[node]=[node]
????????community_node_in_dict[node]=node
????????#初始化Tot
????????T=0.
????????for?nbrs?in?G.neighbors（node）:
????????????if?node==nbrs:
????????????????T?+=?（2*G.get_edge_data（nbrs?node）.values（）[0]）
????????????else:
????????????????T+=G.get_edge_data（nbrsnode）.values（）[0]
????????Tot[node]=T
????????#初始化In
????????if?G.get_edge_data（nodenode）==None:
????????????In[node]=0.
????????else:
????????????In[node]=G.get_edge_data（nodenode）.values（）[0]

????#初始化M
????M=0.0
????for?edge?in?G.edges（）:
????????M+=G.get_edge_data（*edge）.values（）[0]
????????edge_dict[（edge[0]edge[1]）]=（community_node_in_dict[edge[0]]community_node_in_dict[edge[1]]）
????index=True
????##一直遍歷直到收斂
????while?index==True:
????????index=False
????????##遍歷所有節點
????????for?node?in?G.nodes（）:
????????????##保存節點之前所在社區
????????????old_community=community_node_in_dict[node]
????????????#?用來保存節點node的總權值
????????????ki?=?0
????????????#?保存其所有鄰居社區
????????????nbrs_community={}
????????????#?保存該節點移動到某社區所帶來的In增益
????????????kiin_dict={}
????????????#?保存其離開自己所在社區的的In減少量
????????????kiout=0.
????????????#?目標社區
????????????max_community=-1
????????????max_detaQ=-1
????????????max_nbrs=-1
????????????#?臨時保存edge_dict變化
????????????edge_dict_tmp={}
????????????for?nbrs?in?G.neighbors（node）:
????????????????weight=G.get_edge_data（nodenbrs）.values（）[0]
????????????????if?nbrs==node:
????????????????????ki+=（2*weight）
????????????????else:
????????????????????ki+=weight
????????????????current_community=community_node_in_dict[nbrs]
????????????????if?current_community==old_community:
????????????????????kiout+=weight
????????????????????continue

????????????????if?nbrs_community.has_key（current_community）:
????????????????????kiin_dict[current_community]+=weight
????????????????else?:
????????????????????nbrs_community[current_community]=current_community
????????????????????kiin_dict[current_community]=weight
????????????????????if?G.has_edge（node?node）:
????????????????????????kiin_dict[current_community]?+=?G.get_edge_data（node?node）.values（）[0]
????????????#計算它離開自己社區的detaQ
????????????detaQ1=calculateQ（In[old_community]-kioutTot[old_community]-kiM）-calculateQ（In[old_community]Tot[old_community]M）
????????????#計算將要加入的社區的detaQ
????????????for?com?in?nbrs_community:
????????????????detaQ2=calculateQ（In[com]+kiin_dict[com]Tot[com]+kiM）-calculateQ（In[com]Tot[com]M）
????????????????Q=detaQ2+detaQ1
????????????????if?Q>max_detaQ?and?Q>0:
????????????????????max_detaQ=Q
????????????????????max_community=com