In [7]:
import sys
sys.path.append('..')
import socnet as sn
A seguir, vamos configurar as propriedades visuais:
In [8]:
sn.graph_width = 320
sn.graph_height = 180
Por fim, vamos carregar e visualizar um grafo:
In [9]:
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)
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$.
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.
In [10]:
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']))
No entanto, essa demonstração depende de certas hipóteses em relação ao grafo. Tenho uma má e uma boa notícia:
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).
In [48]:
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)
In [ ]: