-
Notifications
You must be signed in to change notification settings - Fork 0
/
tag_p1_202033202.py
186 lines (134 loc) · 7.76 KB
/
tag_p1_202033202.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
# Nome: Gabriel Mendes Ciriatico Guimarães
# Número de matrícula: 202033202
# Referências externas:
## A ideia da construção de grafo por lista de adjacências a partir de dicionário e sets foi vista em artigo da Programiz ("Adjacency List (With Code in C, C++, Java and Python)") (disponível em: https://www.programiz.com/dsa/graph-adjacency-list).
## A montagem do grafo como tipo abstrato de dados, no entanto, foi feita com base no conteúdo e na lista mostrados na aula 3 do curso.
## O pseudo código utilizado para implementar o algoritmo de Bron-Kerbosh sem pivotamento está aqui: https://iq.opengenus.org/bron-kerbosch-algorithm/ (OpenGenus IQ, "Using Bron Kerbosch algorithm to find maximal cliques in O(3^(N/3))")
## Dessa mesma fonte (OpenGenus IQ) também foi utilizado parte do código em Python. A diferença está no fato de que escolhi usar as operações de set para implementar o pseudo-código (inter, union, difference).
## Isso permitiu uma tradução mais simples e direta do pseudo-código para o código.
## A única parte funcional do código do OpenGenus IQ que foi mantida foi a parte de impressão dos cliques maximais e contagem de cliques maximais.
## Para o código do algoritmo com pivotamente, foi utilizado o artigo de Brito e Santos (2011) (disponível em: http://www.din.uem.br/sbpo/sbpo2011/pdf/87964.pdf).
## No artigo, os autores abordam as diferentes formas de escolha de pivô. Para o trabalho, escolhi o pivotamento por grau máximo de nó.
## O pseudo-código foi facilmente traduzido em código em Python a partir do código do algoritmo sem pivotamento.
class Graph:
# Grafo unidirecional e sem peso
def __init__(self):
# Estrutura escolhida é a lista de adjacências, implementada através de 1 dicionário que armazina sets
# Cada vértice é uma chave do dicionário, possuindo um set de adjacentes
self.graph = {}
def insert_edge(self, v1, v2):
# O código não trabalha com estrutura de nós, apenas de grafo, para poder usufruir da junção entre dicionário e sets
# Assim, para adicionar uma aresta precisa primeiro adicionar os vértices da aresta no dicionário
if v1 not in self.graph:
self.graph[v1] = set()
if v2 not in self.graph:
self.graph[v2] = set()
self.graph[v1].add(v2)
self.graph[v2].add(v1)
def edge_exists(self, v1, v2):
return v2 in self.graph[v1]
def get_nodes(self):
return set(self.graph.keys())
def adjacent_nodes(self, v):
return self.graph[v]
def remove_edge(self, v1, v2):
self.graph[v1] = self.graph[v1].difference(v2)
self.graph[v2] = self.graph[v2].difference(v1)
def print_graph(self):
# Imprimir o grafo como lista de adjacências
for n in self.graph.keys():
resultado = str(n) + ": "
resultado += " -> ".join(list(self.graph[n]))
print(resultado)
class Algorithms:
def bron_kerbosh(graph_a, r, p, x):
# Se os conjuntos de nós potenciais e de nós rejeitados estiverem vazios, então o conjunto r é um clique maximal
if ((len(p) == 0) or (p is None)) and (len(x) == 0):
print(str(len(r)) + " vértices: ", sorted(list(r)))
return 1
cliques_maximais = 0
# Para cada nó no conjunto de nós potenciais
for i in p:
new_p = p.intersection(graph_a[i])
new_r = r.union({i})
new_x = x.intersection(graph_a[i])
# O algoritmo é aplicado de forma recursiva, retornando a quantidade de cliques maximais encontrados
cliques_maximais += Algorithms.bron_kerbosh(graph_a, new_r, new_p, new_x)
# Nós testados podem ser removidos do conjunto de potenciais e colocados no conjunto de nós rejeitados
p = p.difference({i})
x = x.union({i})
return cliques_maximais
def biggest_degree_node(graph_a, p):
# Método que retorna o nó com maior grau em uma lista de adjacências
n_max = 0
for v in p:
if len(graph_a[v]) > n_max:
n_max = len(graph_a[v])
bnode = v
return bnode
def bron_kerbosh_with_pivot(graph_a, r, p, x):
if ((len(p) == 0) or (p is None)) and (len(x) == 0):
print(str(len(r)) + " vértices: ", sorted(list(r)))
return 1
cliques_maximais = 0
# As 2 próximas linhas são a única mudança significativa com o código do algoritmo sem pivotamento
# Na seguinte, escolhemos o pivô com maior grau em uma lista de adjacências (P U X)
pivot = Algorithms.biggest_degree_node(graph_a, p.union(x))
# Aqui, fazemos o loop para P \ N(pivot) ao invés de para P, reduzindo as recursões
for i in p.difference(graph_a[pivot]):
new_p = p.intersection(graph_a[i])
new_r = r.union({i})
new_x = x.intersection(graph_a[i])
cliques_maximais += Algorithms.bron_kerbosh_with_pivot(graph_a, new_r, new_p, new_x)
p = p.difference({i})
x = x.union({i})
return cliques_maximais
def nodes_with_mutual_friends(graph_a, node_a):
# Método que retorna a quantidade de nós que tem nós adjacentes em comum
comuns = 0
for vizinho in graph_a[node_a]:
comuns += len(graph_a[vizinho].intersection(graph_a[node_a]))
# Como as arestas são contadas 2 vezes, 1 em cada lista dos vértices de origem, sua contagem precisa ser dividida
return comuns/2
def local_clustering_coefficient(graph_a, node_a):
# Cálculo do coeficiente de aglomeração local, como visto em aula
k = len(graph_a[node_a])
# Se o nó tem apenas 1 vizinho, não é possível que os vizinhos desse nó sejam vizinhos entre si (um nó não pode ser vizinho de si mesmo)
if k <= 1:
return 0
n = Algorithms.nodes_with_mutual_friends(graph_a, node_a)
return (2*n)/(k*(k-1))
def average_clustering_coefficient(graph_a):
# O coeficiente de aglomeração médio é a média dos coeficientes locais de aglomeração
local_coefficients = 0
for node in graph_a.keys():
local = Algorithms.local_clustering_coefficient(graph_a, node)
local_coefficients += local
return local_coefficients/len(graph_a.keys())
def read_mtx_file(filename):
# Leitura do arquivo .mtx fornecido, retornando as arestas em formato de lista de listas
with open(filename) as f:
content = f.readlines()
content = [linha for linha in content if linha[0] != "%"]
content = content[1:]
content = [linha.strip("\n") for linha in content]
content = [linha.split(" ") for linha in content]
return content
def matrix_to_graph(M, G):
# Preenchimento de grafo a partir da lista de arestas lida a partir do arquivo .mtx
for edge in M:
G.insert_edge(int(edge[0]), int(edge[1]))
return G
p1 = read_mtx_file("soc-dolphins.mtx")
G = Graph()
G = matrix_to_graph(p1, G)
print("\nAplicando o algoritmo de Bron-Kerbosh, sem pivotamento:")
n_cliques_sem_pivot = Algorithms.bron_kerbosh(G.graph, set(), G.get_nodes(), set())
print("\n" + str(n_cliques_sem_pivot) + " cliques maximais encontrados.")
print("---------------------------------------")
print("\nAplicando o algoritmo de Bron-Kerbosh, com pivotamento:")
n_cliques_com_pivot = Algorithms.bron_kerbosh_with_pivot(G.graph, set(), G.get_nodes(), set())
print("\n" + str(n_cliques_com_pivot) + " cliques maximais encontrados.")
print("---------------------------------------")
acoef = Algorithms.average_clustering_coefficient(G.graph)
print("\nO coeficiente médio de aglomeração do grafo é: {0:.5}".format(acoef))