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

import socnet as sn

"""
Explanation: Encontro 02, Parte 2: Revisão de Busca em Largura
Este guia foi escrito para ajudar você a atingir os seguintes objetivos:

implementar o algoritmo de busca em largura;
usar funcionalidades avançadas da biblioteca da disciplina.

Primeiramente, vamos importar a biblioteca:
End of explanation
"""


sn.graph_width = 320
sn.graph_height = 180

"""
Explanation: A seguir, vamos configurar as propriedades visuais:
End of explanation
"""


g = sn.load_graph('2-largura.gml', has_pos=True)

sn.show_graph(g)

"""
Explanation: Por fim, vamos carregar e visualizar um grafo:
End of explanation
"""


from math import inf, isinf
from queue import Queue

s = 1
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)

for n in g.nodes():
    print('distância de {}: {}'.format(n, g.node[n]['d']))

"""
Explanation: Caminhos de comprimento mínimo
Seja $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ um caminho. Dizemos que:
* $n_0$ é a origem desse caminho, ou seja, o nó no qual ele começa;
* $n_{k-1}$ é o destino desse caminho, ou seja, o nó no qual ele termina;
* $k-1$ é o comprimento desse caminho, ou seja, a quantidade de arestas pelas quais ele passa.
Um caminho de origem $s$ e destino $t$ tem comprimento mínimo se não existe outro caminho de origem $s$ e destino $t$ de comprimento menor. Note que podem existir múltiplos caminhos de comprimento mínimo.
A distância de $s$ a $t$ é o comprimento mínimo de um caminho de origem $s$ e destino $t$. Por completude, dizemos que a distância de $s$ a $t$ é $\infty$ se não existe caminho de origem $s$ e destino $t$.
Algoritmo de busca em largura
Dado um nó $s$, podemos eficientemente calcular as distâncias desse a todos os outros nós do grafo usando o algoritmo de busca em largura. A ideia desse algoritmo é simples: a partir dos nós de distância $0$, ou seja apenas o próprio $s$, podemos descobrir os nós de distância $1$, a partir dos nós de distância $1$ podemos descobrir os nós de distância $2$, e assim em diante.
Podemos usar uma fila para garantir que os nós são visitados nessa ordem.
End of explanation
"""


def snapshot(g, frames):
    for n in g.nodes():
        if isinf(g.node[n]['d']):
            g.node[n]['label'] = '∞'
        else:
            g.node[n]['label'] = str(g.node[n]['d'])

    frame = sn.generate_frame(g, nlab=True)

    frames.append(frame)

"""
Explanation: Visualizando algoritmos
A função generate_frame é parecida com a função show_graph mas, em vez de mostrar uma imagem imediatamente, gera um quadro que pode ser usado para montar uma animação.
Vamos então definir uma função de conveniência que cria atributos label a partir de distâncias e adiciona um quadro a uma lista.
End of explanation
"""


red = (255, 0, 0)  # linha nova
blue = (0, 0, 255) # linha nova
frames = []        # linha nova

s = 1
q = Queue()

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

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

sn.reset_node_colors(g) # linha nova
sn.reset_edge_colors(g) # linha nova
snapshot(g, frames)     # linha nova

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

    g.node[n]['color'] = red # linha nova
    snapshot(g, frames)      # linha nova

    for m in g.neighbors(n):
        g.edge[n][m]['color'] = red # linha nova
        snapshot(g, frames)         # linha nova

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

        g.edge[n][m]['color'] = sn.edge_color # linha nova
        snapshot(g, frames)                   # linha nova

    g.node[n]['color'] = blue # linha nova
    snapshot(g, frames)       # linha nova

sn.show_animation(frames)

"""
Explanation: Vamos agora escrever uma versão alternativa da busca em largura.
End of explanation
"""


