Implementation
We implemented the two interfaces GraphAlgoInterface.py and GraphAlgoInterface.py to GraphAlgo.py and DiGraph.py
We also used components class to contain the Classes : EdgeData, NodeData and GeoLocation\
Here The methods we build for them:
| Method | Description |
|---|---|
| add_node(node_id, position) | adds a node to the graph. |
| remove_node(node_id) | removes a vertex with all its edges from the graph by its key |
| get_node() | returns the vertex associated with a given key |
| addEdge(id1, id2, weight) | adds an edge with a weight between two existing vertices. The edge is a direction from source to destination when added in a directed graph. If the edge already exists or one of the nodes dose not exists the functions will do nothing |
| removeEdge(id1, id2) | removes an edge between two existing vertices |
| all_in_edges_of_node(node_id) | return a dictionary of all the nodes connected to (into) dest , each node is represented using a pair (key, weight) |
| all_out_edges_of_node(node_id) | return a dictionary of all the nodes connected from src , each node is represented using a pair (key, weight) |
| v_size() | gets the number of vertices in the graph. |
| e_size() | gets the number of edges in the graph. |
| get_mc() | Returns the current version of this graph, on every change in the graph state - the MC should be increased |
| Method | Description | Complexity |
|---|---|---|
| load_from_json(file_name) | Loads a graph from a json file. | O(V+E) |
| save_to_json(file_name) | Saves the graph in JSON format to a file | O(V+E) |
| shortest_path(src, dst) | Returns the shortest path from node src to node dst using Dijkstra's Algorithm | O((V+E)*LOG(V)) |
| connected_component(key) | Finds the Strongly Connected Component(SCC) that node id1 is a part of. | O(V+E) |
| connected_components() | Finds all the Strongly Connected Component(SCC) in the graph. | O(V*(V+E)) |
| plot_graph() | Plots the graph. If the nodes have a position, the nodes will be placed there. Otherwise, they go to getAlong | O(V+E) |
| try_get_along(node, min_x, max_x, min_y, max_y) | The function is setting elegantly the unpositioned nodes and put them between neighbors or inbox. At the end will return position | O(1) |
| bfs_in(node_id) | checks which nodes node_id could go to | O(V+E) |
| bfs_in(node_id) | checks which nodes could get into node_id | O(V+E) |
My Laptop have the specs of:
i5 6200u
integrated Intel graphics card - nothing
16 GB of ram 2133 MHz
and it's mat black
A0 graph from last assignment
