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:



In [1]:

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

import socnet as sn

A seguir, vamos configurar as propriedades visuais:



In [2]:

    
sn.graph_width = 320
sn.graph_height = 180

Por fim, vamos carregar e visualizar um grafo:



In [3]:

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

sn.show_graph(g)

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.



In [5]:

    
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']))









    



distância de 0: 1
distância de 1: 0
distância de 2: 2
distância de 3: 3
distância de 4: 2
distância de 5: 1
distância de 6: 2
distância de 7: 3

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.



In [6]:

    
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)

Vamos agora escrever uma versão alternativa da busca em largura.



In [7]:

    
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)

Ao longo da disciplina, usaremos as seguintes regras de escalabilidade:

visualizações animadas para depurar algoritmos em grafos pequenos;
visualizações estáticas para verificar resultados em grafos médios;
terminal para processar grafos grandes;
Fabio Ayres para processar megagrafos. (se houver oportunidade)