To find a Hamiltonian circuit in a graph

[OrkoHunter]

I was wondering if there's a way to find if a graph whether directed or undirected has a Hamiltonian path or not i.e. a path visiting each vertex exactly once. For graphs with small number of nodes, it can be done easily, but it won't be easy for bigger graphs with more branches. I was thinking to implement a way to find the Hamiltonian circuit in such graphs.

Any suggestions?

[MridulS]

@OrkoHunter

networkx/networkx/algorithms/simple_paths.py

Line 11 in a822b49

def all_simple_paths(G, source, target, cutoff=None):

and

networkx/networkx/algorithms/tests/test_simple_paths.py

Line 40 in a822b49

def hamiltonian_path(G,source):

[OrkoHunter]

@MridulS Thanks for pointing that out. At least it is there already.
But I have no idea how can we use it.
And why is it under the tests?
There's no mention of it in the documentation either

[ysitu]

Implementing "a way" is easy. Implementing "a good way" is hard.

[OrkoHunter]

@ysitu So, I think a way exist here

networkx/networkx/algorithms/tests/test_simple_paths.py

Line 40 in a822b49

def hamiltonian_path(G,source):

But I can't figure out how can someone make use of it. It's under tests.

[MridulS]

@OrkoHunter You do realise that the hamiltonian path problem is a NP-Complete problem. As @ysitu pointed out it will be a hard to implement it in a "good way" .

[hagberg]

Closed due to inactivity.