Additional Information for Project 3
Errors and Typos: This lists any errors or typos that I have discovered (with the help of
- In the last line in Section 1 (Introduction) I say:
is a generalization of the problem of finding an open knight's tour.
The word "open" should not appear in the above line.
- There is a typo on Page 3 of the handout, in Section 3 (on testing
biconnectivity of graphs). In the characterization of cutpoints, item (ii)
if x is not the root A, then x is a cutpoint iff x has a child
y such that there is NO back edge from y or any descendent of y
to a proper ancestor of y.
Your Overall Approach:
I suggest the following steps (in this order) to completing your project:
Start with your solution to the Knight's Tour problem (Homework 3) and integrate it with
the graph class to produce the first version of the Hamiltonian cycle function.
At this stage, do not worry about any of the pruning heuristics mentioned in Section 2
of the Project handout.
Write a driver that reads a graph and tests the HamiltonianCycle function.
Your solution after this step should work correctly for small graphs.
Fine tune your implementation in any way you can. For example, in this step you might want to
get rid of graph templating and simplify your code by taking advantage of the fact that
nodes of the graph are labeled 1, 2,..., n.
Implement the function isConnected and use this to prune the search.
Test your function.
Implement the function degreeCheck and use this to prune the search.
Test your function.
Implement the function isBiconnected and use this to prune the search.
Test your function and try to run your function on the big graphs that I will
Add any heuristics you can think of to speed up your function.
My Timing Results:
- I started with Version 5 of the solution to Project 2 and added a hamiltonianCycle function
to it. I wrote a little driver to read graphs specified in the format of sg1 and
sg2 and then tested the hamiltonianCycle function on these graphs.
On sg1 the function returned immediately
and on sg2 the function took aabout 5-6 minutes.
Note that this was without any fine tuning of the graph class.