Welcome to the Ex3 wiki!

• brief about the project
• algorithms
• graph comparison
• how to clone the project
• how to install the libraries

The purpose of this project was to take our Java programming skills and graphs knowledge
and translate them into a Python program.
Initially the Python program represents a directed weighted graph that supports various kind of algorithms.
(more info about the kind of algorithms and functions in the ReadMe file)
Eventually the main goal of the project was to create a time complexity comparison between our
Java graph representation, the new Python graph representation and an existing Python library graph representation
of NetworkX.

in order to obtain the shortest path or shortest path distance in a directed weighted graph,
we have implemented Dikstra's Algorithm to investigate every edge weight from source node to destination node with breadth traversal.

in order to obtain the Strongly connected components list/s in a directed weighted graph,
we have implemented Trajan's Algorithm recursively
to investigate every edge's neighbor while tracking back edges by using depth traversal.

in order to visualize the graphs we have used Matplotlib tools
to locate the nodes in their initialized position, in a 2D axis of (x, y).
we created a method to initialize the node's location in case it wasn't.

in case all the nodes are position less - we will randomize the location between 0 to max amount of nodes multiplied,
and save the location data in a dictionary, so that we don't repeat the same position again, while verification takes O(1) complexity.

in case only few nodes are position less - we will randomize the (x, y) values between the (max height, min height) position of previous nodes
while saving the data to avoid repeating the same position again.

quick understanding of how the comparison works-
by exporting our java test results into a Json file, we could load it into Python and compare between the platforms.
the tests shown below are preformed over a total of 5 different graphs, each contains a different amount of vertexes and edges.
each table will provide time difference data in seconds comparing a single algorithm between the 3 platforms.
the tests were done on an intel i7gen8, with 8GB ram laptop.

• Python
• Java
• NetworkX

from the cmd/terminal use git clone :

git clone https://github.com/ShalevAsor/Ex3.git

Note If you have not yet initialized git you should use this command first :

git init

or you can download the zip file :

The only library in our project that requires individual installation is mathplotlib
from the terminal/cmd :

Install numpy

second step :

Install matplotlib

Note: you should verify that your numpy version is : 1.19.3