Graph's Algorithms

DWGraph_Algo

Implemets dw_graph_algorithms.

Data Structor & Fields:

• A DWGraph_DS graph which represents the graph.

Functions:

• A regular constructor.
• An override of the equals function- allowing to compare two graphs. Used in tests.
• An init function used to initialize the graph with a given graph.
• getGraph function that returns the graph.
• Copy function that copies the graph to a new graph by number of vertices, number of edges, each edge and each vertex, uses copy constructor in each class.
• isConnected returns true if the graph is connected and false otherwise. Uses the Tarjan's algorithm. Check out Aditional section - "Tarjan's algorithm".
• getComponents returns a list of lists. each inner list contains all of the vertices in the component. Uses the Tarjan's algorithm. Check out Aditional section - "Tarjan's algorithm".
• shortestPathDist returns the distance between two vertices and -1 if there is no valid path between them. Uses the Dijkstra's algorithm. Check out Aditional section - "Dijkstra's algorithm".
• shortestPath returns a list of vertices between the source vertex and the destination vertex. Uses the Dijkstra's algorithm. Check out Aditional section - "Dijkstra's algorithm".
• Save function is the function that allows to save the current graph into a Json format. The function uses the JsonWriter library to perform- uses functions such as beginArray and beginObject to creat the order and separation between the saved objects.
• Load function is the function that allows to load a given Json format graph into a DWGraph_Algo object. The funcion uses the GsonBuilder library to perform- also uses the GraphJsonDesrializeltion class that sets the logic to read from the Json and bulid the object. Check out Aditional section - "JsonDeserializer".

Aditional:

Tarjan's algorithm: The Tarjan class implemets the Tarjan's algorithms.

Data Structor & Fields:

• A DWGraph_DS g which represents the graph.
• int time that sets the time of visiting the vertex.
• List<List<node_data>> components that represents the components of the graph.
• Stack s of NodeData uses to check which vertices are left to visit.

Functions:

• A regular constructor.
• The Tarjan's algorithm- goes over each vertex in the graph and perform the DFS algorithms if the spesific vertex has not been visited.
• DFS algorithm: sets the tag and the isVis fields of the given vertex and pushes to the stack. goes over all of the neighbors of the vertex and perform the DFS algorithms on them if they hasn't been visited. Sets the component root and create a new one if needed.
• isConnected function count down the number of components and return true if the number is one.
• getComponents return the list of components.

Dijkstra's algorithm

JsonDeserializer