In [154]:
import sys
sys.path.append('..')
import socnet as sn
Configurando a biblioteca:
In [155]:
sn.graph_width = 360
sn.graph_height = 360
sn.node_size = 25
def load_graph(path):
g = sn.load_graph(path, has_pos=True)
for n, m in g.edges():
g.edge[n][m]['strong'] = bool(g.edge[n][m]['strong'])
return g
def set_colors(g):
for n, m in g.edges():
if g.edge[n][m]['strong']:
g.edge[n][m]['color'] = (0, 0, 0)
else:
g.edge[n][m]['color'] = (192, 192, 192)
def show_graph(g):
set_colors(g)
sn.show_graph(g, nlab=True)
O objetivo desta atividade é escrever uma simulação animada de negociações e executá-la sobre seis grafos diferentes.
Primeiro grafo:
In [156]:
g1 = load_graph('power-1.gml')
show_graph(g1)
Segundo grafo:
In [157]:
g2 = load_graph('power-2.gml')
show_graph(g2)
Terceiro grafo:
In [158]:
g3 = load_graph('power-3.gml')
show_graph(g3)
Quarto grafo:
In [159]:
g4 = load_graph('power-4.gml')
show_graph(g4)
Quinto grafo:
In [160]:
g5 = load_graph('power-5.gml')
show_graph(g5)
Sexto grafo:
In [161]:
g6 = load_graph('power-6.gml')
show_graph(g6)
A demanda de um nó é um inteiro de $1$ a $23$.
A oferta de um nó $n$ para um nó $m$ é 24 menos a demanda de $n$ (se a aresta $\{n, m\}$ é forte) ou 8 menos a demanda de $n$ (se a aresta $\{n, m\}$ não é forte). Note que essa definição permite que a oferta seja negativa.
Um vizinho $m$ de $n$ é aceitável se a oferta de $m$ para $n$ é máxima em relação aos vizinhos de $n$ e maior ou igual que a demanda de $n$. Note que a segunda condição implica que um nó pode não ter vizinhos aceitáveis.
Inicialize a demanda de cada nó como um inteiro aleatório de $1$ a $23$.
Para cada nó $n$, escolha aleatoriamente um (e apenas um) vizinho aceitável $m$. Defina que $n$ aceita $m$. Se não tem vizinhos aceitáveis, defina que não aceita ninguém.
Para cada aresta $\{n, m\}$, defina que $n$ e $m$ fecharam se $n$ aceita $m$ e $m$ aceita $n$.
Para cada nó $n$, incremente a demanda (se fechou e a demanda é menor que $23$) ou decremente a demanda (se não fechou e a demanda é maior que $1$).
Repita os passos de 2 a 4 até as demandas convergirem.
In [201]:
from random import randint, choice
# TIMES = 50
red = (255, 0, 0)
def offer(g, n, m):
if g.edge[n][m]['strong']:
return 24 - g.node[m]['demand']
return 8 - g.node[m]['demand']
def snapshot(g, frames):
for n in g.nodes():
g.node[n]['label'] = str(g.node[n]['demand'])
frame = sn.generate_frame(g, nlab=True)
frames.append(frame)
def simulate(g, TIMES):
frames = []
for n in g.nodes():
g.node[n]['demand'] = randint(1, 23)
snapshot(g, frames)
for _ in range(TIMES):
for n in g.nodes():
vizinhos_aceitaveis = []
vizinhos = g.neighbors(n)
for vizinho in vizinhos:
if g.edge[n][vizinho]['strong']:
if(g.node[n]['demand'] + g.node[vizinho]['demand'] <= 24):
vizinhos_aceitaveis.append(vizinho);
else:
if(g.node[n]['demand'] + g.node[vizinho]['demand'] <= 8):
vizinhos_aceitaveis.append(vizinho);
if(len(vizinhos_aceitaveis) > 0):
melhor_oferta = -1
vizinho_melhor_oferta = -1
for v in vizinhos_aceitaveis:
oferta = offer(g, n, v)
vizinho_oferta = v
if oferta > melhor_oferta:
melhor_oferta = oferta
vizinho_melhor_oferta = v
elif oferta == melhor_oferta:
vizinho_aleatorio = choice([vizinho_melhor_oferta, vizinho_oferta])
melhor_oferta == offer(g, n, vizinho_aleatorio)
vizinho_melhor_oferta = vizinho_aleatorio
g.node[n]['aceita'] = vizinho_melhor_oferta
else:
g.node[n]['aceita'] = 'null'
g.node[n]['incrementa'] = False
for n in g.nodes():
if(g.node[n]['aceita'] != 'null'):
a = g.node[n]['aceita']
if(g.node[a]['aceita'] == n):
# g.edge[n][a]['fecharam'] = True
g.node[n]['incrementa'] = True
g.edge[n][a]['color'] = red
else:
# g.edge[n][a]['fecharam'] = False
g.node[n]['incrementa'] = False
snapshot(g, frames)
for n in g.nodes():
if (g.node[n]['incrementa'] and g.node[n]['demand'] <= 23):
g.node[n]['demand'] += 1
elif(g.node[n]['demand'] >= 1):
g.node[n]['demand'] -= 1
snapshot(g, frames)
set_colors(g)
snapshot(g, frames)
sn.show_animation(frames)
In [202]:
TIMES = 100
simulate(g1,100)
In [205]:
simulate(g2, TIMES)
In [206]:
simulate(g3,TIMES)
In [214]:
TIMES = 80
simulate(g4,TIMES)
In [219]:
TIMES = 60
simulate(g5, TIMES)
In [223]:
TIMES = 45
simulate(g6,TIMES)
Na consolidação do módulo de centralidade, você pode atingir conceito avançado no objetivo traduzir conceitos sociológicos para teoria dos grafos e algoritmos em grafos se adicionar ao código da simulação um cálculo de lucro acumulado. Essa adição deve ser entregue na mesma data e deve incluir um comentário que explique como você distribui o lucro no caso em que a soma das demandas é menor que o dinheiro disponível.
Entender esse enunciado sozinho faz parte da entrega.
In [ ]: