Finds a hamiltonian path using networkx graph library in Python with a backtrack solution

hamilton.py

import networkx as nx

def hamilton(G):
    F = [(G,[list(G.nodes())[0]])]
    n = G.number_of_nodes()
    while F:
        graph,path = F.pop()
        confs = []
        neighbors = (node for node in graph.neighbors(path[-1]) 
                     if node != path[-1]) #exclude self loops
        for neighbor in neighbors:
            conf_p = path[:]
            conf_p.append(neighbor)
            conf_g = nx.Graph(graph)
            conf_g.remove_node(path[-1])
            confs.append((conf_g,conf_p))
        for g,p in confs:
            if len(p)==n:
                return p
            else:
                F.append((g,p))
    return None

Hello ! Thank you very much for sharing this algorithm, I tried it with a (23, 23) adjacency matrix and it worked well. However, when I try to test this algorithm with a bigger adjacency matrix of a shape (41, 41) I can't get an output and I don't know if you have the same issue when using big adjacency matrix ? I don't know if it comes from the time complexity of the algorithm or if it's related to the networkx library ...

Hi @Quertsy I think (41,41) might be way too large to compute in reasonable time. The time complexity of this algorithm should be O(N!) in the worst case. I think you should be looking at other solvers that use heuristics if you're using such a large data set.