Description
Homework 07
Q1: Create directed acyclic graph have random weight (v=10, e=20), plot this graph using plot_graph function. Prove that using is_undirected and is_acyclic_graph functions. Then run shortest_path function on this graph, use least 3 different label pair (shortest_path(g,v1,v2), shortest_path(g,v3,v4), ……)
Q2: Create undirected and acyclic graph have no weight (v=15), plot this graph using plot_graph function. Prove that using is_undirected and is_acyclic_graph functions. Then run is_connected function on this graph, use least 3 different label pair ( is_connected(g,v1,v2), is_connected(g,v3,v4), ……)
Q3: Create undirected and cyclic graph have no weight (v=10), plot this graph using plot_graph function. Prove that using is_undirected and is_acyclic_graph functions. Then run DepthFirstSearch and BreathFirstSearch functions on text book and plot spanning trees.
Q4: This answer of this question should be only 1 page. Explain what is the differencies of BFS and DFS. (usage areas, advantages, …). Consider the undirected graph below which is represented by its adjacency matrix.
- Run the DFS algorithm starting from vertex 1, and draw the DFS tree.
- Run the BFS algorithm starting from vertex 1, and draw the BFS tree.
- Input – g, a graph object; v1, a vertex label in g; v2, a vertex label in g.
- Output – TRUE if there is a path from v1 to v2 in g, FALSE if not.
- Description – Determine if there is any path between vertex v1 and vertex v2 in graph g. If v1 or v2 are not in g then throw an error.
Function – shortest_path
- Input – g, graph object; v1, a vertex label in g; v2, a vertex label in g.
- Output – path, a vector of the names of vertices that make up the shortest path, in order. If there is no path between the vertices then return an empty vector; distance , total weight of path.
- Description – Find the shortest path from vertex v1 to vertex v2 using Dijkstra’s algorithm. Note that there may not be a unique solution for any given graph, you are only required to return one path.
Function – is_undirected
- Input – g, a graph object.
- Output – TRUE if g is undirected, FALSE if not.
- Description – Check if the graph object is undirected, this is true if all directed edges have a complementary directed edge with the same weight in the opposite direction.
Function – is_acyclic_graph
- Input – g, a graph object.
- Output – TRUE if g is undirected, FALSE if not.
- Description -The graph may or may not have cycles. To check do a graph traversal (BFS or DFS).
Function – plot_graph
- Input – g, a graph object
- Output – plot showing all vertices (labeled) and edges.
- Description – This function should be able to take any graph object and produce a reasonably attractive visual representation of that graph. Your algorithm should make use edge weights to layout the distance between vertices.
Book Student source code:
http://bcs.wiley.com/he-bcs/Books?action=resource&bcsId=5643&itemId=0470128704&reso urceId=21295
Note:
- Obey OOP principles and clean code standarts.
- Write a main and maintest for each function
- Your submission is studentnumber.zip and include following files:
- o intelliJ project file
○ Q1 folder
○ Q2 folder
○ Q3 folder
- o Report.pdf
- o Javadoc
- The report must be in format “ReportFormat_hw7”
