Back to lab index

15-111
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 the x and y components are separated by white space.

For example, a park with four attraction might be described as follows:

```  9 8
12 30
2 15
4 2
```

where (9,8) represents attraction 0 and (4,2) represents attraction 3.

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.74
```

Neither 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( (x2-x1)2 + (y2-y1)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 AdjacencyList and your choice of your Heap or Java's PriorityQueue, you do not need to rewrite these. Although you should not need to change anything in your Heap, you are welcome to adapt it, as appropriate. The same is true of the AdjacencyList from last lab.

You probably want to create a Coordinate class 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 Edge class to make it Comparable so it can work with the PriorityQueue or Heap. If not, you can use Java's PriorityQueue and create an appropriate Comparator.

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 ArrayList with 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 KruskalMST class that contains exactly a static method that implements Kruskal's algorithm. If you go this route, you probably want it to take an AdjacencyList and return a list of Edges. 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:

1. Read in all of the points as Coordinates, likely placing them into some List, e.g. an ArrayList.
2. Find all Edges between the pairs of points, adding them into both the AdjacencyList and the Heap or PriorityQueue.
3. Create an instance of the UnionFind class, initialized for the correct number of verticies. This can be a local to whatever method is implementing the logic for Kruskal's algorithm.
4. Execute Kruskal's algorithm, which will find the edges representing the sidewalks and place them into some List, e.g. an ArrayList.
5. Traverse these edges, printing each edge and its length. While you are traversing, keep a running total of the length
6. 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.