In this project, we implement the following algorithms from Graph Analysis using given benchmarks of increasing number of nodes (from 10 nodes to 100 nodes).
Basically, we need to show a very nice user interface where a user can select any input files to display a graph using x and y co-ordinates provided for each node in each input file. Once displayed, then the user should able to run the following algorithms.
For Prims, Kruskal & Clustering Coefficient in Graph Theory, if there is a link between two nodes, then consider this as edge in undirected graph. If there are two directed link b/w edges, then consider the edge with minimum cost.
- Prims
- Kruskal
- Dijkstra
- Bellman Ford
- Floyd Warshall Algorithm
- Clustering Coefficient in Graph Theory (Only Local Clustering).The final cost should be the average of all local clustering of all nodes
Run npm install to install all the packages and npm start to run it locally.
NETSIM
10
0 0.362291 0.441396
1 0.156279 0.341383
2 0.699696 0.045577
3 0.714313 0.171668
4 0.378966 0.495494
5 0.961942 0.444337
6 0.726886 0.575888
7 0.168639 0.406223
8 0.875627 0.061439
9 0.540054 0.317061
5 7 155200000.000000 54000000.000000 37997287.259045 6 155200000.000000 99000000.000000 39750353.908602 1 155200000.000000 69000000.000000 38678117.620931 4 155200000.000000 30000000.000000 23405259.371858 2 155200000.000000 78000000.000000 56657305.131718
3 4 155200000.000000 40500000.000000 24507574.164251 7 155200000.000000 33000000.000000 23141933.511825 0 155200000.000000 69000000.000000 38678117.620931
4 6 155200000.000000 33000000.000000 18606647.555561 8 155200000.000000 30000000.000000 15445985.998540 3 155200000.000000 58500000.000000 30303381.007264 0 155200000.000000 78000000.000000 56657305.131718
5 6 155200000.000000 72000000.000000 39198085.614926 8 155200000.000000 84000000.000000 44410792.717398 5 155200000.000000 51000000.000000 21057394.108265 9 155200000.000000 82500000.000000 44921474.240129 2 155200000.000000 58500000.000000 30303381.007264
4 1 155200000.000000 40500000.000000 24507574.164251 9 155200000.000000 25500000.000000 14976264.807255 7 155200000.000000 81000000.000000 35908738.453294 0 155200000.000000 30000000.000000 23405259.371858
3 9 155200000.000000 39000000.000000 22698315.021204 6 155200000.000000 39000000.000000 31057947.119098 3 155200000.000000 51000000.000000 21057394.108265
6 9 155200000.000000 27000000.000000 11652174.351163 2 155200000.000000 33000000.000000 18606647.555561 3 155200000.000000 72000000.000000 39198085.614926 8 155200000.000000 18000000.000000 10221573.506817 5 155200000.000000 39000000.000000 31057947.119098 0 155200000.000000 99000000.000000 39750353.908602
3 0 155200000.000000 54000000.000000 37997287.259045 1 155200000.000000 33000000.000000 23141933.511825 4 155200000.000000 81000000.000000 35908738.453294
3 6 155200000.000000 18000000.000000 10221573.506817 3 155200000.000000 84000000.000000 44410792.717398 2 155200000.000000 30000000.000000 15445985.998540
4 5 155200000.000000 39000000.000000 22698315.021204 6 155200000.000000 27000000.000000 11652174.351163 4 155200000.000000 25500000.000000 14976264.807255 3 155200000.000000 82500000.000000 44921474.240129
1
NETSIM // Ignore this line
10 // Total 10 nodes
0 0.362291 0.441396 // x and y position of each node
1 0.156279 0.341383
2 0.699696 0.045577
3 0.714313 0.171668
4 0.378966 0.495494
5 0.961942 0.444337
6 0.726886 0.575888
7 0.168639 0.406223
8 0.875627 0.061439
9 0.540054 0.317061
5 7 155200000.000000 54000000.000000 37997287.259045 6 155200000.000000 99000000.000000 39750353.908602 1 155200000.000000 69000000.000000 38678117.620931 4 155200000.000000 30000000.000000 23405259.371858 2 155200000.000000 78000000.000000 56657305.131718
// 5 to 7, ignore the first value, second one is bandwidth cost // is 5.4 Mbps, ignore the next one
// 5 to 6, same as above, bandwidth cost is 9.9 Mbps,
// Similarly, there is link from 5 to 1 and others
3 4 155200000.000000 40500000.000000 24507574.164251 7 155200000.000000 33000000.000000 23141933.511825 0 155200000.000000 69000000.000000 38678117.620931
4 6 155200000.000000 33000000.000000 18606647.555561 8 155200000.000000 30000000.000000 15445985.998540 3 155200000.000000 58500000.000000 30303381.007264 0 155200000.000000 78000000.000000 56657305.131718
5 6 155200000.000000 72000000.000000 39198085.614926 8 155200000.000000 84000000.000000 44410792.717398 5 155200000.000000 51000000.000000 21057394.108265 9 155200000.000000 82500000.000000 44921474.240129 2 155200000.000000 58500000.000000 30303381.007264
4 1 155200000.000000 40500000.000000 24507574.164251 9 155200000.000000 25500000.000000 14976264.807255 7 155200000.000000 81000000.000000 35908738.453294 0 155200000.000000 30000000.000000 23405259.371858
3 9 155200000.000000 39000000.000000 22698315.021204 6 155200000.000000 39000000.000000 31057947.119098 3 155200000.000000 51000000.000000 21057394.108265
6 9 155200000.000000 27000000.000000 11652174.351163 2 155200000.000000 33000000.000000 18606647.555561 3 155200000.000000 72000000.000000 39198085.614926 8 155200000.000000 18000000.000000 10221573.506817 5 155200000.000000 39000000.000000 31057947.119098 0 155200000.000000 99000000.000000 39750353.908602
3 0 155200000.000000 54000000.000000 37997287.259045 1 155200000.000000 33000000.000000 23141933.511825 4 155200000.000000 81000000.000000 35908738.453294
3 6 155200000.000000 18000000.000000 10221573.506817 3 155200000.000000 84000000.000000 44410792.717398 2 155200000.000000 30000000.000000 15445985.998540
4 5 155200000.000000 39000000.000000 22698315.021204 6 155200000.000000 27000000.000000 11652174.351163 4 155200000.000000 25500000.000000 14976264.807255 3 155200000.000000 82500000.000000 44921474.240129
1 // Use node # 1 to find shortest path from 1 to all // destinations
In the above graph, if there are directed edge from both vertices or nodes, then consider sepearate cost for each outgoing and incoming e.g. above, cost from 4-3 is 5.85Mbps while cost from 3-4 is 8.1Mbps. Ignore cost from same node edge e.g. 5-5 or 0-0. If there is only one edge, then consider this as undirected edge i.e. there is same cost in both directions.
10 // Total 10 nodes
0 0.362291 0.441396 // x and y position of each node
1 0.156279 0.341383
2 0.699696 0.045577
3 0.714313 0.171668
4 0.378966 0.495494
5 0.961942 0.444337
6 0.726886 0.575888
7 0.168639 0.406223
8 0.875627 0.061439
9 0.540054 0.317061
5
7 54000000.000000
6 99000000.000000
1 69000000.000000
4 30000000.000000
2 78000000.000000
// 5 to 7; Bandwidth cost is 5.4 Mbps
// 5 to 6; Bandwidth cost is 9.9 Mbps
// Similarly, there is link from 5 to 1 and others
3
4 40500000.000000
7 33000000.000000
0 69000000.000000
4
6 33000000.000000
8 30000000.000000
3 58500000.000000
0 78000000.000000
5
6 72000000.000000
8 84000000.000000
5 51000000.000000
9 82500000.000000
2 58500000.000000
4
1 40500000.000000
9 25500000.000000
7 81000000.000000
0 30000000.000000
3
9 39000000.000000
6 39000000.000000
3 51000000.000000
6
9 27000000.000000
2 33000000.000000
3 72000000.000000
8 18000000.000000
5 39000000.000000
0 99000000.000000
3
0 54000000.000000
1 33000000.000000
4 81000000.000000
3
6 18000000.000000
3 84000000.000000
2 30000000.000000
4
5 39000000.000000
6 27000000.000000
4 25500000.000000
3 82500000.000000
1 // Use node # 1 to find shortest path from 1 to all // destinations