COP 3503 TopoPath

Abstract

In this assignment, you will determine whether an arbitrary directed graph contains a topopath - an ordering of its vertices that simultaneously corresponds to a valid path in the graph and a valid topological sort. More than anything, this program should serve as a relatively short critical thinking exercise.

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²). 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 thinking 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.

1. Problem Statement

Given a directed graph, determine whether it has a topopath - an ordering of its vertices that simultaneously corresponds to a valid path in the graph and a valid topological sort. For example: see image.

In G₁, the vertex ordering 1, 2, 3, 4 is a valid topological sort, but does not correspond to a valid path in the graph (i.e., 1 -> 2 -> 3 -> 4 is not a path in G₁). In fact, none of the topological sorts for G₁ correspond to actual paths through that graph.

In contrast, the vertex ordering 1, 2, 3, 4 corresponds to a valid path in G₂ (i.e., 1 -> 2 -> 3 -> 4 is an actual path in G₂), but is not a valid topological sort for the graph. None of the paths in G₂ orrespond to a valid topological sort of that graphs vertices.

In G₃, the ordering 1, 2, 3 corresponds to both a valid path (1 -> 2 -> 3) and a valid topological sort.

2. Input File Format

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, with a small twist: 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 files correspond to the graphs G₁, G₂, and G₃ that are pictured above:

g1.txt
4
1 3
2 3 4
1 4
0

g2.txt
4
1 2
1 3
1 4
1 2

g3.txt
3
1 2
1 3
0

3. Special Restriction: Runtime Requirement

Please note that you must implement a solution that is O(n²) where n = |V|. Recall from our formal definition of big-oh that a faster solution is still considered O(n²).

4. Method and Class Requirements

Implement the following methods in a class named TopoPath . Notice that all these methods are both public and static.

public static boolean hasTopoPath(String filename)
Open filename and process the graph it contains. If the graph has a topopath (explained above), return true. Otherwise, return false. The string filename will refer to an existing file, and it will follow the format indicated above. You may have your method throw exceptions as necessary. Note that this function must execute in O(n²) time.

public static double difficultyRating()
Return a double on the range 1.0 (ridiculously easy) through 5.0 (insanely difficult).

public static double hoursSpent()
Return an estimate (greater than zero) of the number of hours you spent on this assignment.