Project Description:

Consider a weighted complete graph G with vertex set V = {v0, v1, v2, …, vn}. The weight of the edge between vi and vj is denoted as w(i, j). A spanning tree T of G is a subtree of G with the following properties: (i) The root of T is v0; (ii) T spans all the vertices in V. The diameter of the spanning tree T is defined as

diameter(T) = maximum {P| P is the path in T from v0 to a vertex in V}

The Minimum Diameter Spanning Tree (MDST) problem is, given G, to find a spanning tree T with minimum possible diameter. The problem is critical in circuit design for Clock layout where the clock signals generated at vertex v0 must reach all other vertices as fast as possible. Note that any shortest path tree is a MDST. Therefore the MDST problem can be solved by using any algorithm for the shortest path tree problem. In particular, assuming that the weights in G are non negative, then the MDST problem can be solved by Dijkstra’s algorithm. However, the spanning tree generated by Dijkstra’s algorithm may have too large total edge length. In circuit design, large total edge length means large total wire length and is not a desired feature.

The Minimum Spanning Tree (MST) problem is, given G, to find a spanning tree T with minimum possible total edge length. There are many algorithms for the MST problem. But these algorithms may generate spanning trees with large diameters.

Prim’s algorithm is a well known MST algorithm with similar structure as Dijkstra’s algorithm. The only different between Prim’s algorithm and Dijkstra’s algorithm is on the calculation of the cost of the action when a vertex u is connected to a vertex v in the spanning tree. For Prim’s algorithm, the cost of the action is simply w(u, v). For Dijkstra’s algorithm, the cost of the action is calculated as w(u, v) + p(v0, v) where p(v0, v) is the path length of the path within the path tree from the root v0 to v.

Thus, Prim’s algorithm and Dijkstra’s algorithm can be integrated by using the following formula for calculating the cost of the action when a vertex u is connected to a vertex v in the spanning tree: w(u, v) + α*p(v0, v), 0≤α≤1. Note that when α=0, the algorithm generates MST; and when α=1, the algorithm generates MDST. By changing the value of α from 0 to 1, the algorithm will generate a list of spanning trees with increasing total edge length, but decreasing diameter.

TASKS

1. Implement a function, randomGraphGenerator(int n) that will generate a non-negative weighted complete graph with n vertices.

2. Implement the integrated algorithm described above.

3. Write a main program to test the integrated algorithm.

o The program will generate a non-negative weighted complete graph with the number of vertices specified interactively by the end user.

o The program will generate 11 spanning trees by changing the value of α from 0 to 1 with step value 0.1.

o The program will evaluate the diameter and total wire length for each of the spanning tree generated.

4. Write a critical analysis of the performance of the integrated algorithm, based on your experiment results for various value of n.

Programming language: recommend Java.

Mathematics