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

Can you write any exaple using it? Thanks. I`ve test it in Jupyter with Networkx and doesn't work.

try to add little fix: F = [(G,[list(G.nodes())[0]])]

How can I implement it?

example:

G = nx.Graph()
edges = [('B', 'C'), ('B', 'E'), ('C', 'D'), ('A', 'D'), ('D', 'J'), ('D', 'E'), ('E', 'F'), ('F', 'J'), ('J', 'A')]
G.add_edges_from(edges)
hamilton(G)

Thank you @USM-F, I updated the above solution to reflect your fix. I wrote this snippet 6 years ago for school. As far as I remember it worked, I suspect networkx updated their library sometime since then.

It works now with at least version 2.4

Thank you! Your algorithm fails, if at least one node has a self-loop.
Depending on your graph-type, you might want to add one of these solutions to remove the self-loops beforehand.

Thank you! Your algorithm fails, if at least one node has a self-loop.
Depending on your graph-type, you might want to add one of these solutions to remove the self-loops beforehand.

Hi @c-93, great find. I didn't want to update the original input G, so I simply filtered these self loops out. Funny thing is I believe i actually got full points for this solution back in school, even my professor didn't catch that :-)

One could argue that self loops should not be allowed though, alas, this is fine for now.

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 ...

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.