import sys
sys.path.append('..')

import socnet as sn

"""
Explanation: Encontro 05: Simulação de Centralidades
Importando a biblioteca:
End of explanation
"""


sn.node_size = 10
sn.edge_width = 1
sn.edge_color = (192, 192, 192)
sn.node_label_position = 'top center'

"""
Explanation: Configurando a biblioteca:
End of explanation
"""


g1 = sn.load_graph('renaissance.gml', has_pos=True)
g2 = sn.load_graph('../encontro02/1-introducao.gml', has_pos=True)

"""
Explanation: O objetivo desta atividade é realizar $24$ simulações de centralidade diferentes, para avaliar o desempenho de medidas clássicas em relação a diferentes processos de fluxo. Dessas $24$ simulações, são $12$ sobre o grafo g1 e $12$ sobre o grafo g2.
End of explanation
"""


sn.show_graph(g1, nlab=True)

"""
Explanation: O primeiro grafo corresponde aos casamentos entre famílias de Florença durante a Renascença.
J. F. Padgett, C. K. Ansell, 1993. Robust action and the rise of the Medici, 1400–1434. American Journal of
Sociology 98, págs. 1259-1319.
End of explanation
"""


sn.show_graph(g2, nlab=True)

"""
Explanation: O segundo grafo corresponde ao estudo de caso do primeiro encontro.
End of explanation
"""


from random import choice

TIMES = 1000

"""
Explanation: Das $12$ simulações sobre um dos grafos, são $6$ de closeness e $6$ de betweenness:

duplicação serial através de caminhos;
transferência através de caminhos;
duplicação serial através de trilhas;
transferência através de trilhas;
duplicação serial através de passeios;
transferência através de passeios.
End of explanation
"""


def simulate_closeness_transfer_geodesic(g):

    # Inicialização das médias.

    for n in g.nodes():
        g.node[n]['simulated_closeness'] = 0

    for _ in range(TIMES):
        for s in g.nodes():

            # Inicialização do closeness de s.
            g.node[s]['closeness'] = 0

            for t in g.nodes():
                if s != t:

                    # Função caixa-preta que calcula, para cada nó, seu subconjunto
                    # de vizinhos que pertencem a geodésicas de s a t. Esse subconjunto
                    # é armazenado no atributo shortest_neighbors. Vocês vão aprender
                    # a abrir essa caixa-preta em encontros posteriores.
                    sn.build_shortest_paths(g, s, t)

                    # Dependendo do processo, o fluxo pode não ter sucesso, ou seja,
                    # pode ficar preso em uma parte do grafo sem nunca atingir t.
                    # Quando isso acontece, simplesmente tenta-se novamente.

                    success = False

                    while not success:

                        # Chamamos de "dono" um nó que possui o bem conduzido pelo
                        # fluxo. No início do processo, sabemos que o único dono é s.
                        for n in g.nodes():
                            g.node[n]['owner'] = False
                        g.node[s]['owner'] = True

                        time = 1

                        while True:

                            # O conjunto nodes_reached indica os nós que o fluxo
                            # alcança ao "avançar mais um passo".
                            nodes_reached = set()

                            for n in g.nodes():
                                if g.node[n]['owner']:

                                    # TRANSFERÊNCIA: Escolhemos aleatoriamente um dos vizinhos válidos.
                                    # GEODÉSICA: Os vizinhos válidos são os que pertencem a geodésicas.
                                    m = choice(g.node[n]['shortest_neighbors'])
                                    nodes_reached.add(m)

                                    # TRANSFERÊNCIA: O fluxo transfere o bem para os nós que o fluxo
                                    # alcança, portanto o nó deixa de ser dono. Nos processos baseados
                                    # em duplicação, a linha abaixo não pode ser executada.
                                    g.node[n]['owner'] = False

                            # Todos os nós que o fluxo alcança tornam-se donos.
                            for n in nodes_reached:
                                g.node[n]['owner'] = True

                            # Se alcançamos t, interrompemos o fluxo e paramos de tentar.
                            if t in nodes_reached:
                                success = True
                                break

                            # Se não alcançamos ninguém, interrompemos o fluxo e tentamos novamente.
                            if not nodes_reached:
                                break

                            time += 1

                    # Soma do tempo de s a t ao closeness de s.
                    g.node[s]['closeness'] += time

        # Incremento das médias.
        for n in g.nodes():
            g.node[n]['simulated_closeness'] += g.node[n]['closeness']

    # Finalização das médias.
    for n in g.nodes():
        g.node[n]['simulated_closeness'] /= TIMES

"""
Explanation: Em uma simulação de closeness, para cada origem s e destino t, mede-se o tempo que o fluxo leva para chegar de s a t. O closeness simulado de um nó s é a soma de todos os tempos medidos quando esse nó é uma origem. Como o fluxo pode ter passos aleatórios, o processo é repetido TIMES vezes e considera-se a média.
A função abaixo calcula o closeness simulado em relação a transferência através de geodésicas.
End of explanation
"""


from math import inf, isinf
from queue import Queue

def build_closeness(g):
    for s in g.nodes():
        # início da busca em largura

        q = Queue()

        for n in g.nodes():
            g.node[n]['d'] = inf

        g.node[s]['d'] = 0
        q.put(s)

        while not q.empty():
            n = q.get()

            for m in g.neighbors(n):
                if isinf(g.node[m]['d']):
                    g.node[m]['d'] = g.node[n]['d'] + 1
                    q.put(m)

        # fim da busca em largura

        g.node[s]['theoretical_closeness'] = 0

        for n in g.nodes():
            g.node[s]['theoretical_closeness'] += g.node[n]['d']

"""
Explanation: Vamos comparar o closeness simulado com o closeness teórico.
Para calcular o segundo, basta usar o algoritmo de busca em largura que vimos em encontros anteriores.
End of explanation
"""


build_closeness(g1)

simulate_closeness_transfer_geodesic(g1)

for n in g1.nodes():
    print(g1.node[n]['label'], g1.node[n]['theoretical_closeness'], g1.node[n]['simulated_closeness'])

"""
Explanation: Comparação de closeness no grafo g1:
(vai demorar alguns segundos)
End of explanation
"""


build_closeness(g2)

simulate_closeness_transfer_geodesic(g2)

for n in g2.nodes():
    print(g2.node[n]['label'], g2.node[n]['theoretical_closeness'], g2.node[n]['simulated_closeness'])

"""
Explanation: Comparação de closeness no grafo g2:
(vai demorar alguns segundos)
End of explanation
"""


def simulate_betweenness_transfer_geodesic(g):

    # Inicialização das médias.

    for n in g.nodes():
        g.node[n]['simulated_betweenness'] = 0

    for _ in range(TIMES):

        # Inicialização de todos os betweenness.
        for n in g.nodes():
            g.node[n]['betweenness'] = 0

        for s in g.nodes():
            for t in g.nodes():
                if s != t:

                    # Função caixa-preta que calcula, para cada nó, seu subconjunto
                    # de vizinhos que pertencem a geodésicas de s a t. Esse subconjunto
                    # é armazenado no atributo shortest_neighbors. Vocês vão aprender
                    # a abrir essa caixa-preta em encontros posteriores.
                    sn.build_shortest_paths(g, s, t)

                    # Dependendo do processo, o fluxo pode não ter sucesso, ou seja,
                    # pode ficar preso em uma parte do grafo sem nunca atingir t.
                    # Quando isso acontece, simplesmente tenta-se novamente.

                    success = False

                    while not success:

                        # Chamamos de "dono" um nó que possui o bem conduzido pelo
                        # fluxo. No início do processo, sabemos que o único dono é s.
                        for n in g.nodes():
                            g.node[n]['owner'] = False
                        g.node[s]['owner'] = True

                        for n in g.nodes():
                            if n != s and n != t:
                                g.node[n]['partial_betweenness'] = 0

                        while True:

                            # O conjunto nodes_reached indica os nós que o fluxo
                            # alcança ao "avançar mais um passo".
                            nodes_reached = set()

                            for n in g.nodes():
                                if g.node[n]['owner']:

                                    # TRANSFERÊNCIA: Escolhemos aleatoriamente um dos vizinhos válidos.
                                    # GEODÉSICA: Os vizinhos válidos são os que pertencem a geodésicas.
                                    m = choice(g.node[n]['shortest_neighbors'])
                                    nodes_reached.add(m)

                                    # TRANSFERÊNCIA: O fluxo transfere o bem para os nós que o fluxo
                                    # alcança, portanto o nó deixa de ser dono. Nos processos baseados
                                    # em duplicação, a linha abaixo não pode ser executada.
                                    g.node[n]['owner'] = False

                            # Todos os nós que o fluxo alcança tornam-se donos.
                            for n in nodes_reached:
                                g.node[n]['owner'] = True

                            # Se alcançamos t, interrompemos o fluxo e paramos de tentar.
                            if t in nodes_reached:
                                success = True
                                break

                            # Se não alcançamos ninguém, interrompemos o fluxo e tentamos novamente.
                            if not nodes_reached:
                                break

                            for n in nodes_reached:
                                if n != s and n != t:
                                    g.node[n]['partial_betweenness'] += 1

                    # Soma de todos os betweenness parciais dos intermediários.
                    for n in g.nodes():
                        if n != s and n != t:
                            g.node[n]['betweenness'] += g.node[n]['partial_betweenness']

        # Incremento das médias. Divide-se o valor por 2 para
        # desconsiderar a simetria de um grafo não-dirigido.
        for n in g.nodes():
            g.node[n]['simulated_betweenness'] += g.node[n]['betweenness'] / 2

    # Finalização das médias.
    for n in g.nodes():
        g.node[n]['simulated_betweenness'] /= TIMES

"""
Explanation: Em uma simulação de betweenness, para cada origem s, destino t e intermediário n, mede-se a quantidade de vezes que o fluxo passa por n antes de chegar de s a t. O betweenness simulado de um nó n é a soma de todas as quantidades medidas quando esse nó é um intermediário. Como o fluxo pode ter passos aleatórios, o processo é repetido TIMES vezes e considera-se a média.
A função abaixo calcula o betweenness simulado em relação a transferência através de geodésicas.
End of explanation
"""


sn.build_betweenness(g1)

simulate_betweenness_transfer_geodesic(g1)

for n in g1.nodes():
    print(g1.node[n]['label'], g1.node[n]['theoretical_betweenness'], g1.node[n]['simulated_betweenness'])

"""
Explanation: Vamos comparar o betweenness simulado com o betweennesss teórico.
Para calcular o segundo, basta usar a função caixa-preta build_betweenness. Vocês vão aprender a abrir essa caixa-preta em encontros posteriores.
Comparação de betweenness no grafo g1:
(vai demorar alguns segundos)
End of explanation
"""


sn.build_betweenness(g2)

simulate_betweenness_transfer_geodesic(g2)

for n in g2.nodes():
    print(g2.node[n]['label'], g2.node[n]['theoretical_betweenness'], g2.node[n]['simulated_betweenness'])

"""
Explanation: Comparação de betweenness no grafo g2:
(vai demorar alguns segundos)
End of explanation
"""


def simulate_closeness_serial_path(g):
    pass

def simulate_closeness_transfer_path(g):
    pass

def simulate_closeness_serial_trail(g):
    pass

def simulate_closeness_transfer_trail(g):
    pass

def simulate_closeness_serial_walk(g):
    pass

def simulate_closeness_transfer_walk(g):
    pass

def simulate_betweenness_serial_path(g):
    pass

def simulate_betweenness_transfer_path(g):
    pass

def simulate_betweenness_serial_trail(g):
    pass

def simulate_betweenness_transfer_trail(g):
    pass

def simulate_betweenness_serial_walk(g):
    pass

def simulate_betweenness_transfer_walk(g):
    pass

"""
Explanation: Entregáveis
Para quinta 24/8, você deve entregar todas as funções abaixo.
Funções auxiliares para evitar repetição de código são permitidas e encorajadas.
End of explanation
"""


