GraphAlgo

GraphAlgo class:

This class implement a number of algorithms on a directional weighted graphs.

• This graphAlgo class algorithms is working in a DiGraph objcet class.

class methods:

1. get_graph() - return the init graph.
2. save_to_json(file_name) - save the graph to a json file with the given file name.
3. load_from_json(file_name) - load the graph from a json file by the give file name.
4. shortest_Path() - counts the length and create a nodes list (path) of the shortest path between two given nodes and return a tuple contains the weight and the path as a list between those nodes (this function uses Dijkstra algorithm).
5. connected_component(node_id) - return a list with all the Strongly Connected Components that specific node is a part of (This function uses the BFS algorithm).
6. connected_components() - return a nested list with all the Strongly Connected Components in the graph (This function uses the BFS algorithm).
7. plot_graph() - plot the graph to a window using matplotlib, If the nodes have a position, this method draw them according to their current position, else they will be placed randomly position by using get_position() method in GraphCreator class.

Dijkstra algorithm explanation:

First in Dijkstra algorithm we reset all the nodes weight to infinity and the tag to 0 (0 - is mean like 'unvisited'), after that using a priority queue the algorithms will get the source node and add it to the priority queue, by a loop (while the queue is not empty) poping the last node from the queue and going throw all the childes of the current node, for each child create a new distance with the current node weight and the child and if the weight of the child node is lower, set the new weight to the child node, and each node we visited we mark the tag to 1 as visited, each time we changed a node weight to the lowest we save for each node the previous parent node that the algorithm got from, after we done to visit all the nodes in the graph we using another loop to go from the destination node by previous nodes to the source node, and meanwhile we create the path between the destination node to the source node, after we got back to the source node we take the path that created and reversed it, and that how we got the shortest path between two nodes, in addition if we want to get the weight of the edges between the nodes (like length or distance) we need to take the weight only of the destination node.