Lab 9 - Sidewalks and Minimum Spanning Trees

Due: Wednesday, April 15, 2009

**Overview**

The park service is concerned about the erosion occuring as the result of the wear created by foot traffic to and from attractions within parks. In order to protect the environment, they want to pave trails. They could, of course, simply pave the existing trails carved by use. But, this could require more pavement than necessary. And, what to say? They are flush with stimulus money and want to protect the employment of applied computer scientists. So, they hire you to write a program to find the shortest way to connect the landmarks together using a system of paved trails. And, since government bureauocrats like to seem technical and knowledgable, and have access to the Web, they have specified that you use Kruskal's algorithm.Your program takes the coordinates of the landmarks and determines the landmarks that should be directly connected to ensure that it is possible to move among the landmarks via sidewalk while using the least concrete. It produces a list of the landmarks to connect and the total length of all of the required sidewalks.

**The Input**

Each input file describes a single park, represented as a cartesion plane, e.g. a grid. The location of the landmarks are specified with(x, y)coordinates, each of which are non-negative, but not necessarily integers (e.g,they might contain decimal fractions). Each line contains one x-y pair, where thexandycomponents are separated by white space.For example, a park with four attraction might be described as follows:

9 8 12 30 2 15 4 2where

(9,8)represents attraction0and(4,2)represents attraction3.

**The Output**

The output should describe which attractions should be directly connected via sidewalks, the length of each sidewalk, and the total of the lengths of the sidewalks.The following is the output for the example above. Your solution should be similarly presented.

0-->2 9.90 3-->0 7.81 2-->1 18.03 35.74Neither the various legs of the sidewalks nor the points that compose them need to be specified in any particular order. Your answers need to contain at least two places of precision after the decimal -- but may contain more.

We are not concerned whether or not trailing zeros are shown, nor are we concerned whether or not the decimal point is shown if the digits to its right are all zeros. We are not concerned about the accuracy of rounding beyond +/- 0.1. In other words, there is no need to worry about number formatting or floating point rounding, unless you so choose. What the computer does naturally is A-Okay. particular order

**Interesting Observations**

- The shortest distance between any two points is a straight line, therefore only straight lines connecting attractions need be considered
- The distance between any two points can be computed as
SQRT( (x
_{2}-x_{1})^{2}+ (y_{2}-y_{1})^{2}) - You might find Math.sqrt(x) and Math pow(x,y) helpful
- You have already written a heap for a prior lab. You can reuse it here.
- Java has a
*PriorityQueue*class. You can use it here (Remember to import java.util.* or java.util.PriorityQueue). - The last lab included an
*AdjacencyList*class -- you are welcome to adapt/reuse it - You'll need to write your own input -- you might consider scanning whole lines and then tokenizing them, or scanning for each coordinate, noting that they come in pairs.
- Sidewalks can handle traffic in two directions.

**Overall Strategy**

Since you've already got an

AdjacencyListand your choice of yourHeapor Java'sPriorityQueue, you do not need to rewrite these. Although you should not need to change anything in yourHeap, you are welcome to adapt it, as appropriate. The same is true of theAdjacencyListfrom last lab.You probably want to create a

Coordinateclass that keeps track of the x- and y- components of a coordinate. It should probably implement a toString() to aid in printing.You'll probably want to modify the

Edgeclass to make itComparableso it can work with thePriorityQueueorHeap. If not, you can use Java'sPriorityQueueand create an appropriateComparator.You'll also want to create a data structure for union-find. You'll need this to detect cycles. Fundamentally, this is an array or

ArrayListwith two operations: union and find. Realistically speaking, you'll want to implement this as a separate class. You'll most likely want a constructor that is parameterized with the number of verticies and union and find operations that take a vertex number. These operations are straight-forward, but there is opportunity for error -- test very thoroughly. You are well-advised to test this class independent of the rest of this assignment to ensure that it works.If you want, you can create a

KruskalMSTclass that contains exactly a static method that implements Kruskal's algorithm. If you go this route, you probably want it to take anAdjacencyListand return a list ofEdges. For convenience, you can also implement this logic in your program's main class, if you so choose. This method isn't complicated, becuase you already have the heap and the cycle detection.Now we can see how the pieces fit together:

- Read in all of the points as
Coordinates, likely placing them into someList, e.g. anArrayList.- Find all
Edges between the pairs of points, adding them into both theAdjacencyListand theHeaporPriorityQueue.- Create an instance of the
UnionFindclass, initialized for the correct number of verticies. This can be a local to whatever method is implementing the logic for Kruskal's algorithm.- Execute Kruskal's algorithm, which will find the edges representing the sidewalks and place them into some
List, e.g. anArrayList.- Traverse these edges, printing each edge and its length. While you are traversing, keep a running total of the length
- Print out this running total.

**Testing**

Please create at least two interesting tests and turn them in. Toward the very end of the lab, the CAs might have mercy on you and offer you a test or two. But, these should just be confidence builders. At this stage of the game, creating good tests is part of the fun.