Skip to content
Lioz Akirav edited this page Jan 22, 2021 · 2 revisions

Welcome to the OOP_Ex3 wiki!

The wiki includes five parts:

  1. Home - Here you can read about the performance of this project compare to other projects.
  2. NodeData - There you can read about the NodeData class and learn how to use its functions.
  3. DiGraph - There you can read about the DiGraph class and learn how to use its functions.
  4. GraphAlgo - There you can read about the GraphAlgo class and learn how to use its functions.
  5. How To Run - There you can read how to install the libraries and run the project on your computer.

Performance Comparison

To examine our implementation in this project we had to test and compare our project to two other implementations:

  1. Our previous project whose goal in the first part was to implement a weighted directed graph in Java[1].
  2. NetworkX implementation[2].

The functions that have been tested:

  1. Shortest_path.
  2. connected_component*.
  3. connected_components.

*Note: NetworkX does not include the connected_component function.

Behind the testing process:

We loaded six different graphs in JSON format from the data directory and tested those three functions multiple times on random inputs, then we calculated the average result of each function of each implementation. Then all the data that we collected moved automatically to the chart generator that we built(using matplotlib library[3]). The generator makes six-bar chart tables that visualize the data.

Results ⏳:

image

Results Table πŸ“œ :

Graph number\Implementation Networkx Python Java
Function: Shortest graph
1 9.72747802734375e-06 0.0 0.0024046
2 0.0007428646087646485 0.0007552623748779297 0.0020393
3 0.005021333694458008 0.00932469367980957 0.0286995
4 0.08763518333435058 0.11620373725891113 0.3990609
5 0.18341240882873536 0.28987560272216795 0.5003517
6 0.39250407218933103 0.5135819911956787 0.2987889
Function: Connected component
1 --- 0.0002090930938720703 0.0001906
2 --- 0.00022492408752441406 0.000615
3 --- 0.002910757064819336 0.0005584
4 --- 0.04917502403259277 0.0255793
5 --- 0.11682829856872559 0.0330737
6 --- 0.19282979965209962 0.0009482
Function: Connected components
1 0.0 0.0 0.0001255
2 0.0002048015594482422 0.00019288063049316406 0.00016747
3 0.0010515689849853516 0.010731363296508789 0.0255405
4 0.0010289669036865235 1.0416228294372558 0.22445279999999998
5 0.013895463943481446 5.761834239959716 0.757112
6 0.04243769645690918 21.568990182876586 0.9485512

Data analysis πŸ“‘ :

Shortest path:

The NetworkX has a little advantage over python with a total run time of 0.669 compared to 0.929 seconds. The java implementation shows the worse results in the small graphs but improves in the bigger graphs.

  • πŸ₯‡ NetworkX - 0.669 sec.
  • πŸ₯ˆ Python - 0.929 sec.
  • πŸ₯‰ Java - 1.231 sec.
Connected component:

The java implementation has a little advantage over python with a total run time of 0.060 compared to 0.362 seconds.

  • πŸ₯‡ Java - 0.060 sec.
  • πŸ₯ˆ Python - 0.362 sec.
Connected components:

NetworkX is the most efficient implementation to find the connected components in the graph. In the big graphs (with more than 1,000 vertices and 8,000 edges) the python implementation shows the worst results.

  • πŸ₯‡ NetworkX - 0.058 sec.
  • πŸ₯ˆ Java - 1.955 sec.
  • πŸ₯‰ Python - 28.383 sec.

Conclusions πŸ†:

To summarize the most efficient implementation is the NetworkX after it showed the best results in 2 of the 3 functions. The Java implementation took second place thanks to its advantage in the Connected components test.

  • πŸ₯‡ NetworkX
  • πŸ₯ˆ Java
  • πŸ₯‰ Python

Tested on πŸ–₯️:

  • OS: Microsoft Windows 10 pro 64 bit.
  • RAM Memory: 20 GB.
  • Processor: Intel(R) Core(TM) i7-85500U @ 1.8GHz, 4 cores.

References πŸ“š :

  1. https://github.com/Lioo7/OOP_Ex2-Pokmon_game
  2. https://networkx.org/
  3. https://matplotlib.org/