from cfai.utils import *
import numpy as np


def compute_complex(L):
    '''
    计算edge/node
    :param L: 
    :return: 
    '''
    return np.diag(L).sum()/2/len(L)

def pickBest(queue,maxComplex,minNode):
    '''
    每次选择分割,选择 的 图 应该是 节点数最多的，
    
    但是进行选择的 图要满足一下条件：
    1.图足够复杂：complex>maxComplex
    2.图不能太小:num(node)>minNode
    
    
    如果这样的集合不是空，在这个集合中
    选择节点最大的那个图返回，进行分割
    
    否则返回none
    
    :param queue: 
    :return: 
    '''
    maxsofar=-1
    popindex=-1
    for i,(L,indexes), in enumerate(queue):
        cm=compute_complex(L)

        if cm <maxComplex or len(L)<=minNode:
            continue

        if len(indexes)>maxsofar:
            popindex=i
            maxsofar=len(indexes)

    if popindex>-1:
        return queue.pop(popindex)
    else:return None
def getPairCluster(L):

    def updateDiag(l):
        '''
        对子图进行修正
        :param l: 
        :return: 
        '''
        lsum=l.sum(axis=1)
        i1,i2=np.diag_indices_from(l)
        l[i1,i2]-=lsum
    S,V=eig(L)
    label=V[:,1]>0
    c1=np.where(label)[0]
    c2=np.where(1-label)[0]
    L1=L[c1][:,c1]
    L2=L[c2][:,c2]


    updateDiag(L1)
    updateDiag(L2)
    assert np.all(L1.sum(axis=1)==0)
    assert np.all(L2.sum(axis=1) == 0)
    return L1,L2,c1,c2

def clusterHelper(L,makK=16,minNode=5,complex=1.8):
    def initqueue(L):
        S,V=eig(L)
        disconnected=(S<1e-8).sum()
        if disconnected>1:
            labels=getCluster(disconnected,V)
            ret=[]
            for k in range(disconnected):
                ii=np.where(labels==k)[0]
                if len(ii)>0:
                    ret.append((L[ii][:,ii],ii))
            return ret
        
        else:
            return [(L,np.arange(len(L)))]
    N=len(L)
    queue=initqueue(L)
    initLen=len(queue)

    for k in range(makK-initLen):


        best=pickBest(queue,maxComplex=complex,minNode=minNode)
        if best is None:
            break
        L, sp=best

        cm=compute_complex(L)
        print('%d,分割的节点数:'%(k+initLen),len(L),'复杂度:',cm)
        if cm<complex:
            raise ValueError('should not happened')
            queue.append((L,sp))
            break

        if len(sp)<minNode:
            raise ValueError('should not happened')
            queue.append((L, sp))
            break

        L1,L2,c1,c2=getPairCluster(L)
        if len(c1)>0:
            queue.append((L1,sp[c1]))
        if len(c2)>0:
            queue.append((L2,sp[c2]))
    labels=np.zeros(N)-1

    for i,(_,lab) in enumerate(queue):
        labels[lab]=i
    return labels.astype(np.int32)
# import numpy as np
if __name__ == '__main__':
    # a=np.random.rand(10,10)
    # getPairCluster(a)
    G, Id2Index, Index2Id, _ = makeChengfGraph('mydata/15649923023463.json')
    L = LaplacianMatrix(graph2Matrix(G, norm=False))
    labels = clusterHelper(L,makK=25)

    # print(np.histogram(labels))
    print(np.unique(labels))