# main program to Implement a function, randomGraphGenerator(int n) that will generate a non-negative weighted complete graph with n vertices. - repost

Budget $30-250 SGD

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.

## 16 freelancers are bidding on average $185 for this job

I am proficient in graph theory and OOP languages and can easily implement the described algorithm and main program in Java, as well as write up the complexity analysis.

I am very proficient in java. I have 12 years java developing experience. I have worked for 5 years. Please let expert help you.

Don't hire user samitXI. He is a scammer, stole $1800 from me. Happy to provide more information in PM.

I am an experienced Java engineer and has already done task like this. I will be able to accomplish this task in set time frame and design quality. Let me know the details and I am ready to start finish as per your exp More

Hello. I have worked before with both algorithms and also have experience in java. The critical analysis should be no problem. Seems like a fun project!