2

I have been playing with Hamiltonian paths for some time and have found some cool uses of it. One being a sort of puzzle where the goal is to connect all the nodes to form a hamiltonian path.

So, being a novice programmer I am, I created a very basic brute force graph generator that creates graphs having a hamiltonian path. But the problem arises when I try to increase the graph size to 10x10. Needless to say, by brute force does not works there.

I understand Hamiltonian path is an NP-Complete problem, but is there a method to optimize the graph generation process. Any sort of trick that can create 15x15 grids in reasonable time.

Thank you very much.

Improve this question
8
  • So having a path (say, 3 -> 1 -> 2 -> 4) you want to create a graph (e.g. 3 -> 1, 1 -> 2, 2 -> 4, 3 -> 4, the last edge is not mandatory one)? If it is, why not take vertexes in arbitrary order (shuffle them), declare them to be on the path, create corresponding edges (path) and then add arbitrary edges (that are on on the path)? Commented Jan 20, 2017 at 10:19
  • Generating graphs that contain a Hamiltonian path is trivial and not at all related to the NP-Completeness of taking an arbitrary graph and determining whether or not it has a Hamiltonian path. Commented Jan 20, 2017 at 10:36
  • 1
    @harold: S/he presumably wants to generate a random-looking HP in a grid. If we drop either "random-looking" requirement or the "in a grid" requirement, yes, it's trivial, but with both in place I don't see an obvious algorithm. Commented Jan 20, 2017 at 14:16
  • I think this is a good question. I don't see the reason for close votes. It is not homework like question. Commented Jan 20, 2017 at 23:20
  • @j_random_hacker well it looks like you have a point but that whole grid thing means absolutely nothing to me. Commented Jan 21, 2017 at 9:53

1 Answer 1

Reset to default
3

You're looking for what's called the "Backbite algorithm" - start with any Hamiltonian path, a trivial one will do (zig-zag back and forth across your grid, or have a spiral).

Then loop a random number of times:

  1. Select either end point

  2. There are at least two and at most four neighboring vertices; randomly select one that is not already the Hamiltonian neighbor of the end point you started with

  3. If the second point was not the other endpoint

    a. connect the two points you picked - this will produce a graph that looks like a loop with a tail

    b. Find the edge that causes the loop (not the edge you just added, rather one of its neighbors), and delete it (this is the 'backbite' step)

  4. If in step 3 the second point was the other endpoint, join the two (you will now have a Hamiltonian cycle), and delete any other random edge

At each step, the new graph is still a Hamiltonian path.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

This may help as reference also: datagenetics.com/blog/december22018/index.html

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.