 hjacobs
/
laser-cut-templates
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 Raw Permalink Blame History

 `#!/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]:` ` 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` ``` ``` ` 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, "\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() ``` ``` ```