Lab: 39 - Topological Sorting

Assigned

Friday, 1 December 2023

The goal of this lab is to do tasks related to the topological sorting. Use the files that you already modified for Dijkstra’s Algorithm lab. In Graph.java class, the acyclic method computes the shortest weighted paths using the topological ordering.

Preparation

Before you start the lab use the Topological Sort(DFS) Visualization program from the University of San Francisco to confirm your understanding of the algorithm.

Read the acyclic method so you understand the algorithm.

If you find errors, warnings, or identify places that could use improvements, fix the code.

Critical path

The critical path between two vertices in a weighted directed acyclic graph is the path with the greatest sum of edge weights. In this graph, each vertex has a value equal to the sum of the edge weights of a path from a given start vertex to that vertex.

1. Inside Graph.java, define a method, called criticalPath, to compute the longest paths from a start vertex to the other vertices on the acyclic graphs and will return the vertex name with the longest path. Use the body of the acyclic method to compute the longestPath that will be used in criticalPath. Create the longestPath method then update the code as needed.
   • Do you need to change the vertex structure to compute the longest path instead of the shortest path?
   • You can find the critical path by considering the vertices one at a time in topological order. Start by computing the indegree value of the vertices.
   • When visiting or processing the vertices taken from the queue, for each vertex consider all the edges that leave the vertex.
     • For each of these edges, add the weight of the edge to the value of the source vertex on that edge.
     • For each edge, compare the sum with the value of the destination vertex.
     • Make the larger of these values the value of the destination vertex.
   • After all vertices have been visited, the largest value stored in a vertex will be cost of the longest path to that vertex.
2. Modify the processRequest method by asking users to enter a name for the algorithm that you implement for criticalPath. Note: Remember, when testing your program, it is not necessary to enter a destination node, criticalPath method will return the destination node/vertex.
3. What other changes are necessary to test your program successfully? Test criticalPath by finding the longest paths for the following weighted directed graph. Assume that A is a start vertex. Confirm that the critical path from A to I is 19.

Lab Submission

For your lab write up, include:

• (4 points) The source file Graph.java and a screenshot of the outcome after running your program.

Remember: Do not use magic numbers, write your code anticipating errors and print user-friendly error messages, all your public methods should be well documented (use Javadoc comments). Please include comments or organize your code and report in a way that will help the grader to find the answer to the exercises or posted questions.

For those with extra time

Topological ordering

(1 extra point) The topological sorting algorithm adds a vertex to a queue when there is not an incoming edge to the vertex. (That is, the vertex indegree is zero.) Now, suppose that the topological sorting adds a vertex to the queue when there is not an outgoing edge from that vertex (You may need to update Vertex and Edge to keep track of outgoing edges).

Write the method topologicalOrdering that displays the topological ordering of vertices in a graph using outdegree instead of indegree of vertices.

• The queue stores a vertex when its outdegree becomes zero.
• Use a stack stores a vertex when it is visited. Print the nodes using the stack to show a topological ordering of the vertices.

Test your method for the graph shown above.

• In a lab report, explain the changes in Graph.java to test the topologicalOrdering method and the console screenshot after running your program.
• The Graph.java file must include the topologicalOrdering method.