<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 12
Step1:  Configurando a biblioteca
Step2:  Carregando o primeiro grafo
Step3:  Você pode usar esse grafo para depurar sua implementação do cálculo de edge betweenness.
Step4:  Carregando o segundo grafo
Step5:  Construindo uma animação do Girvan-Newman
<ASSISTANT_TASK:>
Python Code:
import sys
sys.path.append('..')
import socnet as sn
Explanation: Encontro 12: Algoritmo de Girvan-Newman
Importando a biblioteca:
End of explanation
sn.graph_width = 400
sn.graph_height = 225
sn.edge_width = 1
Explanation: Configurando a biblioteca:
End of explanation
g = sn.load_graph('teste.gml', has_pos=True)
sn.show_graph(g)
Explanation: Carregando o primeiro grafo:
End of explanation
def calculate_partial_betweenness(g, s):
    # Esta função deve calcular o betweenness parcial de cada aresta
    # e armazenar esse valor no campo `partial_betweenness` dela.
    # Betweenness parcial significa o valor do fluxo quando um nó
    # específico é a fonte. Nesta função, esse nó é o parâmetro s.
Explanation: Você pode usar esse grafo para depurar sua implementação do cálculo de edge betweenness.
End of explanation
sn.graph_width = 800
sn.graph_height = 450
g = sn.load_graph('karate.gml', has_pos=True)
sn.show_graph(g)
Explanation: Carregando o segundo grafo:
End of explanation
from random import randrange
from queue import Queue
def snapshot(g, frames):
    frame = sn.generate_frame(g)
    frames.append(frame)
frames = []
prev_num_components = 1
gc = g.copy()
snapshot(gc, frames)
while g.edges():
    # Identifica e remove a aresta com maior betweenness.
    for n, m in g.edges():
        g.edge[n][m]['betweenness'] = 0
    for n in g.nodes():
        calculate_partial_betweenness(g, n)
        for n, m in g.edges():
            g.edge[n][m]['betweenness'] += g.edge[n][m]['partial_betweenness']
    for n, m in g.edges():
        g.edge[n][m]['betweenness'] /= 2
    n, m = max(g.edges(), key=lambda e: g.edge[e[0]][e[1]]['betweenness'])
    g.remove_edge(n, m)
    gc.edge[n][m]['color'] = (255, 255, 255)
    # Calcula o número de componentes depois da remoção.
    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:
                        g.node[m]['label'] = label
                        q.put(m)
    num_components = label
    # Se o número de componentes aumentou, identifica as componentes por cores aleatórias.
    if prev_num_components < num_components:
        colors = {}
        for label in range(1, num_components + 1):
            colors[label] = (randrange(256), randrange(256), randrange(256))
        for n in gc.nodes():
            gc.node[n]['color'] = colors[g.node[n]['label']]
        prev_num_components = num_components
    snapshot(gc, frames)
sn.show_animation(frames)
Explanation: Construindo uma animação do Girvan-Newman:
End of explanation
<END_TASK>