In [ ]:
import sys
sys.path.append('..')
import socnet as sn
Configurando a biblioteca:
In [ ]:
sn.node_size = 3
sn.node_color = (0, 0, 0)
sn.edge_width = 1
sn.edge_color = (192, 192, 192)
Gerando um grafo completo:
In [ ]:
g = sn.generate_complete_graph(15)
sn.show_graph(g)
Esse será o grafo dos professores.
Atribuindo aleatoriamente tipos negativos e positivos às arestas:
In [ ]:
from random import random
def randomize_types(g):
for n, m in g.edges():
if random() < 0.5:
g.edges[n, m]['type'] = -1
else:
g.edges[n, m]['type'] = 1
randomize_types(g)
Essa distribuição uniforme modela de forma aproximada os julgamentos dos professores após o "retreat". Não vamos usar uma atribuição fixa de tipos, pois sua solução não pode ser "viciada". Ela deve ser adequada para qualquer atribuição aleatória próxima.
Convertendo tipos em cores para visualização:
In [ ]:
def convert_types_to_colors(g):
for n, m in g.edges():
if g.edges[n, m]['type'] == -1:
g.edges[n, m]['color'] = (255, 0, 0)
else:
g.edges[n, m]['color'] = (0, 0, 255)
convert_types_to_colors(g)
sn.show_graph(g)
Definindo uma atualização de tipo:
In [ ]:
from random import choice
# Essa função calcula a pressão que cada aresta sofre para mudar seu tipo,
# ou seja, a quantidade de situações de influência nas quais está envolvida.
# Se nenhuma aresta está sofrendo pressão, a função devolve False. Senão,
# uma aresta com maior pressão inverte seu tipo e a função devolve True.
#
# Os parâmetros a, b, c representam os pesos dos três tipos de pressão.
#
# a: peso da Situação A ("inimigo comum")
#
# b: peso da Situação B ("pacificador")
#
# c: peso da Situação C ("cizânia")
#
# Os valores padrão são 1. Já vimos em sala que eles levam a polarização.
def update_type(g, a=1, b=1, c=1):
# Inicializa as pressões.
for n, m in g.edges():
g.edges[n, m]['pressure'] = 0
# Para cada triângulo do grafo.
for n in g.nodes():
for m in g.nodes():
if n != m:
for l in g.nodes():
if n != l and m != l:
# Armazena em uma lista as três arestas do triângulo.
edges = [(n, m), (n, l), (m, l)]
# Conta quantas dessas arestas são positivas.
positives = 0
for e in edges:
if g.edges[e[0], e[1]]['type'] == 1:
positives += 1
# Se existem zero ou duas positivas, aumenta as pressões.
if positives == 0:
for e in edges:
g.edges[e[0], e[1]]['pressure'] += a # Situação A
if positives == 2:
for e in edges:
if g.edges[e[0], e[1]]['type'] == -1:
g.edges[e[0], e[1]]['pressure'] += b # Situação B
else:
g.edges[e[0], e[1]]['pressure'] += c # Situação C
# Obtém a maior pressão.
pressure = max([g.edges[n, m]['pressure'] for n, m in g.edges()])
# Se essa maior pressão for zero, devolve False.
if pressure == 0:
return False
# Senão, escolhe aleatoriamente uma aresta com maior pressão e inverte seu tipo.
n, m = choice([(n, m) for n, m in g.edges() if g.edges[n, m]['pressure'] == pressure])
g.edges[n, m]['type'] *= -1
return True
Você não precisa modificar update_type, apenas decidir quais valores de a, b e c devem ser passados.
Definindo um contador de componentes:
In [ ]:
from queue import Queue
# Não é obrigatório entender esse código, mas eu ficarei triste se
# você não perceber que é apenas uma sequência de buscas em largura!
def count_components(g):
for n in g.nodes():
g.node[n]['label'] = 0
label = 0
q = Queue()
for s in g.nodes():
if g.node[s]['label'] == 0:
label += 1
g.node[s]['label'] = label
q.put(s)
while not q.empty():
n = q.get()
for m in g.neighbors(n):
if g.node[m]['label'] == 0 and g.edges[n, m]['type'] == 1:
g.node[m]['label'] = label
q.put(m)
return label
Simulando várias vezes o processo no qual as arestas do grafo mudam de tipo até as pressões acabarem.
No final das simulações, o número médio de componentes é impresso.
Esse é o código que você deve modificar. Em particular, deve modificar as variáveis a, b e c.
In [ ]:
TIMES = 100
LIMIT = 100
a = 1 # Situação A
b = 1 # Situação B
c = 1 # Situação C
# Inicializa o número médio de componentes.
mean_components = 0
for _ in range(TIMES):
# Inicializa as arestas para uma nova simulação.
randomize_types(g)
# Inicializa o contador de iterações.
iterations = 0
# Continua enquanto alguma aresta sofre pressão.
while update_type(g, a=a, b=b, c=c):
iterations += 1
# Se passou de LIMIT iterações, provavelmente nunca vai terminar.
if iterations == LIMIT:
break
# Se uma das simulações não convergiu, desiste.
if iterations == LIMIT:
break
# Senão, atualiza o número médio de componentes.
mean_components += count_components(g)
if iterations == LIMIT:
print('uma das simulações não parecia estar convergindo')
else:
# Finaliza o número médio de componentes
mean_components /= TIMES
print('número médio de componentes:', mean_components)
Para ter insights sobre o que está acontecendo, não esqueça de examinar a versão animada da simulação!
In [ ]:
def snapshot(g, frames):
convert_types_to_colors(g)
frame = sn.generate_frame(g)
frames.append(frame)
frames = []
# Inicializa as arestas para uma nova simulação.
randomize_types(g)
# Inicializa aleatoriamente as posições dos nós.
sn.randomize_positions(g)
snapshot(g, frames)
iterations = 0
# Continua enquanto alguma aresta sofre pressão.
while update_type(g, a=a, b=b, c=c):
# Move um pouco os vértices de posição, usando o atributo 'type' das
# arestas como referência para saber o quanto dois vértices se atraem.
sn.update_positions(g, 'type')
snapshot(g, frames)
iterations += 1
# Se passou de LIMIT iterações, provavelmente nunca vai terminar.
if iterations == LIMIT:
print('a simulação não parecia estar convergindo')
break
sn.show_animation(frames)
ATENÇÃO: Segundo a primeira parte do enunciado, uma das configurações que você deve encontrar é a que leva a polarização. Essa não pode ser a configuração na qual os três pesos são iguais, pois já foi vista em sala. Não se preocupe, existem outras!