Comparison report - nofaryos/OOP_Ex3 GitHub Wiki
ASUS PC Specifications: i7, Memory: 7.9GB, Processor: Intel (R) Core (Tm) i7-8565U CPU 1.80GHz, num of Processors: 8.
In this report we performed run times comparisons of 6 graphs in three different implementations: Jave, Phyton, NetworX.
Details on each graph:
Graph 1- graph with 10 nodes and 80 edges.
Graph 2- graph with 100 nodes and 800 edges.
Graph 3- graph with 1000 nodes and 8000 edges.
Graph 4- graph with 10000 nodes and 80000 edges.
Graph 5- graph with 20000 nodes and 160000 edges.
Graph 6- graph with 30000 nodes and 240000 edges.
For each of the graphs we checked correctness and run times in each of the implementations mentioned above in the following functions:
1. Short Path -function that finds the path with the minimum weight, we ran this function 100 times and selected src and dest at random each time.
2. BFS - function that marks in black the nodes to which we were able to reach from the src node. We ran this function 100 times in each of the implementations and selected a random src each time.
3.Dijkstra- function that scans the graph using the weight and the info of each node, starting from the src node, returns a nodes dictionary of the shortest path from the resulting node. We ran this function 100 time in each of the implementations and selected a random src each time.
4. Connected Components - function that finds all the connected components in a graph. We ran this function once for each graph in each of the implementations.
5. Connected Component -function that finds the strongly connected component (SCC) of specific node. We ran this function 100 times for each graph in each of the implementations and each time we choose a random key of node.
The results of the comparison between the running times of the three implementations are shown in the following graphs:
- BFS- you can be seen that in the big graphs the BFS algorithm of networkX, as expected is the fastest, then the implementation of java and finally the implementation in python. The implementation in java may be faster because in python we have access to the in edges and out edges of the graph so when we want to "turn" the edges of the graph we do so within the BFS function, by using the in edges of each node. In java, on the other hand, we only have access to the out edges, so when we want to turn the edges of the graph we have to create a new graph with inverted edges, we do this using an external function that tranposes the graph. This saves runtime within the BFS function in java.
- Short Path- in the three implementations of the shortest path is found using the Dijkstra algorithm. However, the implementation in Java seems to be a little more faster than the implementation of networkX!
- Connected Component- you can see that the implementation in python is faster than java, because in Python when we want to "turn" the edges of the graph we just use the dictionary of the in-edges within the BFS function, however, in java we do not have access to the in-edges, so we have to create a new graph with inverted edges, this involves calling another function that actually turns the graph besides BFS.
- Connected Components- you can see that the implementation in python is as fast as the implementation in natworkX! This function is called to Connected Component function which is faster in python, therefore this function is also faster in python.
- Dijkstra- you can see that this algorithm is the fastest in java, this explains the comparison of times in the function of the shortest path in the three implementations - because it calls to Dijkstra algorithm in java you can find the shortest path in the fastest time. Perhaps the implementation in java is the most effective because we returned a Boolean answer in java - whether the graph is connected or not and used the information of the nodes after running this algorithm. In Python, on the other hand, we returned a dictionary of nodes that we were able to reach and their ancestors.
