Hamiltonian Cycle Algorithm and Concept

Overall this concept is quite like the n-queens problem and also why not, because this is also a Backtracking Problem, that is generally considered more difficult than it actually is. 

Now, Hamiltonian Path is just a path in an undirected graph in which every vertex is visited atleast once and Hamiltonian Cycle is a Hamiltonian Path such that there is an edge from the last vertex in the path to the first vertex in the path, 

or we can say that 

Hamiltonian Path is a round trip path in which every vertex is visited at least once  and Ham Cycle is a Ham Path such that the starting and the ending position in the Ham Path is same.

Both of the above statements evince the same thing and if you understand what is Hamiltonian Path well then this should be quite easy for you to understand and also make sure to get the concept well before going for the algo or the difficulty of the Algo will just barge in to you.

Now coming to the concept part of the idea of the Algo... basically we start everytime from the vertex 0 because if a Hamiltonian Cycle exists then it doesn't matter from which vertex we start so 0 for simplicity.

We are gonna put 0 in the path array firstly then call the main hamCycleUtil func for 1 vertex saying that if there is hamCycle for 1 vertex then return True else False, now we get inside the hamCycleUtil func..

so, hamCycleUtil func makes use of a Base condition which will be when we will reach the end of the vertices, means till n(cause vertices are from 0 to n-1) then we will just check our condition that we mentioned in the definition part of the Cycle that there should be a edge from the Last vertex(path[n-1]) in the Path to the First vertex(path[0]). If yes then return True else False, then we will be returning whatever is the result. 

Now what's the isSafe function right? This function just checks if the vertex we are considering currently in the for loop in the hamCycleUtil func is safe or not, obviously if we cannot go from vertex 0 to vertex 1 suppose then 1 is not safe. And also if suppose vertex 1 is already in the path then acc. to the definition(no vertex can be visited twice) it's not safe.

If the vertex being considered in the for loop is safe then just get inside another function call and try to get the next vertex in the Path, THIS IS THE MAIN AND MOST INTERESTING PART OF THE ALGO if there will be any problem in the future( like we get stuck somewhere or at the end we get to know that it was a safe yet a bad decision to have gone to the selected vertex then we just BACKTRACK to the previous vertex in the Path and try for some other vertex we do this until we find the correct path or we have run out of choices then we return False.

Test Graph are taken from a GFG article so you can confirm the output from there and also try to get the answer on your own by manually solving the graph.

That's it for this, algo is mentioned below ;)

''' Hamiltonian Cycle Algo - Python '''

'''

This algo is designed to show clearly what happens under the hood in the

Hamiltonian Cycle Problem's Algorithm

and also to simplify the backtracking concept by the help of print statements

'''

class Graph:

    def __init__(self,graph,size):

        self.graph=graph

        self.size=size

    def isSafe(self,vertex,path,n):

        # If this vertex cannot be visited from the last vertex in the

        # path that is path[n-1], then return false and also

        # if this vertex is already visited then also return false

        if(self.graph[path[n-1]][vertex]==0):

            return False

        if(vertex in path):

            return False

        # Else this vertex is safe to visit for now, note that it is not

        # clear that this is the correct choice

        # this may be proven to be a bad idea in future but then we would

        # backtrack( this is what makes this technique beautiful )

        return True

    def hamCycleUtil(self,path,n):

        # Base Condition

        if(n==self.size):

            if(self.graph[path[n-1]][path[0]]==0):

                return False

            else:

                print(f"""This is the last call and the ham cycle is found to

                           exist for sure, return True from here...""")

                return True

        # Will try each vertex( and will go in depth and if there would be a

        # problem then would backtrack

        # to the same vertex and then try with another different vertex )

        for vertex in range(self.size):

            if(self.isSafe(vertex,path,n)):

                path[n]=vertex

                print(f"Vertex {vertex} was safe...")

                if(self.hamCycleUtil(path,n+1)==True):

                    # print("Hamiltonian Cycle Found!!")

                    print(f"Returning True from vertex {vertex}")

                    # print(f"Path: {path}")

                    return True

                print(f"""Vertex {vertex} was found to be unsafe later... removing

                        it from path and backtracking...""")

                # Else this was a wrong way to go, and now we have backtracked

                # and now will neglect this vertex that we had choosen earlier

                # and will neglect this move by removing the vertex from the path

                path[n]=-1

        return False

       

    def hamCycle(self):

        path=[-1 for i in range(self.size)]

        # Will start the Hamiltonian cycle with the 0th vertex, cause we can start

        # with any vertex, it doesn't affect the end result

        path[0]=0

        if(self.hamCycleUtil(path,1)==False):

            print("No Hamiltonian Cycle found in the Graph!!")

            return False

        print("Hamiltonian Path:",path)

        return True

# For the below graph solution exists and the path should be --> [0,1,2,4,3]

graph1 = [ [0, 1, 0, 1, 0], [1, 0, 1, 1, 1],

            [0, 1, 0, 0, 1,],[1, 1, 0, 0, 1],

            [0, 1, 1, 1, 0], ]

# For the below graph solution doesn't exist

graph2 = [ [0, 1, 0, 1, 0], [1, 0, 1, 1, 1],

        [0, 1, 0, 0, 1,], [1, 1, 0, 0, 0],

        [0, 1, 1, 0, 0], ]

graph1=Graph(graph1,len(graph1))

graph2=Graph(graph2,len(graph2))

# graph1.hamCycle()

graph2.hamCycle()

print("Is this Safe?")