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

import socnet as sn

"""
Explanation: Encontro 02, Parte 3: Algoritmo de Bellman-Ford
Este guia foi escrito para ajudar você a atingir os seguintes objetivos:

implementar o algoritmo de Bellman-Ford;
praticar o uso 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('3-bellman.gml', has_pos=True)

for n, m in g.edges():
    g.edge[n][m]['label'] = g.edge[n][m]['c']

sn.show_graph(g, elab=True)

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


from math import inf, isinf

s = 0

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

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

for i in range(g.number_of_nodes() - 1):
    for n, m in g.edges():
        d = g.node[n]['d'] + g.edge[n][m]['c']

        if g.node[m]['d'] > d:
            g.node[m]['d'] = d

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

"""
Explanation: Passeios de custo mínimo
O arquivo atribui c às arestas. Formalmente, esse atributo é uma função que mapeia pares de nós a reais:
$c \colon N \times N \rightarrow \mathbb{R}$.
O custo de um passeio $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ é
$\sum^{k-2}{i=0} c(n_i, n{i+1})$.
Um passeio de origem $s$ e destino $t$ tem custo mínimo se não existe outro passeio de origem $s$ e destino $t$ de custo menor. Note que podem existir múltiplos passeios de custo mínimo.
A distância ponderada de $s$ a $t$ é o custo mínimo de um passeio de origem $s$ e destino $t$. Por completude, dizemos que a distância ponderada de $s$ a $t$ é $\infty$ se não existe passeio de origem $s$ e destino $t$.
Algoritmo de Bellman-Ford
Dado um nó $s$, podemos eficientemente calcular as distâncias ponderadas desse a todos os outros nós do grafo usando o algoritmo de Bellman-Ford. A ideia desse algoritmo é diferente da ideia do algoritmo de busca em largura, mas também é simples: inicializamos a distância de $s$ como $0$, inicializamos a distância dos outros nós como $\infty$ e verificamos todas as arestas. Para cada aresta $(n, m)$, se a distância de $m$ for maior que a distância de $n$ mais o custo de $(n, m)$, essa soma passa a ser a nova distância de $m$.
É possível demonstrar matematicamente esse laço precisa ser repetido não mais que $|N|-1$ vezes, onde $|N|$ é a quantidade de nós.
End of explanation
"""


from math import inf, isinf
from queue import Queue

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)

    
red = (255, 0, 0)  
blue = (0, 0, 255) 
black = (0, 0, 0)
frames = []       

s = 0

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

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

sn.reset_node_colors(g) 
sn.reset_edge_colors(g)
snapshot(g, frames)

for i in range(g.number_of_nodes() - 1):
    for n, m in g.edges():
        d = g.node[n]['d'] + g.edge[n][m]['c']
        
        g.edge[n][m]['color'] = red 
#         snapshot(g, frames) 
        
        if g.node[m]['d'] > d:
            g.node[m]['d'] = d
            g.edge[n][m]['color'] = blue
        
        snapshot(g, frames)
        g.edge[n][m]['color'] = sn.edge_color

snapshot(g, frames)
sn.reset_edge_colors(g)

sn.show_animation(frames)

"""
Explanation: No entanto, essa demonstração depende de certas hipóteses em relação ao grafo. Tenho uma má e uma boa notícia:

a má é que existem grafos em que o algoritmo não funciona, ou seja, devolve uma resposta incorreta;
a boa é que, nos grafos em que ele funciona, os passeios de custo mínimo são caminhos de custo mínimo.

Exercício 1
Que grafos são esses?
Os gráficoso nos quais o algoritmo não funciona são os grafos fechados cujas arestas possuem apenas valores negativos. Isso acontece pois, nesse caso, o código ficaria em loop infinito ja que esse caminho seria sempre o menor de todos (o mais negativo). 
Exercício 2
Monte uma visualização do algoritmo de Bellman-Ford.
End of explanation
"""


