hamiltonian cycle Algorithm

The Hamiltonian Cycle Algorithm is a computational method used to determine whether a given graph contains a Hamiltonian cycle or not. A Hamiltonian cycle is a closed loop in a graph that visits each vertex exactly once and returns to the starting vertex. This problem is of great significance in various scientific and practical fields, such as network routing, circuit design, and traveling salesman problem (TSP). The Hamiltonian Cycle Algorithm is typically implemented using backtracking, depth-first search, or dynamic programming approaches. In the backtracking version of the Hamiltonian Cycle Algorithm, the process starts at an arbitrary vertex and explores the graph by recursively adding vertices to the cycle while ensuring that the current vertex is not already in the path. If a dead-end is encountered, meaning that there are no further vertices to explore that maintain the Hamiltonian cycle conditions, the algorithm backtracks to the previous vertex and tries another path. The algorithm continues this process until a valid Hamiltonian cycle is found or all possibilities have been exhausted. The Hamiltonian cycle problem is known to be NP-complete, which means that there is no known efficient algorithm that can solve it in polynomial time for all types of graphs. Due to its computational complexity, the Hamiltonian Cycle Algorithm is primarily suitable for small to moderately sized graphs.
"""
    A Hamiltonian cycle (Hamiltonian circuit) is a graph cycle
    through a graph that visits each node exactly once.
    Determining whether such paths and cycles exist in graphs
    is the 'Hamiltonian path problem', which is NP-complete.

    Wikipedia: https://en.wikipedia.org/wiki/Hamiltonian_path
"""
from typing import List


def valid_connection(
    graph: List[List[int]], next_ver: int, curr_ind: int, path: List[int]
) -> bool:
    """
    Checks whether it is possible to add next into path by validating 2 statements
    1. There should be path between current and next vertex
    2. Next vertex should not be in path
    If both validations succeeds we return true saying that it is possible to connect this vertices
    either we return false

    Case 1:Use exact graph as in main function, with initialized values
    >>> 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]]
    >>> path = [0, -1, -1, -1, -1, 0]
    >>> curr_ind = 1
    >>> next_ver = 1
    >>> valid_connection(graph, next_ver, curr_ind, path)
    True

    Case 2: Same graph, but trying to connect to node that is already in path
    >>> path = [0, 1, 2, 4, -1, 0]
    >>> curr_ind = 4
    >>> next_ver = 1
    >>> valid_connection(graph, next_ver, curr_ind, path)
    False
    """

    # 1. Validate that path exists between current and next vertices
    if graph[path[curr_ind - 1]][next_ver] == 0:
        return False

    # 2. Validate that next vertex is not already in path
    return not any(vertex == next_ver for vertex in path)


def util_hamilton_cycle(graph: List[List[int]], path: List[int], curr_ind: int) -> bool:
    """
    Pseudo-Code
    Base Case:
    1. Chceck if we visited all of vertices
        1.1 If last visited vertex has path to starting vertex return True either return False
    Recursive Step:
    2. Iterate over each vertex
        Check if next vertex is valid for transiting from current vertex
            2.1 Remember next vertex as next transition
            2.2 Do recursive call and check if going to this vertex solves problem
            2.3 if next vertex leads to solution return True
            2.4 else backtrack, delete remembered vertex

    Case 1: Use exact graph as in main function, with initialized values
    >>> 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]]
    >>> path = [0, -1, -1, -1, -1, 0]
    >>> curr_ind = 1
    >>> util_hamilton_cycle(graph, path, curr_ind)
    True
    >>> print(path)
    [0, 1, 2, 4, 3, 0]

    Case 2: Use exact graph as in previous case, but in the properties taken from middle of calculation
    >>> 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]]
    >>> path = [0, 1, 2, -1, -1, 0]
    >>> curr_ind = 3
    >>> util_hamilton_cycle(graph, path, curr_ind)
    True
    >>> print(path)
    [0, 1, 2, 4, 3, 0]
    """

    # Base Case
    if curr_ind == len(graph):
        # return whether path exists between current and starting vertices
        return graph[path[curr_ind - 1]][path[0]] == 1

    # Recursive Step
    for next in range(0, len(graph)):
        if valid_connection(graph, next, curr_ind, path):
            # Insert current vertex  into path as next transition
            path[curr_ind] = next
            # Validate created path
            if util_hamilton_cycle(graph, path, curr_ind + 1):
                return True
            # Backtrack
            path[curr_ind] = -1
    return False


def hamilton_cycle(graph: List[List[int]], start_index: int = 0) -> List[int]:
    r"""
    Wrapper function to call subroutine called util_hamilton_cycle,
    which will either return array of vertices indicating hamiltonian cycle
    or an empty list indicating that hamiltonian cycle was not found.
    Case 1:
    Following graph consists of 5 edges.
    If we look closely, we can see that there are multiple Hamiltonian cycles.
    For example one result is when we iterate like:
    (0)->(1)->(2)->(4)->(3)->(0)

    (0)---(1)---(2)
     |   /   \   |
     |  /     \  |
     | /       \ |
     |/         \|
    (3)---------(4)
    >>> 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]]
    >>> hamilton_cycle(graph)
    [0, 1, 2, 4, 3, 0]

    Case 2:
    Same Graph as it was in Case 1, changed starting index from default to 3

    (0)---(1)---(2)
     |   /   \   |
     |  /     \  |
     | /       \ |
     |/         \|
    (3)---------(4)
    >>> 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]]
    >>> hamilton_cycle(graph, 3)
    [3, 0, 1, 2, 4, 3]

    Case 3:
    Following Graph is exactly what it was before, but edge 3-4 is removed.
    Result is that there is no Hamiltonian Cycle anymore.

    (0)---(1)---(2)
     |   /   \   |
     |  /     \  |
     | /       \ |
     |/         \|
    (3)         (4)
    >>> 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]]
    >>> hamilton_cycle(graph,4)
    []
    """

    # Initialize path with -1, indicating that we have not visited them yet
    path = [-1] * (len(graph) + 1)
    # initialize start and end of path with starting index
    path[0] = path[-1] = start_index
    # evaluate and if we find answer return path either return empty array
    return path if util_hamilton_cycle(graph, path, 1) else []

LANGUAGE:

DARK MODE: