CS69001: One-Step Reachability Graph - IT Assessment Answer

IT Assessment Task

Let G = (V,E) be a connected undirected graph, and let s,t be two distinct vertices of G. Each vertex v ∈ V stores a positive integer l(v). Two robots are initially sitting at vertices s and t. They then enter a loop. Let u and v be the current positions of the two robots (initially u = s and v = t). The robots read the two integers l(u) and l(v).

The first robot then moves along a path in G of length equal to l(u), starting from u. Likewise, the second robot starts from v, and moves along a path in G of length equal to l(v). If the new positions of the robots are u ′ and v ′ , we say that the robots move from (u, v) to (u ′ , v ′ ) in one step or iteration.

Your task is to find out whether the two robots, starting initially from s and t, can switch their positions, that is, can reach t and s simultaneously after the same number of steps. Notice that in a single step, no path of either robot is allowed to contain repeated vertices. However, the paths of each robot in different steps (iterations) may contain repeated vertices.

If in some step, a path of the desired length does not exist, then the problem definitely has no solution. Assuming that the problem is solvable, we ask two questions.

1. What is the minimum number of steps (that is, iterations) needed for the robots to switch positions?

2. The effort of each robot is the sum of the lengths of the paths it traverses in all the iterations. What is the minimum combined effort (the sum of the efforts of the two robots) needed for the robots to change their positions from (s,t) to (t,s)?

You consider two situations. Let (u, v) be the positions of the robots at the end of an iteration.

(i) It is allowed to have u = v at the end of one or more iterations.

(ii) It is never allowed to have u = v.

Part 1:

Declare and print a graph Define a suitable data type to store a graph G = (V,E) (directed or undirected) in the adjacency-list format. The structure should store the number n of vertices of G, the number m of edges of G, and n headers to the linked lists of neighbors of the vertices. In this assignment, each vertex v is needed to store the path length l

(v), so your graph should also contain an integer array of size n. Assume that V = {0,1,2,...,n−1}.

Write a function prngraph to print a graph G in the format shown in the sample output. You first print n and m. Then, for each vertex v, you print its weight followed by its neighbors.

Part 2:

Generate the one-step reachability graph GR The user enters the input undirected graph G = (V,E) in the main function. From this, you generate a graph GR = (VR,ER) as follows. We have VR = V. Let u ∈ VR = V. If a robot sits at u at some point of time, it can reach a vertex v from u in one step if there is a u, v path of length l(u). If and only if this is the case, include the edge (u, v) in ER. For each v ∈ V, copy l(v) from G to GR. Write a function genrgraph to generate GR from G.

Notice that GR is a directed graph (even though G is undirected).

Part 3:

Generate the one-step simultaneous reachability graph GS You need to track the simultaneous movements of the two robots. This is captured by a bigger graph GS = (VS,ES), and can be generated from GR. Take VS = VR ×VR = V ×V. Renumber the pair (u, v) of vertices of GS as nu + v, so VS = {0,1,2,...,n 2 − 1}. Include the edge ((u, v),(u ′ , v ′ )) in ES if and only if (u,u ′ ) ∈ ER and (v, v ′ ) ∈ ER (so ES is essentially ER ×ER). Finally, store l(u, v) in GS as l(u) +l(v). Write a function gensgraph to generate GS from GR.

Notice that GS is again a directed graph.

Part 4:

Minimize the number of steps The initial position of the robots is (s,t), and their final position is (t,s). Run a BFS in GS from (s,t) . If (t,s) is ever reached, the minimum number of steps is the level of (t,s) in the BFS tree. Print the unique — Page 1 of 4 — path from (s,t) to (t,s) in the BFS tree, its length, and its cost (combined total effort of the robots on this path). If (t,s) is never reached from (s,t), then the problem has no solution; report that.

Your BFS function should be able to handle both the situations (i) and (ii) described above. We start with the assumption that s 6= t. In situation (i), your BFS is allowed to visit nodes (u,u). In situation (ii), you initially mark all nodes (u,u) as visited so you never try to revisit them in the BFS loop. Pass a flag to your BFS function to indicate which situation you are dealing with.

Part 5:

Minimize the total combined effort While BFS traversal can minimize the number of steps, it may fail to give the correct solution when the goal is to minimize the total combined effort of the robots. You need to run a single-source-shortest-path (SSSP) algorithm in GS with (s,t) acting as the source. Implement Dijkstra’s algorithm to this end. This algorithm requires edges to be weighted, but we stored weights in vertices.

This is not a problem. For a directed edge e = ((u, v),(u ′ , v ′ )) ∈ ES, the weight is weight(e) = l(u, v) = l(u)+l(v), and is dependent solely on the starting vertex (u, v).

As in Part 4, pass a flag to your SSSP function to indicate which of the situations (i) and (ii) you are dealing with. In situation (ii), you do not consider vertices of the form (u,u) even though GS stores information about these vertices. After you find a shortest (s,t) → (t,s) path, print its cost and also its length (number of steps). If in the end, the distance of (t,s) from (s,t) remains ∞, then there is no (s,t) → (t,s) path in GS.

This IT Assessment has been solved by our IT experts at My Uni Paper. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK & US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics & referencing style.

Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.