Analyzing the code
This object holds simple function for creating a graph.
It holds a dictionary for nodes, inEdges and outEdges.
nodes - holds each node as an object, the key is the node's ID.
Edges - holds the edges as pair of integers, which are the source and destination IDs.
The IDs also serve as key and value for the dicionary, switching places for inEdges and outEdges.
Add edge - When adding an edge we need to mind the source and destination. And add the edge to the correct dictionary with the correct key and values. Note that edge is not an object in our implementation, it is presented using the Integers of the IDs of the src and dest. Also, when adding an edge we insert the weight of it (float) into the value of the dictionary as well.
Remove node - Removing a node is more tricky then it seems. We first need to find the corresponding edges that are going into or out of the current node. Then, we remove each edge from the correct dictionary. After that we remove the node itself.
This is a more advanced object with more complicated algorithm that requires more explaining. It holds in its values a DiGraph, which then it can loads graph from a json file.
dijkstra - This function creates a dictionary 'D' which holds in tuples the distance for each node, and it's parent node in the path. The key is the destinations node of that particular path.
This function is an direct implementation of Dijkstra's algorithm using Priority Queue. Note that in the following picture, the part that was cut is just retrieving the weight of the current edge.
TSP - Travelling sales person problem. This algorithm receives a list of nodes, and calculates the shortest path going between all those paths. Its easy to see that the naïve way of calculating it is to find the minimum weight of all permutations, problem is that the time complexity of it is n!. Therefore, for small lists we use the naïve algorithm. While for the bigger lists we will use a simple greedy algorithm.
greedyTSP - The greedy algorithm is rather simple. For each step in the path it goes to the closest node in the list.
centerPoint - Simple find min. For each node in the graph we take the maximum weight (using dijikstra), and then we find the minimum maximum weight in the graph. The function returns a tuple, the center ID and the minimum maximum weight.
shortest_path - Simple function that uses dijikstra to find a path between two nodes. It uses the pointer for the parent of each node in dijikstra's dictionary.
In this project we made two different GUIs. A more simple GUI that is based only on matplotlib and a more advanced one that uses also pygame.
The command that initializes the GUI (according to assignment's orders) is plot_graph(). It first pops up a window to the user, asking if he wants to use the simple or advanced GUI.