In this assignment, you will determine whether an arbitrary directed graph has a valid topological sort in which some vertex, x, comes before some other vertex, y.
You will gain experience reading graphs from an input file, representing them computationally, and writing graph theory algorithms. You will also solidify your understanding of topological sorts, sharpen your problem solving skills, and get some practice at being clever, because your solution to this problem must be O(n 2 ). In coming up with a solution, I recommend focusing first on developing a working algorithm, and then analyzing its runtime. (Focusing too much on the runtime restriction might cloud your thought as you cook up a solution to this problem.)
If you use any code that I have given you so far in class, you should probably include a comment to give me credit. The intellectually curious student will, of course, try to write the whole program from scratch.
Given a directed graph, G, and two integers, x and y, determine whether G has a valid topological sort in which vertex x comes before vertex y. (Notice that the problem does not ask whether x comes directly before y.) For example: see image.
In G 1 , there is a valid topological sort in which vertex 2 comes before vertex 1 (2, 1, 3, 4). There is also a valid topological sort in which vertex 1 comes before vertex 2 (1, 2, 3, 4). Both of those are also valid topological sorts in which vertex 2 comes before vertex 4. (Notice that vertex 2 does not have to come directly before vertex 4.) However, there is no valid topological sort in which vertex 4 comes before vertex 1.
Each input file contains a single digraph. The first line contains a single integer, n 2, indicating the number of vertices in the graph. (Vertices in these graphs are numbered 1 through n.) The following n lines are the adjacency lists for each successive vertex in the graph. Each adjacency list begins with a single non-negative integer, k, indicating the number of vertices that follow. The list of vertices that follows will contain k distinct integers (i.e., no repeats) on the range 1 through n. For example, the following text file corresponds to the graph G 1 that is pictured above: see image.
Implement the following methods in a class named ConstrainedTopoSort .
public ConstrainedTopoSort(String filename)
This constructor opens the file named filename and reads the graph it contains into either an adjacency matrix or adjacency list. We will process multiple xy queries for this graph, but we only want to load it into memory once. This method should throw exceptions as necessary.
public boolean hasConstrainedTopoSort(int x, int y)
Given integers x and y such that 1 x n and 1 y n, if this graph has a valid topological sort in which vertex x precedes vertex y, return true. Otherwise, return false. Do this in O( n 2 ) time.
public static double difficultyRating()
Return a double on the range 1.0 (ridiculously easy) to 5.0 (insanely difficult).
public static double hoursSpent()
Return an estimate (greater than zero) of the number of hours you spent on this assignment.
Runtime Requirement: Please note that you must implement a solution that is O( n 2 ), where n = |V|. Recall from our formal definition of Big-Oh that a faster solution is still considered O(n 2 ).