Some example templates as SVG for laser cutting
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

107 lines
3.0 KiB

#!/usr/bin/env python3
# Python program for solution of
# hamiltonian cycle problem
import random
import svgwrite
class Graph:
def __init__(self, vertices):
self.graph = [[False for column in range(vertices)] for row in range(vertices)]
self.random_vertex_candidates = list(random.sample(range(1, vertices), k=vertices-1))
print(self.random_vertex_candidates)
self.V = vertices
# A recursive utility function to solve
# hamiltonian cycle problem
def hamCycleUtil(self, path, pos):
# base case: if all vertices are
# included in the path
if pos == self.V:
# Last vertex must be adjacent to the
# first vertex in path to make a cyle
if self.graph[path[pos - 1]][path[0]]:
return True
else:
return False
# Try different vertices as a next candidate
# in Hamiltonian Cycle. We don't try for 0 as
# we included 0 as starting point in hamCycle()
for v in self.random_vertex_candidates:
if not self.graph[path[pos - 1]][v]:
continue
# Check if current vertex not already in path
if v in path:
continue
path[pos] = v
if self.hamCycleUtil(path, pos + 1):
return True
# Remove current vertex if it doesn't
# lead to a solution
path[pos] = -1
return False
def hamCycle(self):
path = [-1] * self.V
""" Let us put vertex 0 as the first vertex
in the path. If there is a Hamiltonian Cycle,
then the path can be started from any point
of the cycle as the graph is undirected """
path[0] = 0
if self.hamCycleUtil(path, 1) == False:
print("Solution does not exist\n")
return False
self.printSolution(path)
return path
def printSolution(self, path):
print("Solution Exists: Following", "is one Hamiltonian Cycle")
for vertex in path:
print(vertex, end=" ")
print(path[0], "\n")
width = 8
height = 8
g1 = Graph(width * height)
for x in range(width):
for y in range(height):
n = y * width + x
for next_point in ((x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)):
x2, y2 = next_point
if x2 >= 0 and x2 < width and y2 >= 0 and y2 < height:
n2 = (y2 * width) + x2
g1.graph[n][n2] = True
g1.graph[n2][n] = True
# Print the solution
path = g1.hamCycle()
if path:
dwg = svgwrite.Drawing(
"test.svg", ("210mm", "297mm"), profile="tiny", viewBox="0 0 210 297"
)
d = []
for vertex in path:
y, x = divmod(vertex, width)
d.append(f"{x*2} {y*2}")
obj = dwg.path(
d="M " + " ".join(d) + "Z", stroke="black", stroke_width=0.2, fill="none"
)
dwg.add(obj)
dwg.save()