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

Closed

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.

Skills: Java, Mathematics, Software Architecture

See more: implement function randomgraphgenerator, where to find java, where i find programming tasks, vertices on a graph, vertex programming software, tree structure programming, tree structure algorithm, trees structure, trees properties, trees in algorithm, trees graph, trees algorithms, tree of a graph, tree in algorithm, tree graph java, tree graph, tree and graph, the shortest path algorithm, the analysis of algorithms, test algorithms, structure trees, structure graph, shortest path in graph, shortest path graph algorithm, shortest path dijkstra

Project ID: #4832019

16 freelancers are bidding on average $185 for this job

samitXI

Consider it done~~ Thanks

$253 SGD in 3 days
(88 Reviews)
6.5
msabouri

I can help you with your project. Please contact me if you are interested.

$99 SGD in 1 day
(51 Reviews)
5.3
ranganathp

Can help... I am a Java expert... can start immediately...

$400 SGD in 7 days
(11 Reviews)
5.3
yeki

I'm an expert developer. Please see your PMB.

$200 SGD in 5 days
(11 Reviews)
4.6
CodingWhiz

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.

$88 SGD in 5 days
(7 Reviews)
4.1
hbxfnzwpf

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

$194 SGD in 3 days
(12 Reviews)
4.2
szymszteinsl

Ready, sir!

$206 SGD in 3 days
(10 Reviews)
4.2
Jraml

Please, read my private message. Thanks.

$100 SGD in 3 days
(3 Reviews)
2.6
siamreza

i am interested., please check pm., thanks

$147 SGD in 3 days
(1 Review)
2.6
cimemi

Please see PM

$200 SGD in 5 days
(1 Review)
0.4
luddelol

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

$155 SGD in 3 days
(0 Reviews)
0.0
sivari

If you like to do this C#.Net, check PM please.

$222 SGD in 7 days
(0 Reviews)
0.0
nehajain2050

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

$88 SGD in 3 days
(0 Reviews)
0.0
moeed10

i have a lot of experience in graphs. i can do it in no time.

$83 SGD in 2 days
(0 Reviews)
0.0
ulisesrdom

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!

$135 SGD in 7 days
(0 Reviews)
0.0
makbous

Hello, Can you please check PM. Best regards

$200 SGD in 3 days
(0 Reviews)
0.0
hamedk72

I'm here to help you. please contact me if you're interested.

$98 SGD in 3 days
(0 Reviews)
0.0
zswnetworks

is there any demo

$444 SGD in 3 days
(0 Reviews)
0.0