Analyzing performance

Performance

We'll begin by explaining the createK() function. It receives an Integer which it uses to multiply the amount of nodes in the created graph.

We used this function to save graphs with different sizes of nodes, from 1k all the way to 1000k (1m).

The graphs we use for performance tests are loaded and saved in the 'testData' directory.

• Note that the 1m graph was too big to push to github, about 0.5GB.

Performance of large graphs

• Loaded on a pc with 16GB of ram and an I7-7700HQ (mobile chip).
• Each node has exactly 10 out edges.
• All the functions used to test performance are in 'performanceTests'.

times are in MS

N. of nodes	1k	10k	100k	1000k (1m)
LOADING	41	452	4337	50212
SAVING	100	1037	11154	105000
SHORTESTPATH	16	210	2498	31598
TSP (4 STOPS)	117	1883	19182	214211
CENTER	15900	1886900	timeout	timeout

Output for running `tspPerformance()` in 1M graph:

finished in 214.21165776252747 | TSP Path: ([4, 16381, 49720, 424498, 502888, 461733, 423495, 403513, 97141, 313, 194016, 460487, 650065, 62436, 265373, 858414, 165073, 983255, 495353, 436517, 888, 936736, 414386, 298875, 648611, 295823, 5], 34) | On graph 1m

Output for running center on a 10k graph (30 minutes):