CSC 225 Fall 2017: Assignment #5: Programming
Due by 11:55pm on Saturday Nov. 25.

Submission Instructions

Put your name in a comment at the top of WeightedEdgeList.java.
Upload WeightedEdgeList.java to connex (in the same place as the assignment is posted). You can change the file that you upload as many times as you want up until the submission deadline. Do not zip, tar, or otherwise compress your file before uploading it. Do not use packages.
Your program must be written in Java. All code must be nicely indented and thoroughly documented. Do not make your code overly complex.
You are not permitted to use any libraries besides those provided with the assignment to implement the data structures.
You will lose marks for not following the specifications precisely. It is important in an industrial setting to stick rigorously to specifications given to you. Also, the tasks are defined as they are to meet educational objectives.
Code that does not compile will be assigned a mark of 0.
If you allow a friend to copy your code or work together on code with another student then both you and the other student will receive a mark of 0 for the assignment. Students may discuss the algorithms and compare computational results but should not share any code with each other.
If your code is not as efficient as it could be (for example using THETA(n) time for an operation that can be done in THETA(1) time) then you will lose marks.

Learning objectives:

Writing the code requires an understanding of radix sort, the minimum weight spanning tree problem, and the union/find data structure.

Students will get additional practice in working with linked lists. For a linked list, it is critical to ensure that the number of items in the list is recorded correctly, the rear pointer is correct and the list is null terminated. You should rearrange the pointers for the nodes you already have. Do not make new nodes. It would be wise to write code for checkList in Test.java to make sure that your lists are correct.

Graphs for this assignment are stored using a WeightedEdgeList. The WeightedEdgeList has fields:

n= the number of vertices in the graph.
m= the number of edges in the edge list.
start= a pointer to the first node on the edge list.
rear= a pointer to the last node on the edge list.

The nodes of a WeightedEdgeList are of type WeightedEdgeNode. A WeightedEdgeNode has fields:

An integer array edge such that for an edge (u, v) of weight w:
edge[0]= w
edge[1]= u
edge[2]= v
When the data is read in, it is stored to maintain the property that u < v for all edges. An array is used instead of just w, u, v to make the sort easier to implement. Vertex numbers should be in the range [0, n-1]. The edge weights should be at least 1.
A pointer next that points to the next node on the list.

The two routines you should add to the code given are:

[50 marks] edgeSort: the object associated with the method is a WeightedEdgeList. Rearrange the pointers so that the list is sorted in increasing order. Each edge (u,v) of weight w corresponds to a sequence w, u, v. Edge e1 is smaller than e2 if the sequence for e1 is lexicographically smaller than the sequence for e2. That is, if e1 has sequence w1, u1, v1 and e2 has sequence w2, u2, v2 then e1 < e2 if
- w1 < w2, or
- w1 = w2 and u1 < u2, or
- w1 = w2 and u1 = u2 and v1 < v2.
The algorithm you implement should be a modification of radix sort. Treat each of w, u and v as one "digit" for the radix sort.
[50 marks] minWeightTree: the object associated with the method is a WeightedEdgeList that has already been sorted by weight. The tasks of sorting by weight and finding the minimum weight tree have been separated so that you can get part marks if one of the two methods works properly but the other one does not.
If the graph is connected, the method returns a WeightedEdgeList that contains the edges in a minimum weight spanning tree. If the graph is not connected, the edges returned give minimum weight spanning trees for each of the components of the graph. The tree edges should be removed from the WeightedEdgeList that is the object associated with the method. This means that when the method returns, the original object contains just the non-tree edges (the chords).
The algorithm you should implement for this question is:
```
For each of the edges e= (u, v) in the original WeightedEdgeList:
     If u and v are not in the same component
         Remove the node with e from the WeightedEdgeList
         and add it to the end of the list of tree edges.
     endif
end for
```
You should use the methods in the class UnionFind to maintain information about the connected components.

Files Provided for this assignment:

Right click on the file names and use "Save as" to save these.

Java code:

Some sample input files

in.txt
The corresponding output file: out.txt
in_3reg.txt The corresponding output file: out_3reg.txt
in_dense.txt
in_disc.txt
in_repeat.txt