Mayan Bashan & Yuval Moshe
This project is a part of an OOP class in Python which is divided into 2 main parts:
In this part we implemented a directed weighted graph with the following classes:
- NodeData - represents the a node that is a vertex in a graph a directed weighted graph.
- DiGraph - implements the GraphInterface interface, which represents the graph itself.
- GraphAlgo - implements the GraphAlgoInterface interface, which allows performing algorithmic queries on a specific graph.
The graph was realized by using dictionary structure, and the operations were written by realizing Dijkstra algorithm (please see explanation in the algorithm itself).
In this part we compared our performance, to NetworkX performance (*NetworkX is a python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks).
- Python 3+ compiler | Download Python
- Networkx grpahs python package | View Networkx Install Manual
- matplotlib python package | View matplotlib Install Guide
- Python IDE (Pycharm, Visual Studio Code, etc') | Pycharm Download / Visual Studio Code Download
In order to gain more specific imformation on how to run this project please view the attached wiki pages:
- directed graph - a set of nodes that are connected together, where all the edges are directed from one vertex to another
- weighted graph - edges of the graph are holding a weight
This graph contains 6 nodes and 9 edges.
- connected_component() with 1 as input will return the list [0,1,2,3,4] (we can get from each node in the list to each other node from the list).
- connected_components() function will return [[5],[0,1,2,3,4]] - no path from node 5 to any other node, and if we take any 2 nodes from [0,1,2,3,4],
there will be a path from first node to second node, and a path from second node to first node. - shortest_path() method between node 0 to node 5 will return a dict - {14 , [0,1,3,4,5]} (14=4+2+2+6).
Do notice that the shortest path depends on the sum of the weights of the edges between the 2 nodes and not on the sum of the nodes between 2 nodes.