Hamiltonian Path Python

PROGRAM TO SOLVE HAMILTONIAN CYCLE PROBLEM




class Graph():

    def __init__(self, vertices):

        self.graph = [[0 for column in range(vertices)]

                            for row in range(vertices)]

        self.V = vertices

 

    ''' Check if this vertex is an adjacent vertex

        of the previously added vertex and is not

        included in the path earlier '''

    def isSafe(self, v, pos, path):

        # Check if current vertex and last vertex

        # in path are adjacent

        if self.graph[ path[pos-1] ][v] == 0:

            return False

 

        # Check if current vertex not already in path

        for vertex in path:

            if vertex == v:

                return False

 

        return True

 

    # 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] ] == 1:

                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 range(1,self.V):

 

            if self.isSafe(v, pos, path) == True:

 

                path[pos] = v

 

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

                    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 True

 

    def printSolution(self, path):

        print ("Solution Exists: Following",

                 "is one Hamiltonian Cycle")

        for vertex in path:

            print (vertex, end = " ")

        print (path[0], "\n")

 

# Driver Code

 

''' Let us create the following graph

    (0)--(1)--(2)

    | / \ |

    | / \ |

    | /     \ |

    (3)-------(4) '''

g1 = Graph(5)

g1.graph = [ [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], ]

 

# Print the solution

g1.hamCycle();

 

''' Let us create the following graph

    (0)--(1)--(2)

    | / \ |

    | / \ |

    | /     \ |

    (3)     (4) '''

g2 = Graph(5)

g2.graph = [ [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], ]

 

# Print the solution

g2.hamCycle();







OUTPUT:

Solution Exists: Following is one Hamiltonian Cycle
 0  1  2  4  3  0

Solution does not exist

CREDITS: https://www.geeksforgeeks.org/hamiltonian-cycle-backtracking-6/