Caminos hamiltonianos

# Create the graph being used in the example
def setup_graph():
    r"""
    (0)--(1)--(2)
      \  / \  /
      (3)---(4)
    """
    v = 5
    edges = [(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2,4), (3, 4)]
    graph = [[] for _ in range(v)]
    for start, end in edges:
        graph[start].append(end)
        graph[end].append(start)
    return graph

# Check if the node is the solution by checking if the node is the first node in the solution and the length of the solution is equal to the length of the graph + 1
def is_solution(graph, sol, node):
    return node == sol[0] and len(sol) == len(graph) + 1

# Check if the node is feasible by checking if the node is not in the solution or if the node is the first node in the solution and the length of the solution is equal to the length of the graph
def is_feasible(node, sol, n):
    return node not in sol or (node == sol[0] and len(sol) == n)

# Find the number of Hamiltonian paths in the graph
def hamiltonian_paths(graph, node, sol, numSol):
    # Hamiltonian path found
    if is_solution(graph, sol, node):
        numSol += 1
    # Continue searching for Hamiltonian paths
    else:
        # Check all adjacent nodes
        for ady in graph[node]:
            # Check if the adjacent node is feasible (not in the solution or the first node in the solution and the length of the solution is equal to the length of the graph)
            if is_feasible(ady, sol, len(graph)):
                sol.append(ady) # Add the adjacent node to the solution
                numSol = hamiltonian_paths(graph, ady, sol, numSol) # Continue searching for Hamiltonian paths
                sol.pop() # Remove the adjacent node from the solution after searching for Hamiltonian paths
    
    return numSol

if __name__ == "__main__":
    graph = setup_graph()
    
    ini = 0
    sol = [ini]
    
    numSols = hamiltonian_paths(graph, ini, sol, 0)
    print(numSols)