Ex3 Python

presented by: Almog David - 207749441 & Roni Pick - 206794075

The classes:

• Node class: This class is designed to create a node/vertex in the graph. Each node in the graph has a unique key and a location- that represents a geo location <x,y,z> of the node in 3D space.

• DiGraph class: This class implements the abstract class GraphInterface. Each graph has a counter (MC) that counts the changes in the graph, a nodeSize parameter (int) that contains the number of nodes in the graph, a edgeSize parameter (int) that contains the number of edges in the graph and 3 collections in the form of dictionary:

  • The first (nodes) for keeping the nodes of the graph in a pair of node id: Node.
  • The second (out_edges) for keeping the information of all the out edges from every node in a set of source id: destination id: weight.
  • The third (in_edges) for keeping the information of all the in edges to every node in a set of destination id: source id: weight.

• GraphAlgorithms class: This class implements the abstract class GraphAlgoInterfaces, which has algorithms that can be run on the graph:

  • shortestPath(): This algorithm gets two id numbers (source node's id and destination node's id) and return a tuple that contains a length of the path between the two vertices and a list of the nodes we visited in the shortest path between two vertices. In order to check the shortest path we will use a variant of Dijkstra that return 2 dictionaries: one for all the length (value) from the source node to all the nodes in the graph, and the other represents the previous node id of every node (from who we got to this node). For example: if we went from node A to node B, in the dictionary at the node B id we will add node A because A is his previous.

  for more information about Dijkstra Algorithm: Dijkstra or watch this video video

  • center(): This algorithm return a tuple that contains the node that represent the center of the graph and the value of his min-maximum distance. A center is determined by the minimum length of the group that contains the longest path of every node. In order to find the center we will use a variant of Dijkstra that return 2 dictionaries: one for all the length (value) from the source node to all the nodes in the graph, and the other represents the previous node id of every node (from who we got to this node). (just like in shortestPath).

  • Tsp(list cities): this algorithm get a list of cities/node's id and return a tuple that contains a list of the nodes that are in the shortest path that visits all the cities/nodes that given to us, and the overall distance.

    for more information about the TSP problem: TSP problem

  • save_to_json()/load_from_json(): saving the graph to Json object and loading the graph from Json String.

Results Table:

Number of Nodes/ Function	Save	Load	shortestPath	Center	Tsp
1,000 Nodes	187 ms	46 ms	62 ms	30.6 sec	781 ms
10,000 Nodes	1.755 sec	374 ms	570 ms	X	9.43 sec
100,000 Nodes	34.462 sec	8.841 sec	14 sec	X	212.4 sec

X - more then 10 minuets to run.

How to run:

In order to run the program, all you need to do is to open the program in pycharm, then there are few classes, choose the "main.py" class and there are 4 different checks, you can choose:

• if you want to run them you need to copy your json file name of path in check1 or check2 and to change in the last function main you need to change the number of the check. check0 and check3 are randoms nodes in the graph, you can change the number of the Nodes and add edges as you wish.
• if you want to run your own json file - we have a different function called enter_json, it's in the main and you only need to remove the - #, enter your path to your json file as a string "..../.json" and run - it will open the grapic of your graph.

if you would like to check different function on your graph you can add the following lines:

• find TSP: you need to add the wanted nodes in []

  • e.g: print(g_algo.TSP([1, 2, 4]))

• find Center: you just need to write the command: print(g_algo.centerPoint())

• find Shortest path: you need to add the wanted nodes in 2 variables

  • e.g: dist, path = g_algo.shortest_path(2, 20) and then the commaned: print(dist, path)

• if you want to save your graph into json file you need to write the command: g_algo.save_to_json(file + '_saved') the file is your string json name, and it will save the graph as json file with the ending _saved.

  • e.g: file = "C:/Users/User/Desktop/Ex3/src/data/T0.json"