StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It looks to me that your backtracking is the problem. You greedily add nodes to your <code>hs</code> to build your path but you don't remove them when you fail to make a cycle/don't have any way to go.</p> <p>The first thing I would do is put <code>hs.remove(n)</code> before the final <code>return false</code>.Then I would also save the result of <code>isHamiltonian(start,nodes[i],hs)</code> and exit when it's true. Something like this </p> <pre><code>boolean result = isHamiltonian(start,nodes[i],hs); if(result)return true;` </code></pre> <p>That should fix up a lot. I do think that this exhaustive search will be quite slow.</p> <p><strong>EDIT</strong>: the whole thing should look like this:</p> <pre><code>private static boolean isHamiltonian(NodeI start, NodeI n, HashSet<NodeI> hs) { hs.add(n); NodeI[] nodes = n.getReachableNeighbours(); boolean connectedWithStart = false; for (int i = 0; i < nodes.length; i++) { if (nodes[i].compareTo(start) == 0) { connectedWithStart = true; break; } } if (hs.size() == n.getGraph().nodes().length && connectedWithStart) { return true; } for (int i = 0; i < nodes.length; i++) { if (!hs.contains(nodes[i])){ boolean result=isHamiltonian(start, nodes[i], hs); if(result)return true; } } hs.remove(n); return false; } </code></pre> <p>The problem itself is NP-hard so don't expect fast solutions for general graphs. Read up on <a href="http://en.wikipedia.org/wiki/Hamiltonian_path_problem#Algorithms" rel="nofollow">some basic algorithms</a> and decide if it's worth the time to implement for your application.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload