import networkx as nx
from math import cos,sin,pi,ceil
import random as rd

def measure_visibility(S,all_qclqs):
    "measure the min and average visibility of the quasi-cliques of all_qclqs with respect to S"
    
    def visibility(Q):
        "measure the visibility of Q with respect to S"
        
        maxi = 0
        
        for Q2 in S:
            vis_Q2_Q = len(set(Q2) & set(Q))/len(set(Q)) # definition of the visibility
            if vis_Q2_Q > 0.999:
                return 1
            elif vis_Q2_Q > maxi:
                maxi = vis_Q2_Q
        
        return maxi
    
    if len(all_qclqs) == 0:
        return 1,1
    
    min_vis = 1
    avg_vis = 0
    
    for Q in all_qclqs:
        vis_S_Q = visibility(Q)
        avg_vis += vis_S_Q
        min_vis = min(min_vis,vis_S_Q)
    
    return avg_vis/len(all_qclqs), min_vis
        

def load_graph(path2file):
    "load a graph from a .txt file, each line of the .txt file corresponds to an edge"
    
    G = nx.Graph()
    
    file = open(path2file,'r')
    
    line = file.readline().rstrip('\n\r')
    
    while line:
        l = line.split()
        u = int(l[0])
        v = int(l[1])
        
        G.add_edge(u,v)
        
        line = file.readline().rstrip('\n\r')
    
    file.close()

    return G

def random_subgraph(G,n,n_0):
    """ return H=(V',E') a random induced subgraph of G, H is generated according to the following rules:
            - n_0 first vertices are added to V'
            - add vertices from the neighbours of V' until |V'|=n
        rk : this function uses the random package, use rd.seed(new_seed) to modify the seed
    """
    
    V_prime = list(G.nodes)
    rd.shuffle(V_prime)
    V_prime = set(V_prime[:n_0])
    initials = V_prime.copy()
    
    candidates = set()
    for u in V_prime:
        candidates = candidates | set(G[u])
    
    candidates -= V_prime
    candidates = list(candidates)
    
    while len(V_prime)<n:
        if len(candidates)>0:
            i = rd.randrange(0,len(candidates))
            v = candidates[i]
        
        else:       # assuming here that V-V' is not the empty set
            l = list(set(G.nodes)-set(V_prime))
            i = rd.randrange(0,len(l))
            v = l[i]
        
        V_prime.add(v)
        neigh_v = set(G[v])-set(V_prime)-set(candidates)
        candidates = candidates + list(neigh_v)
        candidates.remove(v)
    
    H = G.subgraph(V_prime)
    H2 = nx.Graph()
    H2.add_nodes_from(H.nodes)
    H2.add_edges_from(H.edges)

    return H2,initials



def add_rd_edges(G, n_edges):
    "add n_edges new random edges to G"
    
    n = len(G.nodes)
    non_edges = [(j,i) for i in range(1,n) for j in range(i)]
    
    for (u,v) in G.edges:
        non_edges.remove((u,v))
    
    rd.shuffle(non_edges)
    
    G.add_edges_from(non_edges[:n_edges])



def rd_nodes_to_supernodes(G, min_supernode_size=10, max_supernode_size=10, proba_clique=1):
    "transforme les sommets d'un graphe en ensemble de sommets (cliques ou anticliques)"
    
    n = len(G.nodes)
    supernodes = []
    last_node = -1      # on a deja utilise tous les sommets de 0 a last_node
    
    for i in range(n):
        supernode_size = rd.randrange(min_supernode_size, max_supernode_size+1)
        supernodes.append([last_node+1+j for j in range(supernode_size)])
        last_node += supernode_size
    
    G2 = nx.Graph()
    G2.add_nodes_from(range(last_node+1))
    
    for i_U in range(1,n):
        SU = supernodes[i_U]
        for i_V in range(i_U):
            if G.has_edge(i_U,i_V):
                SV = supernodes[i_V]
                G2.add_edges_from([(u,v) for u in SU for v in SV])
                
        if rd.random()<=proba_clique:
            G2.add_edges_from([(SU[i],SU[j]) for i in range(1,len(SU)) for j in range(i)])
    
    return G2,supernodes
            

def compare_graphe(G1,G2):
    "renvoie la taille de la difference symetrique des arretes de G1 et G2"
    diff = len(set(G1.edges)-set(G2.edges)) + len(set(G2.edges)-set(G1.edges))
    return diff


def position_affichage(G,list_comm):
    "calcule une position d'affichage pour les sommets d'un graphe de communautes"
    pos = {}
    
    distance = 30
    distance_au_centre = 10
    angle = 2*pi/len(list_comm)
    
    pas_encore_vu = set(G.nodes)
    
    for i,C in enumerate(list_comm):
        centre_x = distance*cos(i*angle)
        centre_y = distance*sin(i*angle)
        
        copy_pas_encore_vu = pas_encore_vu.copy()
        
        for u in (copy_pas_encore_vu & set(C)):
            pas_encore_vu.remove(u)
            x = (2*rd.random()-1)*distance_au_centre + centre_x
            y = (2*rd.random()-1)*distance_au_centre + centre_y
            pos[u]=(x,y)
    
    for u in pas_encore_vu:
        x = (2*rd.random()-1)*distance_au_centre
        y = (2*rd.random()-1)*distance_au_centre
        pos[u] = (x,y)
        
    return pos

def barycentre(l):
    "calcule le barycentre d'une liste de points"
    if len(l)==0:
        return (0,0)
    
    S_x = 0
    S_y = 0
    
    for (x,y) in l:
        S_x += x
        S_y += y
    
    return (S_x/len(l), S_y/len(l))

def position_affichage2(G,list_comm):
    "calcule une position d'affichage pour les sommets d'un graphe de communautes"
    pos = {}
    
    distance = 50
    distance_au_centre = 10
    angle = 2*pi/len(list_comm)
    
    centres = [[] for i in range(len(G.nodes))]
    
    for i,C in enumerate(list_comm):
        centre_x = distance*cos(i*angle)
        centre_y = distance*sin(i*angle)
        
        for u in C:
            centres[u].append((centre_x,centre_y))
    
    for u in G.nodes:
        
        (x,y) = barycentre(centres[u])
        
        dx = (2*rd.random()-1)*distance_au_centre
        dy = (2*rd.random()-1)*distance_au_centre
        
        pos[u] = (x+dx,y+dy)
        
    return pos

def position_affichage3(list_comm):
    "calcule une position d'affichage pour les sommets d'un graphe de communautes"
    pos = {}
    
    distance = 50
    distance_au_centre = 10
    angle = 2*pi/len(list_comm)
    
    for i,C in enumerate(list_comm):
        centre_x = distance*cos(i*angle)
        centre_y = distance*sin(i*angle)
        
        angle_2 = 2*pi/len(C)
        
        for j,u in enumerate(C):
            dx = distance_au_centre*cos(j*angle_2)
            dy = distance_au_centre*sin(j*angle_2)    
            pos[u] = (centre_x+dx,centre_y+dy)
        
    return pos

def position_affichage4(list_comm, pos_centres):
    "calcule une position d'affichage pour les sommets d'un graphe de communautes"
    pos = {}

    distance_au_centre = 1
    
    for i,C in enumerate(list_comm):
        centre_x = pos_centres[i][0]
        centre_y = pos_centres[i][1]
        
        angle_2 = 2*pi/len(C)
        
        for j,u in enumerate(C):
            dx = distance_au_centre*cos(j*angle_2)
            dy = distance_au_centre*sin(j*angle_2)    
            pos[u] = (centre_x+dx,centre_y+dy)
        
    return pos

def node_in_comm(G,list_comm):
    dico = {}
    for i in range(len(list_comm)):
        C = list_comm[i]
        for u in C:
            dico[u] = i
    return dico

def non_edges_inside_comms(G,list_comm):
    missing_edges = []
    for C in list_comm:
        for i in range(1,len(C)):
            for j in range(i):
                u = C[i]
                v = C[j]
                #print(u,v,G[u])
                if not (v in G[u]):
                    missing_edges.append((u,v))
    return missing_edges

def edges_outside_comms(G,list_comm):
    edges = []
    node_comm = node_in_comm(G,list_comm)
    
    for (i,j) in G.edges:
        if node_comm[i] != node_comm[j]:
            edges.append((i,j))
    
    return edges
        
def calcule_gamma(G,X):
    gamma_deg = 1
    gamma_density = 0
    for u in X:
        gamma_u = len(set(X) & set(G[u]))/(len(X)-1)
        gamma_deg = min(gamma_deg, gamma_u)
        gamma_density += gamma_u
    gamma_density /= len(X)
    return gamma_deg, gamma_density

def est_deg_qclq(G,X,gamma):
    "verifie que X est une gamma deg-qclq de G"
    for u in X:
        if len(set(X) & set(G[u])) < gamma*(len(X)-1):
            return False
    return True

def est_density_qclq(G,X,gamma):
    "verifie que X est une gamma density-qclq de G"
    H = G.subgraph(X)
    return (2*len(H.edges)>gamma*len(X)*(len(X)-1))

def deleted_edges_in_comm(list_comm,edges_del):
    "renvoie les arretes supprimees lors de edge_reduction qui sont dans une communaute"
    l = []
    for (u,v) in edges_del:
        for X in list_comm:
            if (u in X) and (v in X):
                l.append((u,v))
    return l

def deleted_nodes_in_comm(list_comm,nodes_del):
    "renvoie les sommets supprimes lors de la reduction qui sont dans une communaute"
    l = set()
    nodes_del = set(nodes_del)
    
    for X in list_comm:
        l = l|(set(X) & nodes_del)
    
    return l

def reduction(G,gamma,min_size,edge_red=False):

    "delete the nodes (and edges) of G not contained in any quasi-cliques"    
    
    def edge_reduction():
        nb_deleted = 0
        list_edges = list(G.edges).copy()
        bound = ceil(2*gamma*(min_size-1))-min_size
        for (u,v) in list_edges:
            if len(set(G[u]) & set(G[v])) < bound:           # condition of the lemma
                G.remove_edge(u,v)
                nb_deleted += 1
                edges_deleted.append((u,v))
        
        return nb_deleted
    
    def node_reduction():
        nb_deleted = 0
        list_nodes = list(G.nodes).copy()
        for u in list_nodes:
            if len(G[u])< ceil(gamma*(min_size-1)):
                G.remove_node(u)
                nb_deleted += 1
                nodes_deleted.append(u)
        
        return nb_deleted
    
    flag_reduction = True
    
    while flag_reduction:
        nb_edges_deleted = 0
        if edge_red:
            nb_edges_deleted = edge_reduction()
        nb_nodes_deleted = node_reduction()
        flag_reduction = ((nb_edges_deleted+nb_nodes_deleted)>0)


def only_maximal(Quasi_Cliques):
    
    max_Quasi_Cliques = []
    # If C is not maximal then there is C' before C such that C c C'
    
    for C in Quasi_Cliques:
        
        is_maximal = True
        
        for max_C in max_Quasi_Cliques:
            if set(C).issubset(set(max_C)):
                is_maximal = False
                break
        
        if is_maximal:
            max_Quasi_Cliques.append(list(C))
    
    return max_Quasi_Cliques

def connected_components(G):
    "compute the connected components of G"
    
    n = len(G.nodes)
    nodes = list(G.nodes)
    
    colors = {}
    
    for i in range(n):
        u = nodes[i]
        colors[u] = i
    
    for i in range(n):
        for (u,v) in G.edges:
            coul = min(colors[u],colors[v])
            colors[u] = coul
            colors[v] = coul
    
    
    components = {}
    comp_color = []
    
    for u in G.nodes:
        if colors[u] in comp_color:
            components[colors[u]].append(u)
        else:
            comp_color.append(colors[u])
            components[colors[u]] = [u]
    
    return list(components.values())

edges_deleted = []
nodes_deleted = []