#Python代码

#coding=gbk

import numpy as  np

import networkx as nx

'''

输入参数格式说明

comm=[[1,2,3],[4,5,6],...]

G=nx.Graph()

Q1、Q2、Q3是采用三种不同方法来计算模块度，其结果相同

G中边(a,b)都是a<b,

如果查询(b,a) 是不是图的边，返回的结果为false（得到的返回结果是错的，这是个坑，要注意）

'''

def Q1(comm,G):

   #边的个数

   edges=G.edges()

   m=len(edges)

   #print 'm',m

   #每个节点的度

   du=G.degree()

   #print 'du',du

   #通过节点对（同一个社区内的节点对）计算

   ret=0.0

   for c in comm:

       for x in c:

           for y in c:

               #边都是前小后大的

               #不能交换x，y，因为都是循环变量

               if x<=y:

                   if (x,y) in edges:

                       aij=1.0

                   else:

                       aij=0.0

               else:

                   if (y,x) in edges:

                       aij=1.0

                   else:

                       aij=0

               #print x,' ',y,' ',aij

               tmp=aij-du[x]*du[y]*1.0/(2*m)

               #print du[x],' ',du[y]

               #print tmp

               ret=ret+tmp

               #print ret

               #print ' '

   ret=ret*1.0/(2*m)

   #print 'ret ',ret

   return ret

def Q2(comm,G):

   #边的个数

   edges=G.edges()

   m=len(edges)

   #print 'm',m

   #每个节点的度

   du=G.degree()

   #print 'du',du

   #通过节点对计算

   ret2=0.0

   for c in comm:

       #首先计算出社区c中的边的个数

       #这样计算出来的边数是实际边数的2倍

       bian=0

       for x in c:

           for y in c:

               #边都是前小后大的

               #不能交换x，y，因为都是循环变量

               if x<=y:

                   if (x,y) in edges:

                       bian=bian+1

               else:

                   if (y,x) in edges:

                       bian=bian+1

       #社区c内的节点度的和

       duHe=0

       for x in c:

           duHe=duHe+du[x]

       tmp=bian*1.0/(2*m)-(duHe*1.0/(2*m))*(duHe*1.0/(2*m))

       #print 'bian',bian,'tmp',tmp

       ret2=ret2+tmp

   return ret2

def Q3(comm,G):

   #社区个数

   k=len(comm)

   #边数

   m=G.number_of_edges()

   print 'm',m

   #边列表

   edges=G.edges()

   #k*k的矩阵e

   e=np.zeros((k,k),np.float)

   for i in range(k):

       for j in range(k):

           #计算comm[i]和comm[j]之间的边数

           #由于是对称矩阵，只需要计算上三角即可

           bian=0

           for x in comm[i]:

               for y in comm[j]:

                   if x<y:

                       if (x,y) in edges:

                           bian=bian+1

                   else:

                       if (y,x) in edges:

                           bian=bian+1

           #如果i==j，边重复了一遍，需要除以2

           if i==j:

               bian=bian/2

           #如果i==j，e[i,i]是边数/m

           if i==j:

               e[i,j]=bian*1.0/m

           else:#如果i!=j,e[i,j]是边数/m的一半

               e[i,j]=bian*0.5/m

           #e[i,j]=bian

       #endforj

   #endfori

   print e

   #1*k的行向量a

   a=np.zeros(k,np.float)

   for i in range(k):

       he=0

       for j in range(k):

           he=he+e[i,j]

       a[i]=he

   #

   print a

   QValue=0

   for i in range(k):

       QValue=QValue+e[i,i]-a[i]*a[i]

   #

   return QValue