127 lines
3.6 KiB
Python
127 lines
3.6 KiB
Python
import random
|
|
import time
|
|
import matplotlib.pyplot as plt
|
|
import sys
|
|
from typing import List
|
|
|
|
def generate_hamiltonian_graph(n, saturation_percent):
|
|
max_possible_edges = n * (n - 1) // 2
|
|
target_edges = max_possible_edges * saturation_percent // 100
|
|
|
|
# Working on sets, its just easier
|
|
graph = {i: set() for i in range(n)}
|
|
edge_count = 0
|
|
|
|
cycle = list(range(n))
|
|
random.shuffle(cycle)
|
|
for i in range(n):
|
|
u = cycle[i]
|
|
v = cycle[(i + 1) % n]
|
|
if v not in graph[u]:
|
|
graph[u].add(v)
|
|
graph[v].add(u)
|
|
edge_count += 1
|
|
|
|
possible_edges = {(i, j) for i in range(n) for j in range(i+1, n)}
|
|
used_edges = {(min(u, v), max(u, v)) for u in graph for v in graph[u]}
|
|
available_edges = list(possible_edges - used_edges)
|
|
random.shuffle(available_edges)
|
|
|
|
while edge_count < target_edges and available_edges:
|
|
u, v = available_edges.pop()
|
|
if v not in graph[u]:
|
|
graph[u].add(v)
|
|
graph[v].add(u)
|
|
edge_count += 1
|
|
|
|
return {k: list(v) for k, v in graph.items()}
|
|
|
|
def graphFromMatrix(matrix: List[List[int]]):
|
|
n = len(matrix)
|
|
graph = {i: [] for i in range(n)}
|
|
for i in range(n):
|
|
for j in range(n):
|
|
if matrix[i][j] == 1:
|
|
graph[i].append(j)
|
|
return graph
|
|
|
|
|
|
def find_all_hamiltonian_cycles(graph):
|
|
n = len(graph)
|
|
cycles = set()
|
|
|
|
def backtrack(path, visited):
|
|
if len(path) == n:
|
|
if path[0] in graph[path[-1]]:
|
|
# We have to normalize the cycle to avoid duplicates
|
|
cycle = tuple(path)
|
|
rev_cycle = tuple(reversed(path))
|
|
canonical = min(cycle, rev_cycle)
|
|
|
|
min_idx = canonical.index(min(canonical))
|
|
normalized = canonical[min_idx:] + canonical[:min_idx]
|
|
cycles.add(normalized)
|
|
return
|
|
|
|
for neighbor in graph[path[-1]]:
|
|
if neighbor not in visited:
|
|
visited.add(neighbor)
|
|
path.append(neighbor)
|
|
backtrack(path, visited)
|
|
path.pop()
|
|
visited.remove(neighbor)
|
|
|
|
for start in range(n):
|
|
backtrack([start], {start})
|
|
|
|
return list(cycles)
|
|
|
|
if __name__ == "__main__":
|
|
if len(sys.argv) > 1:
|
|
file = sys.argv[1]
|
|
"""
|
|
Format we are expecting:
|
|
0 0 1 1 1 1
|
|
0 0 1 1 0 0
|
|
1 1 0 0 1 1
|
|
1 1 0 0 1 1
|
|
1 0 1 1 0 1
|
|
1 0 1 1 1 0
|
|
"""
|
|
with open(file, 'r') as f:
|
|
lines = f.readlines()
|
|
matrix = [list(map(int, line.strip().split())) for line in lines]
|
|
graph = graphFromMatrix(matrix)
|
|
|
|
cycles = find_all_hamiltonian_cycles(graph)
|
|
|
|
for cycle in cycles:
|
|
print(cycle)
|
|
exit(0)
|
|
|
|
n_values = range(5, 15)
|
|
saturation = 50
|
|
|
|
times = []
|
|
cycle_counts = []
|
|
|
|
for n in n_values:
|
|
graph = generate_hamiltonian_graph(n, saturation)
|
|
print(f"Running test for n={n}...")
|
|
start = time.time()
|
|
cycles = find_all_hamiltonian_cycles(graph)
|
|
elapsed = (time.time() - start) * 1000
|
|
times.append(elapsed)
|
|
cycle_counts.append(len(cycles))
|
|
print(f"Found {len(cycles)} cycles in {elapsed:.2f} ms")
|
|
|
|
plt.figure(figsize=(10, 6))
|
|
plt.plot(n_values, times, marker="o")
|
|
plt.xlabel("Liczba wierzchołków (n)")
|
|
plt.ylabel("Czas działania [ms]")
|
|
plt.title("Czas znajdowania wszystkich cykli Hamiltona dla nasycenia 50%")
|
|
plt.grid(True)
|
|
plt.tight_layout()
|
|
plt.yscale('log', base=2)
|
|
plt.savefig("hamilton.png")
|