Data Structure - HelenYunes/OOP_Ex3 GitHub Wiki

DiGraph class:

This class represents a directed weighted graph. This class can create a directional and weighted graphs and add or remove nodes or edges on a given graph. The DiGraph class implements the GraphInterface interface. Each graph has a 3 dictionary: the first is a dictionary of all the nodes in the graph, each node is represented using a pair (node_id, NodeData), the second is a dictionary of all the nodes connected to (into) node_id , each node is represented using a pair (other_node_id, weight) and the last is a dictionary of all the nodes connected from node_id , each node is represented using a pair (other_node_id, weight).

GraphAlgo class:

This class implements GraphAlgoInterface and represents an directed (positive) Weighted Graph Theory algorithms including:

  • get_graph- return the directed graph on which the algorithm works on.

  • load_from_json - loads a graph from a json file.

  • save_to_json - saves the graph in JSON format to a file

  • shortest_path - returns the shortest path from node id1 to node id2 using Dijkstra's algorithm

dijkstra algorithm step by step:

Dijkstra algorithm

  • Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.

  • Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes. Set the initial node as current.

  • For the current node, consider all of its unvisited neighbours and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one.

  • When we are done considering all of the unvisited neighbours of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.

  • If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.

  • Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3.

  • connected_component - finds the Strongly Connected Component(SCC) that node id1 is a part of using tarjan's strongly algorithm.

  • connected_components - finds all the Strongly Connected Component(SCC) in the graph using tarjan's strongly algorithm.

Tarjan Algorithm is based on following steps:

Tarjan's algorithm

  1. DFS search
  2. Strongly Connected Components form subtrees of the DFS tree.
  3. If we can find the head of such subtrees, we can store all the nodes in that subtree (including head) and that will be one SCC.
  4. There is no back edge from one SCC to another (There can be cross edges, but cross edges will not be used while processing the graph).
  • plot_graph - plots the graph using matplotlib. If the nodes have a position, the nodes will be placed there, otherwise, they will be placed in a random but elegant manner.