Skip to content

GraphAlgo

Jump to bottom
AmitSheer edited this page Jan 8, 2021 · 7 revisions

This class is responsible of running algorithms and drawing a graph.

Methods

  • load_from_json(self, file_name: str) -> bool
    Given a file location, including ending, it will load a the graph from the file into the class. If the loading was successful it will return True, otherwise False.
  • get_graph(self) -> GraphInterface
    returns the graph used in the class
  • save_to_json(self, file_name: str) -> bool
    saves the currently held graph with file_name, includes the path. If saved successfully returns True, otherwise False.
  • shortest_path(self, id1: int, id2: int) -> (float, list)
    finds shortest path from id1 to id2, in given graph. It uses Dijkstra's algorithm find the distance and path, thile taking into account the weight of each edge.
    Dijkstra_Animation
    The implementation used is the one with a priority queue where the shortest path is always taken. Afterwards it puts the path into a list, and returns it and the distance from id1 - node to id2 - node, the distance is calculated using the weight of the edges in the path.
  • connected_component(self, id1: int) -> list
    Finds and returns the strongly connected component of a specific node , in a given graph. In order to achieve that it uses Tarjan's strongly connected components algorithm
    Tarjan's_Algorithm_Animation
    To solve recursion problems in bigger graphs the DFS algorithm used to travel in the was flattened, to work as as a loop instead of recursion. In the File Tarjan you can view other algorithms implemented but not used due to longer runtimes.
    After it found the SCC's that can be reached from node it will go over them and extract the one containing the given node.
  • connected_components(self) -> List[list]
    Finds and returns the strongly connected components, SCC, in a given graph. Similarly to connected_component method it uses Tarjan's strongly connected components algorithm to find all of the SCC, and returns them to the user.
  • plot_graph(self) -> None
    Uses the Plotter module to draw the graph, in an aesthetic way. If graph doesn't have position to any of the nodes in the graph it will use Force-Directed graph drawing method - Fruchterman-Reingold. It uses forces of attraction and repulsion between nodes, to calculate the pos of a node in regard to those forces.

Clone this wiki locally