import easygraph as eg 

__all__ = [
    "ICC",
    "BICC",
    "AP_BICC"
]

def inverse_closeness_centrality(G,v):
    c_v=sum(eg.Dijkstra(G,v).values())/(len(G)-1)
    return c_v

def bounded_inverse_closeness_centrality(G,v,l):
    queue=[]
    queue.append(v)
    seen=set()
    seen.add(v)
    shortest_path=eg.Floyd(G)
    result=0
    while (len(queue)>0):
        vertex=queue.pop(0)
        if shortest_path[v][vertex]==l+1:
            break
        nodes=G.neighbors(node=vertex)
        for w in nodes:
            if w not in seen:
                queue.append(w)
                seen.add(w)
                result+=shortest_path[v][w]
    return result/(len(G)-1)      

def Modified_DFS(G,u,V,time,n):
    V[u]['color']='black'
    time+=1
    n-=1
    V[u]['discovered']=time
    V[u]['lowest']=time
    cc0=n
    V[u]['descendant']=0
    root=u
    for edge in G.edges:
        u, v = edge[:2]
        if V[u]['color']=='white':
            V[u]['color']='grey'
            V[v]['parent']=u
            V[u]['child']+=1
            V,time,n=Modified_DFS(G,v,V,time,n)
            V[u]['descendant']=V[u]['descendant']+V[v]['descendant']
            V[u]['lowest']=min(V[u]['lowest'],V[v]['lowest'])
            if V[v]['lowest']>=V[u]['discovered'] or root==u and V[u]['child']>1:
                V[u]['c']+=V[v]['descendant']*(n-V[v]['descendant']-1)
                cc0-=V[v]['descendant']
        elif v!=V[u]['parent']:
            V[u]['lowest']=min(V[u]['lowest'],V[v]['discovered'])
    V[u]['c']+=cc0*(n-cc0-1)
    return V,time,n

def approximate_inverse_closeness_centrality(G):
    V={}
    for i in G.nodes:
        V[i]={}
        V[i]['child']=0
        V[i]['color']='white'
        V[i]['c']=0
        V[i]['parent']=None
        V[i]['discovered']=0
        V[i]['lowest']=0
        V[i]['descendant']=0 
    time=0
    n=len(G)
    for u in G.nodes:
        if V[u]['color']=='white':
            V,time,n=Modified_DFS(G,u,V,time,n)
    return V

def ICC(G,k):
    """an efficient algorithm for structural hole spanners detection.

    Returns top k nodes as structural hole spanners,
    Algorithm 1 of [1]_

    Parameters
    ----------
    G : easygraph.Graph
        An unweighted and undirected graph.

    k : int
        top - k structural hole spanners

    Returns
    -------
    V : list
        The list of top-k structural hole spanners.
    
    Examples
    --------
    Returns the top k nodes as structural hole spanners, using **ICC**.

    >>> ICC(G,k=3)

    References
    ----------
    .. [1] https://dl.acm.org/doi/10.1145/2806416.2806431
    
    """
    Q=[]
    V=[]
    for v in G.nodes:
        i_c=inverse_closeness_centrality(G,v)
        if len(Q)<k:
            Q.append([v,i_c])
            continue
        MAX=0
        t=v
        for i in Q:  
            if MAX<i[1]:
                MAX=i[1]
                t=i[0]
        if i_c<MAX:
            Q.remove([t,MAX])
            Q.append([v,i_c])
    for i in Q:
        V.append(i[0])
    return V

def BICC(G,k,K,l):
    """an efficient algorithm for structural hole spanners detection.

    Returns top k nodes as structural hole spanners,
    Algorithm 2 of [1]_

    Parameters
    ----------
    G : easygraph.Graph
        An unweighted and undirected graph.

    k : int
        top - k structural hole spanners

    K : int
        the number of candidates K for the top-k hole spanners

    l : int 
        level-l neighbors of nodes

    Returns
    -------
    V : list
        The list of top-k structural hole spanners.
    
    Examples
    --------
    Returns the top k nodes as structural hole spanners, using **BICC**.

    >>> BICC(G,k=3,K=5,l=4)

    References
    ----------
    .. [1] https://dl.acm.org/doi/10.1145/2806416.2806431
    
    """
    H=[]
    V=[]
    for v in G.nodes:
        b_i_c=bounded_inverse_closeness_centrality(G,v,l)
        if len(H)<K:
            H.append([v,b_i_c])
            continue
        MIN=10000000
        t=v
        for i in H:
            if MIN>i[1]:
                MIN=i[1]
                t=i[0]
        if b_i_c>MIN:
            H.remove([t,MIN])
            H.append([v,b_i_c])
    for i in H:
        v=i[0]
        i_c=inverse_closeness_centrality(G,v)
        if len(V)<k:
            V.append([v,i_c])
            continue
        MAX=0
        t=v
        for i in V:
            if MAX<i[1]:
                MAX=i[1]
                t=i[0]
        if i_c<MAX:
            V.remove([t,MAX])
            V.append([v,i_c])
    VS=[]
    for i in V:
        VS.append(i[0])
    return VS

def AP_BICC(G,k,K,l):
    """an efficient algorithm for structural hole spanners detection.

    Returns top k nodes as structural hole spanners,
    Algorithm 3 of [1]_

    Parameters
    ----------
    G : easygraph.Graph
        An unweighted and undirected graph.

    k : int
        top - k structural hole spanners

    K : int
        the number of candidates K for the top-k hole spanners

    l : int 
        level-l neighbors of nodes

    Returns
    -------
    V : list
        The list of top-k structural hole spanners.
    
    Examples
    --------
    Returns the top k nodes as structural hole spanners, using **AP_BICC**.

    >>> AP_BICC(G,k=3,K=5,l=4)

    References
    ----------
    .. [1] https://dl.acm.org/doi/10.1145/2806416.2806431
    
    """
    V=[]
    T=[]
    A={}
    A=approximate_inverse_closeness_centrality(G)
    for v in A:
        if len(T)<k:
            T.append([v,A[v]['c']])
            continue
        MIN=10000000
        t=v
        for i in T:
            if MIN>i[1]:
                MIN=i[1]
                t=i[0]
        if A[v]['c']>MIN:
            T.remove([t,MIN])
            T.append([v,A[v]['c']])
    if len(T)<k:
        U={}
        for i in G.nodes:
            if i not in A:
                U.append(i)
        kk=k-len(T)
        Q=[]
        for v in U:
            b_i_c=bounded_inverse_closeness_centrality(G,v,l)
            if len(Q)<K:
                Q.append([v,b_i_c])   
            else:
                MIN=10000000
                t=v
                for i in Q:
                    if MIN>i[1]:
                        MIN=i[1]
                        t=i[0]
                if b_i_c>MIN:
                    Q.remove([t,MIN])
                    Q.append([v,b_i_c])    
    while len(T)!=k:
        MAX=0
        t=None
        for i in Q:
            if MAX<i[1]:
                MAX=i[1]
                t=i[0]
        T.append([t,A[t]['c']])
    for i in T:
        V.append(i[0])
    return V

if __name__ == '__main__':
    G = eg.datasets.get_graph_karateclub()
    print(ICC(G,3))
    print(BICC(G,3,5,3))
    print(AP_BICC(G,3,5,3))