This project consists of 3 parts:
Part A: Implements a data structure type of a directed weighted graph in Python.
Part B: Implements algorithms for use on a directed weighted graph in Python.
Part C: Makes a comparison for the implementation of selected algorithms of the graph in Python versus 2 other implementations:
- The first is of ex2 project which implemented in Java.
- The second is of the Python library for graphs - NetworkX.
This package contains:
3 python files which each file contains a class.
2 abstract classes which represents interfaces.
-
NodeData class implemented in the node_data file.
It represents the set of operations applicable on a node in a directed weighted graph.
This class implements the methods:
set & get methods, _ _ init _ _ method, _ _ str _ _ method and _ _ copy _ _ method. -
DiGraph class implemented in DiGraph file using the definition of GraphInterface.
It represents a directed weighted graph.
This class implements the methods:
_ _ init _ _ method, methods for returning the number of nodes / edges in the graph,
methods for returning a dictionary of all nodes in the graph / all edges connected to (into) a given node / all edges connected from a given node, a method for returning the mc (mode count - counts changes in the graph), methods for adding / removing nodes and edges to / from the graph, _ _ str _ _ method and _ _ copy _ _ method. -
GraphAlgo class implemented in GraphAlgo file. It inherits from the given GraphAlgoInterface abstract class and represents a Directed (positive) Weighted Graph Theory algorithms.
The class includes a set of operations applicable on a graph type of DiGraph:
_ _ init _ _ method which initializes a graph with a given graph, a get_graph method, a method which saves self graph to a given file name and a method which loads a graph to self graph (using JSON format), a method for finding the shortest path in the graph between a given source and destination and finding its length - using Dijkstra's algorithm, a method for finding the Strongly Connected Component that a specific node is part of, a method for finding all the Strongly Connected Component in the graph and a method for plotting the graph using Matplotlib library.
This ptoject includes 2 unittest tests :
- TestDiGraph - for testing DiGraph class's methods.
- TestGraphAlgo - for testing GraphAlgo class's algorithms.
For more information go to the project's wiki pages