Emily's Hints for TSP

Only one class to write this week, Tour.java. Point.java and the client classes are already done for you.
Writing a Node toString() method will help you debug this.
You are using a very simple Node class to build your linked list of points. Refresh your memory of how linked lists work; here is a helpful page. Note: do not use the implementation of Node from the page; use the one on our assignment page.
Our linked list is singly linked and circular.
What instance variables do you need for Tour? I used two, but it could be done with one. What does Tour need to know? It needs to know where its linked list is stored, and it is useful if it knows how big it is (but not required, as you can compute this on the fly).
Where do you need to update your instance variables?

There are 2 this week. The one with no arguments is what will actually be used by the clients, the other is for debugging. Code these up first, because it helps you think about the data in a Node and how to link Nodes together into a list.

This a one-liner if you took my advice about the instance variables. Otherwise, you need to step through each node and count until you get back to the head of the list.

Now we get to practice traversing linked lists. The link I gave above will help you understand how to do this. Think about it like this: you are holding one end of a chain, and feeling your way down it link by link. There is no way to jump to another point on the chain; you need to inch along it passing each link on the way. We traverse nodes in a linked list in a similar way.
Write this method and test it by calling the constructor with 4 arguments, then show()ing what is inside.

There are two special cases here: if there is nothing in the list or if there is only one point in the list.
Otherwise, step through the nodes just like you do in show(), and use the distanceTo() method from Point.java to sum up the total distance. Don't forget that the salesman has to return to his starting point at the end of his tour! This is why we made the list circular!

This is going to look a lot like show() and distance(). For each sequence of two in the list, you can call the drawTo() method in Point.java. When testing this make sure your canvas is the right size for the points you are drawing. If you have a totally blank canvas that is probably the problem.

Here's the meat of this program. But this algorithm is deceptively simple. All you are doing is finding the Point in your list that is closest to your new Point, and inserting the new Point right after that closest one.
There is only special case: if the list is currently empty, then you just need to add the new Point.
Otherwise, you need to compute a minimum like you did in KMeans. Step through the list, and for each Point in it, compute the distance between your new point and the current point in the list. DON'T use distance() for this! Use Point.java's distanceTo() method. Keep track of which Node is closest to your new one.
Now for the fun part. How do you insert a Node into a linked list? It would help you to look at the figures on the link I gave up top.

This is a bit more complicated than insertNearest(), but not much! For this method, you are comparing your new Point with each sequential SET of points currently in the list. You need to compute the distance between these two original points, and subtract that value from the distance between the first original point and your new point plus the second original point and your new point.
There are two special cases here: when the list is empty, and when the list has only one Node in it.