For this homework you edit TSP.java, as detailed below.

To run your program, you will need an environment where you can open
a graphics window (so either in the lab, or on your laptop, but not
via standard ssh, unless you know how to run a remote X server).  The
files here should work as a BlueJ project, if you like that tool, or
else just use "make" from the command line.  (In particular, that is
why we put book.jar into a subdirectory named +libs/.)

On the command line, you may invoke your program as follows:

   java -cp '.:+libs/*' TSP FILENAME D

Here FILENAME is the name of an input text file, like tsp100.txt (a
set of 100 points) and D is a small integer, like 10 or 15.
For some test examples from the command line, try:

    make run10
    make run100
    make run1000

For a complete list of make commands, try "make".

Or in BlueJ, try these static methods (predefined in TSP):
    run10(), run100(), run1000()

Your TSP.java program should do the following (first few steps
are already done for you):

1.  Read the input into an array of Point objects (points[]), and
    compute G = new GeomGraph(points, D).  That is the graph we get by
    including edges to the D closest neighbors of each vertex.

2.  Plot graph G in a StdDraw window, with edges in black (the default
    color).  Leave that window at its default size (512 by 512) and
    save a snapshot as "G.png" (a file in the current directory).

3.  Compute the MST in G (a list of edges). In the same StdDraw
    window, erase the image of G (StdDraw.clear()), plot the MST edges
    in RED.  Save a snapshot of that image as "MST.png".  Print just
    the weight of the MST to StdOut.  This should be the first line of
    output on System.out (or StdOut).  If you want other diagnostic
    output, send that to System.err.

4.  If, as a side-effect of computing the MST, you discover G is not
    connected (can happen if D is small), quit with: System.exit(1)

5.  Compute a TSP (a cyclic tour of the points), by doing a DFS on the
    MST, starting at 0.  That is, the tour should visit the vertices
    in the order they are discovered by the DFS.  The TSP may contain
    edges that are not part of the original G (their weight is just
    the point-to-point distance).  It should be cyclic, with an edge
    from its last vertex back to the first (0).   Print two lines of
    output to System.out (or StdOut):
         the sequence of vertices (starting with 0)
         the weight of the TSP (sum of edge lengths)
    For example (10 vertices, made up):
         0 2 8 5 3 1 6 7 4 9
         522.32412

6.  Clear the previous image, and plot the TSP edges in GREEN.
    Save the image as "TSP1.png".

7.  Improve your TSP by "2-opt" moves (see 2OPT.txt), until it
    cannot be improved any more.  Print out the tour and its weight
    again (two more lines of output, for five total).  Clear the image
    and draw these edges in BLUE.  Save it as "TSP2.png".

    To keep this step from being too time-consuming, it is enough for
    you to consider 2-opt moves you get by trying to add a new edge e
    from G, the geometric graph (with D closest neighbors of each
    point).  Keep trying, until you are sure that no edge from G
    creates an improving 2-opt move.  If D were large enough, then you
    would not see any crossing edges in TSP2.png.  But it is OK if you
    see just a few, since we are not trying all possible 2-opt moves.

8.  Do not wait for user input, just exit (closing the StdDraw window)
    with System.exit(0).


In summary, there should be five lines of System.out output:

MST weight
TSP1 weight
TSP1 sequence of vertex ids (probably starting with 0)
TSP2 weight
TSP2 sequence of vertex ids (starting with whatever)

Also, these four files should be created:

G.png
MST.png
TSP1.png
TSP2.png

For some example outputs, see:
    http://www.mathcs.emory.edu/~cs323000/share/0328/hw4-outputs/

If you do not do anything to make the GeomGraph construction faster,
then you probably cannot run the larger examples (like mona-20k.txt)
in reasonable time; this is OK.  But "make run1000" should take less
than a minute, even without special speedups.


EXTRA CREDIT: if you attempt either of these, you should email me a
detailed message of what you accomplished.

  EC#1: look for more TSP improvements than just 2-opt moves.  Let me
        know what you end up doing, and give some example where you
	get some better result than just 2-opt.   Include both timing
        and tour weight information.

  EC#2: speed up the GeomGraph(points, D) constructor, so it can
        handle larger point sets in a reasonable time (see the "TODO"
        suggestion in GeomGraph.java), but still computes the same
        Edge set. I won't see this though, unless you tell me that you
        did it.  Describe an example speed-up with your approach.


Remark: the various *.txt inputs are from princeton.edu and TSPLIB.