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.
This feature in our project uses strictly matplotlib. We simply draw a dot and an ID for each node in the dictionary of nodes in the graph. Then, we go through each node and get the out edges of this particular node. We use this data to find the source and destination nodes. We use their x, y values to draw an arrow pointing from the source to the destination.
For each edge drawn we add 1 to a counter and at the end of the function we compare e_size and ecounter. We use this for software safety. We used the following source: https://www.southampton.ac.uk/~feeg1001/notebooks/Matplotlib.html
This feature uses - in addition to matplotlib - pygame and easygui. easygui is an open library for simple popups, it uses tkinter. The reason we did not implement this feature ourselves, is because the GUI was not a crucial part of the assignment.
We used the following source for combining matplotlib and pygame: http://www.pygame.org/wiki/MatplotlibPygame
The pygame window will show the graph on the left side of the screen, and buttons on the right side. We emphasize that this feature is WIP and the design is just for debugging purposes.
There are 11 buttons, the top half is for the different algorithms and the bottom half is for editing the graph.
For refreshing the graph in pygame, for each button listener, if a refresh is needer we change the boolean updated from False to True.
At the end of the while loop (-pygame) we check if updated is True, if it is, we update the graph. Using the draw_graph function, which returns a matplotlib graph, and then painting it on the pygame canvas.
In the following picture, we can see an example of a listener that asks the program to refresh the graph (updated = True). At the bottom we can see the if updated: condition that refreshes the graph.
