Scribd
Upload
4 views3 pages

RGB Chips Isomorphism Analysis

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
4 views3 pages

RGB Chips Isomorphism Analysis

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

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 = [Link]()
for u in range(n):
if adj[v][u] and not visited[u]:
visited[u] = True
[Link](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 = [Link](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 = [Link]()
is_isomorphic = enhanced_color_refinement(adj1, adj2)
elapsed_time = [Link]() - 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()

Common questions

Powered by AI

Graph regularity is utilized in the isomorphism checking process by using it as a condition for specific optimizations. If both graphs are regular, meaning all vertices have the same degree, this property simplifies the isomorphism checking by making certain assumptions, like symmetry, which allow potentially reducing the permutation search space when graph size conditions are met (n <= 6, for example).

The enhanced color refinement method improves upon the naive isomorphism check by iteratively refining vertex colors based on the colors of neighboring vertices, thus capturing more structural information of the graph. This reduces the number of permutations needed to find an isomorphism as more structure is captured in each iteration, making it effective on larger graphs compared to the naive check applied for smaller graphs directly .

Color maps in the enhanced color refinement method function to assign a unique color to vertex and its connected structure (neighbors), effectively encoding vertex connectivity into discrete mappings. These mappings are iteratively refined and compared across both graphs, capturing increasingly nuanced structural equivalences, which assists in determining isomorphism by aligning structure-dictated color patterns between graphs .

The enhanced color refinement method fails when initial checks on vertex degree sums or connected components number do not match because these metrics are fundamental invariants of graph isomorphism. If the total degree sums differ, or the number of connected components is different, it indicates the graphs cannot be isomorphic as isomorphic graphs must preserve such structural properties .

The naïve isomorphism check is limited to graphs with eight or fewer vertices because its computational complexity grows factorially with the number of vertices due to permutation testing. For graphs larger than this, the potentially vast number of permutations becomes computationally expensive, thus the naive check becomes impractical for larger graphs .

Limitations of enhanced color refinement methods for larger graphs include possible failures in handling graphs with indistinguishable structure based on the coloring technique, particularly for highly symmetrical or complex graphs where multiple isomorphisms exist. For very large graphs, the method may still face scalability issues, as complex inter-node relationships could result in lengthy or insufficient distinguishing refinement cycles .

In cases where initial checks show potential for isomorphism, the procedure uses the enhanced color refinement technique to iteratively refine the correspondence based on progressively more sophisticated structural vertex-naming schemes. This iterative refinement contrasts pieces of graph structure until either an isomorphic mapping is found, or it becomes clear that no simple refinement achieves correspondence, thus eliminating false positives from initial checks .

The process optimizes computation time by leveraging initial checks that quickly discard non-isomorphic graphs through invariant properties such as vertex degree sums and component counts. For graphs passing these checks, efficient algorithms like color refinement reduce computational overhead by structuring their iterations around vertex connectivity patterns rather than exhaustive permutations, dramatically reducing the solution space needing exploration .

DFS is used to count connected components by iterating through each unvisited node, marking it as visited, and exploring all its connected nodes recursively. Each DFS initiation marks a new connected component, and the total number of initializations corresponds to the number of components in the graph. This method works because DFS can traverse all vertices in a component, ensuring each is visited once .

The primary methods for checking graph isomorphism described are the naive isomorphism check and the enhanced color refinement method. The naive isomorphism check is used when the number of vertices (n) is eight or less. The enhanced color refinement method is applied for graphs where n is nine or more and involves comparing sums of vertex degrees, sorting neighbors, and mapping colors through multiple iterations. It is used unless the initial checks on vertex degree sums, sorted degrees, and connected components number already show isomorphism is impossible .

You might also like