<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Encontro 02, Parte 2
Step1:  A seguir, vamos configurar as propriedades visuais
Step2:  Por fim, vamos carregar e visualizar um grafo
Step3:  Caminhos de comprimento mínimo
Seja $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ um caminho. Dizemos que
Step4:  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.
Step5:  Vamos agora escrever uma versão alternativa da busca em largura.
<ASSISTANT_TASK:>
Python Code:
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
<END_TASK>