# CSE222/505-Homework 7- Create directed acyclic graph have random weight Solved

30.00 \$

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: .  zip solution files instantly, after Payment

## Description

Rate this product

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.

1. Run the DFS algorithm starting from vertex 1, and draw the DFS tree.
2. 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