Code structure, how algorithms are implemented - nofaryos/OOP_Ex3 GitHub Wiki

On this page we will detail you about the interfaces, classes and functions in our project. The project consists of two classes: DiGraph and GrapgAlgo that implement the interfaces of: GraphInterface, GraphAlgoInterface.

DiGraph class:

  • This class contains an internal class called nodeData:

nodeData class:

The nodeData internal class initializes a vertex in a graph by a unique key and location. If we do not initialize a location to the node, its location will be null. Moreover, the node has additional properties that are set at the time the node is initialized, this properties initialized in the same way for all tne nodes:

  • Tag- Indicates whether the node belongs to any connected component in the graph.

  • Info- The color of the node. In running algorithms in the Algo Graph class, the node color indicates whether we were able to reach the node.

  • Weight- used to find weights of paths in a graph.

The functions on this class are gettes and setters of the node fildes.

DiGraph:

  • This class creates a directed weighted graph. The graph consists of nodes data objects- Which represent the vertices in the graph, and edges that connect between the nodes. Each side has a weight that is the "cost" of the side up to the target node. In this class you can run various functions on the graph:

  • remove_node(id1) - A function that removing the node with id1.

  • remove_edge(node_id1, node_id2)- A function that removing the edge between node_id1 to node_id2.

  • get_mc()- A function that returns the number of changes that made to the graph.

  • get_all_v()- A function that returns the nodes that the graph contains.

  • v_size()- A function that returns the number of nodes in the graph.

  • e_size()- A function that returns the number of edges in the graph.

  • all_in_edges_of_node(id1)- A function that returns all the in-edges to the node with id id1 and their weights.

  • all_out_edges_of_node(id1)- A function that returns all the out-edges to the node with id id1 and their weights.

  • add_node(node_id, pos)- A function that adding node_id to the graph.

  • add_edge(id1, id2, weight)- A function that connecting an edge with specific weight between id1 to id2.

  • as_array_edges()- A function that returns an array of edges, for each edge there is: src node, dest node and edge weight

  • as_array_nodes()- A function that returns an array of nodes- for each node there is unique id and position.

  • as_dict_graph() - A function that returns a dictionary Representing json of the graph with the nodes and edges of that graph.

GraphAlgo class:

This class contains a number of algorithms that operate on Digraphs.

The functions in this class:

  • get_graph() - A function that return the directed graph on which the algorithm works on.

  • load_from_json(file_name)- A function that load a graph from Json file.

  • save_to_json(file_name)- A function that save the graph to file in Json format.

  • Shortest Path(id1, id2)- A function that accepts two keys that represent two nodes in the graph and finds the path with the minimum weight between them. If there is a path between the two node, the function returns the keys of the nodes in the path, as well as the weight of the path. else, the algorithem return empy list and a value of infinity. To implement this algorithm we used another algorithm which is Dijkstra.

  • Dijkstra(key)- This algorithm scans the graph starting from some src node(the node with id key). Using the info and the weight of each node, at each stage of the algorithm each node is marked in black or white, according to which it is possible to know whether the algorithm has already visited a particular node in the graph: black- visit, white- not visit yet. At the end of the algorithm run some of the info nodes may remain white because we were unable to reach them, i.e. there is no path between them and the src node. We kept the nodes in a priority queue data structure, the priority of each node in the queue is actually its weight, so at each step we removed a node from the queue, we removed the node with the minimum weight and thus ensured we found the path with the minimum weight between the two nodes. The algorithm returns a dictionary of all the nodes we were able to reach from the beginning node and the ancestor of each node we were able to reach

  • Connected Component(id1)- An algorithm that finds the strong connected component of the node with id id1 in the graph, meaning that the algorithm returns a set of nodes where it can be reached from any node to any node. To implement this algorithm we used another algorithm which is BFS. We called BFS twice - the first time with the out edges of the node with which we called the connected_component function and returned all the nodes that can be reached from that node. In the second time we called BFS with the in edges to the same node and returned all the nodes that reach that node. The group of nodes we returned is the group of intersections between these two groups - that is, all the nodes that reach the same node and all the nodes that we were able to reach from the same node.

  • Connected Components- An algorithm that finds all the strong binding elements in a graph. To implement this algorithm we will repeat the process of finding connected_component for each node in the graph, but only if it does not belong to a particular connected component. A node that already belongs to any connected component has a (-1) tag.

  • BFS(self, key, regular) - An algorithm that used to find connected components in a graph, this algorithm scans the graph from the src node(the node with id key). The algorithm uses the node info field and first colors all the nodes in white. During the run of the algorithm, each node we were able to reach was marked in black. The algorithm returns all the nodes we were able to reach from the beginning node. If the algorithm in regular position then we go over the out-edges of each node, otherwise we go over the in-edges of each node.

  • plot_graph()- A plot function that draws a directed graph with the help of the matplotlib library, we added the nodes and edges with arrows in the appropriate places. If there is a node without pos: We took an average of his neighbors' pos and updated his pos on that average, If he has no neighbors, he was drawn a random pos.

You can download the code by opening cmd on your computer in the desired folder and executing the git clone command with the url of this page. You can then run the code after importing the directories in which we used this code, for example: random priority queue, matplotlib and more.