Class GraphAlgo - GiladShotland/EX3-OOP GitHub Wiki

3.GraphAlgo

This Class provides a bunch of algorithms the apply on a directed weighed graph. The class has the following methods:

1. save_to_json( file_name: str) - save the graph which the Algo object is initialized on in a json format to a file named and placed by a String given (the method will return true if the graph was successfully saved)

2. load_from_json( file_name: str) - load a graph from a json formatted file(the method will return true if the graph was successfully loaded) For example to a json formatted graph - see below.

3. shortest_path(self, id1: int, id2: int) : returns a tuple with the shortest path length and an array with the ids of the nodes in the pat between two nodes in the graph. This implementation uses Dijkstra's algorithm (wikipedia link below)

4. connected_component( id1: int) : returns a list with ids of the nodes in the strongly connected component which the given node is at. This implementation uses a version of Kosaraju's Algorithm with a BFS (wikipedia link below)

5. connected_components() : returns a list of lists, each list contains ids of a single strongly connected component, such that all the lists in the list represents all the strongly connected components in the graph.

6. plot_graph(): plotting the graph using matplotlib library.

Related Links and Examples

1. Dikjstra's Algorithm

2.Kojsaraju's Algorithm

3.Example for a Json formatted grpah:

{"Edges":[{"src":0,"w":1.0286816758196655,"dest":1},{"src":0,"w":1.4195069847291193,"dest":2}],"Nodes":[{"pos":"35.212217299435025,32.106235628571426,0.0","id":0},{"pos":"35.21172908313156,32.10509072268908,0.0","id":1},{"pos":"35.21313005165456,32.1046000487395,0.0","id":2}]}