4 Programming Assignment
You are to implement either Prim’s or Kruskal’s algorithm for finding a Minimum Spanning Tree (MST) of an undirected graph, and evaluate its running time performance on a set of graph instances. The 13 input graphs are RMAT graphs [1], which are synthetic graphs with power-law degree distributions and small-world characteristics.
4.1 Static Computation
The first part of the assignment entails coding either Prim’s or Kruskal’s algorithm to find the cost of an MST given a graph file. You may use the programming language of your choice (either C++, Java, or Python). We provide a wrapper function in all three languages to help you get started with the assignment. You may call your own functions inside the wrapper. We also have implemented a timer in the wrapper that records the running time of your algorithms. To implement these algorithms, you may make use of data structure implementations in the programming language of your choice; e.g. in python, the heapq library may be used for implementing priority queues and set operations may be used for implementing the union-find data structure. In Java, java.util.PriorityQueue may be used for implementing priority queues and java.util.Set may be used for set operations.
The ‘graph file’ format is as follows: Line 1: N E (N = number of vertices, E = number of edges)
Every subsequent line contains three integers: u v weight (u &v are end points of edge, weight = weight of edge between u and v. Please note each undirected edge is only listed once in the file.)
The MST calculation is to be implemented in the computeMST function, as indicated in the wrapper code.
4.2 Dynamic Recomputation
The next part of the assignment requires you to update the cost of the MST given new edges to be added to the graph. You are provided with a ‘changes file’ and the format is as follows:
Line 1: N (N = number of changes/edges to be added)
Every subsequent line contains three integers: u v weight (u & v are end points of the new edge to be added, weight = weight of edge between u and v)
You are to implement the function recomputeMST as indicated in the wrapper code that computes the new MST given the new edge to be added into the graph. You are responsible for maintaining the old MST before recomputing.
Note: it is very easy to complete this part of the assignment by simply adding the new edge and calling your old computeMST function from part 1 (Subsection 4.1). The objective is to minimize computation and e ciently recompute the cost of the MST.
4.3 Execution
The wrapper code is set up to require three command line arguments: <executable> <graph file.gr> <change file.extra> <output file>. The <graph file> is the one described in Subsection 4.1 and the <change file> is the one described in Subsection 4.2.