[go: up one dir, main page]
Scribd
Upload
20 views3 pages

Code Ex3

The document contains a Python script that implements algorithms for checking the isomorphism of graphs using techniques like depth-first search and color refinement. It includes functions to determine if graphs are regular, count connected components, and perform naive isomorphism checks. The main function processes graph pairs from a file and prints the results of the isomorphism checks along with the CPU time taken.

Uploaded by

ryugfx2
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
20 views3 pages

Code Ex3

The document contains a Python script that implements algorithms for checking the isomorphism of graphs using techniques like depth-first search and color refinement. It includes functions to determine if graphs are regular, count connected components, and perform naive isomorphism checks. The main function processes graph pairs from a file and prints the results of the isomorphism checks along with the CPU time taken.

Uploaded by

ryugfx2
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

import time

from collections import defaultdict


from itertools import permutations
import random
import numpy as np
from matplotlib import pyplot as plt
import networkx as nx

def is_regular(graph):
degrees = [sum(row) for row in graph]
return len(set(degrees)) == 1

def count_components(adj):
"""Conta componentes conexos usando DFS"""
n = len(adj)
visited = [False] * n
components = 0

def dfs(node):
stack = [node]
while stack:
v = stack.pop()
for u in range(n):
if adj[v][u] and not visited[u]:
visited[u] = True
stack.append(u)

for i in range(n):
if not visited[i]:
visited[i] = True
dfs(i)
components += 1
return components

def naive_isomorphism_check(adj1, adj2, max_attempts=500):


n = len(adj1)
if n > 8:
return None

for _ in range(max_attempts):
perm = random.sample(range(n), n)
if all(adj1[i][j] == adj2[perm[i]][perm[j]] for i in range(n)
for j in range(n)):
return True
return False

def enhanced_color_refinement(adj1, adj2):


n = len(adj1)

if (sum(sum(row) for row in adj1) != sum(sum(row) for row in adj2))


or \
(sorted(sum(row) for row in adj1) != sorted(sum(row) for row in
adj2)) or \
(count_components(adj1) != count_components(adj2)):
return False

if n <= 8:
return naive_isomorphism_check(adj1, adj2)

if is_regular(adj1) and is_regular(adj2):


return naive_isomorphism_check(adj1, adj2) if n <= 6 else False

color1 = [sum(row) for row in adj1]


color2 = [sum(row) for row in adj2]

for _ in range(3 * n):


color_map = {}
new_color = 0

new_color1 = []
for v in range(n):
neighbors = tuple(sorted(color1[u] for u in range(n) if
adj1[v][u]))
key = (color1[v], neighbors)
if key not in color_map:
color_map[key] = new_color
new_color += 1
new_color1.append(color_map[key])

new_color2 = []
for v in range(n):
neighbors = tuple(sorted(color2[u] for u in range(n) if
adj2[v][u]))
key = (color2[v], neighbors)
if key not in color_map:
return False
new_color2.append(color_map[key])

if sorted(new_color1) != sorted(new_color2):
return False

if color1 == new_color1 and color2 == new_color2:


break

color1, color2 = new_color1, new_color2

return naive_isomorphism_check(adj1, adj2) if n <= 12 else False

def process_graph_pairs(graphs):
"""Processa todos os pares de grafos e imprime os resultados"""
if not graphs:
return

print("|V| +++/--- CPU time")


for idx, (n, adj1, adj2) in enumerate(graphs, 1):
start_time = time.time()
is_isomorphic = enhanced_color_refinement(adj1, adj2)
elapsed_time = time.time() - start_time

result = "+++" if is_isomorphic else "---"


print(f"{idx}) n = {n} {result} {elapsed_time:.6f}")

def main():
filename = "instancias_isomorfismo.txt"

graphs = read_graphs(filename)

if graphs:
process_graph_pairs(graphs)
else:
print("Nenhum grafo foi processado.")

if __name__ == "__main__":
main()

You might also like