Skip to content

Instantly share code, notes, and snippets.

@mikkelam
Last active October 29, 2022 07:21
Show Gist options
  • Save mikkelam/ab7966e7ab1c441f947b to your computer and use it in GitHub Desktop.
Save mikkelam/ab7966e7ab1c441f947b to your computer and use it in GitHub Desktop.
Finds a hamiltonian path using networkx graph library in Python with a backtrack solution
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
@YaseenBU
Copy link

YaseenBU commented Feb 2, 2018

How can I implement it?

@juankafree
Copy link

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

@USM-F
Copy link

USM-F commented Feb 20, 2020

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)

@mikkelam
Copy link
Author

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

@c-93
Copy link

c-93 commented Jul 28, 2020

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.

@mikkelam
Copy link
Author

mikkelam commented Aug 13, 2020

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.

@Quertsy
Copy link

Quertsy commented Mar 29, 2022

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

@mikkelam
Copy link
Author

mikkelam commented Apr 4, 2022

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment