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
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=vertices1))


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()


