# https://www.geeksforgeeks.org/hamiltonian-path-cycle-in-python/ 

import time

class Graph(): 
    def __init__(self, vertices): 
        self.adjacency_matrix = [[0 for column in range(vertices)]
                                    for row in range(vertices)] 
        self.vertices_count = vertices 

    def is_safe_to_add(self, v, pos, path): 
        if self.adjacency_matrix[path[pos-1]][v] == 0: 
            return False

        for vertex in path: 
            if vertex == v: 
                return False

        return True

    def hamiltonian_cycle_util(self, path, pos): 
        if pos == self.vertices_count: 
            if self.adjacency_matrix[path[pos-1]][path[0]] == 1: 
                return True
            else: 
                return False

        for v in range(1, self.vertices_count): 
            if self.is_safe_to_add(v, pos, path): 
                path[pos] = v 

                if self.hamiltonian_cycle_util(path, pos+1): 
                    return True

                path[pos] = -1

        return False

    def find_hamiltonian_cycle(self): 
        path = [-1] * self.vertices_count 

        path[0] = 0

        if not self.hamiltonian_cycle_util(path, 1): 
            print ("No Hamilton circle")
            return False

        self.print_solution(path) 
        return True

    def print_solution(self, path): 
        print ("Hamilton circle:")
        for vertex in path: 
        #   print (vertex)
            print(vertex + 1)

n = int(input('Anzahl der Knoten random-Matrix: '))
print()

# Erzeugen einer n x n - Matrix mit lauter Nullen
a = [[0] * n for i in range(n)]

# Eingabe der Adjazenzmatrix
for i in range(n):
   for j in range(i+1,n):
      if j % 2 == 0: a[i][j] = 1
      else: a[i][j] = 0
      a[j][i] = a[i][j]


print()



# Example Dodekaeder
print('Dodekaeder')
g = Graph(20) 
g.adjacency_matrix = [[0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                      [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                      [0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
                      [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
                      [1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                      [0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
                      [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
                      [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                      [0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
                      [0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                      [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0],
                      [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0],
                      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
                      [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0],
                      [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
                      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1],
                      [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0],
                      [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
                      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
                      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0]]

for i in range(20): print(g.adjacency_matrix[i])
print()
start = time.time()
g.find_hamiltonian_cycle()
end   = time.time()
FindHamiltonianCycleTime = end - start
print('Zeitaufwand bei',20,'Knoten: {:7.3f} s'.format(FindHamiltonianCycleTime))
print()
print()

# example semi-hamilton
print('Graph G semi-hamiltonian')
g = Graph(5) 
g.adjacency_matrix = [[0, 1, 0, 1, 1],
                      [1, 0, 1, 0, 0],
                      [0, 1, 0, 1, 0],
                      [1, 0, 1, 0, 0],
                      [1, 0, 0, 0, 0]]
for i in range(5): print(g.adjacency_matrix[i])
print()
start = time.time()
g.find_hamiltonian_cycle()
end   = time.time()
FindHamiltonianCycleTime = end - start
print('Zeitaufwand bei',5,'Knoten: {:7.3f} s'.format(FindHamiltonianCycleTime))
print()
print()

# random graph
g = Graph(n)
g.adjacency_matrix = a
print('random-matrix:')
for i in range(n): print(g.adjacency_matrix[i])          
print()
start = time.time()
g.find_hamiltonian_cycle()
end   = time.time()
FindHamiltonianCycleTime = end - start
print('Zeitaufwand bei',n,'Knoten: {:7.3f} s'.format(FindHamiltonianCycleTime))
print()
print()