dvir-shaul/dw_graph

Description

This is a project given by Ariel university, the purpose is to implement a directed weighted graph.

Implementation

The implementation of the graph itself was done by using 3 dictionaries, A dictionary to keep all nodes, a dictionary to keep the incoming edges from a node and the outgoing edges.

We have also created a class for nodes and edges. Below is the list of the methods and their short summary. Please look at the code for a more detailed explanation.

Methods

DiGraph pydoc :

https://sylbris.github.io/DW_Graph/docs/DiGraph.html

GraphAlgo pydoc :

https://sylbris.github.io/DW_Graph/docs/GraphAlgo.html

DiGraph	Use	Run time
repr()	prints the graph	O(V+E)
v_size()	returns amount of nodes	O(1)
e_size()	returns amount of edges	O(1)
get_all_v	gets the node	O(1)
all_in_edges_of_node	get the edge	O(1)
all_out_edges_of_node	add the node to the graph	O(1)
get_mc	Content Cell	O(1)
add_edge	Get a collection of all nodes	O(1)
add_node	Get a collection edges from node	O(1)
remove_node	remove a node from the graph	O(K)
remove_edge	remove an edge from the graph	O(1)

Graph_Algo	Use	Run time
get_graph()	Returns the graph	O(1)
load_from_json	load the graph from json format	O(V+E)
save_to_json	save the graph in json format	O(V+E)
shortest_path	shortest path between two given nodes and a list of the path	O(n^2)
connected_component	returns the strongly connected component which that node is a part of	O(V+E)
connected_components	returns a list of all the strongly connected components	O(V(V+E))
plot_graph	plot the graph using mathploblib	O(V+E)

Installation

Copy the repository

git clone

Overview

This project uses varias graph algorithms such as Breadth first search and Dijkstra's algorithm. More information can be found : https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

https://en.wikipedia.org/wiki/Breadth-first_search

https://en.wikipedia.org/wiki/Shortest_path_problem

Test

Use DiGraphTest.py & GraphAlgoTest.py

Common issues

Check the issues tab for more info.