Description:
Given a directed graph, if we want to see whether it has a topological order, we need to check if it has a cycle first. Only when it is a DAG, we can find a topological order for this graph. In this project, we want to combine these two things together (detecting a cycle and finding a topological order).
Background: see image.
The above graph shows that you cannot find a topological order because this graph has a cycle. Therefore, you need to make sure there is no cycle in this graph; otherwise the topological finding algorithm does not apply.
Requirements:
1.(Input) The input comes from a text le that stores the adjacency matrix of a graph. Your program will take the le name of an input as a command-line argument. Then your program will read the content of the le line by line, in which each row corresponds to one row of the adjacency matrix of a graph.
2.(Validation) Before we process the graph, we need to validate the data to make sure that the given data corresponds to the adjacency matrix of a graph. Basically we need to check the following items:
(Square Matrix) Each row of the data le has a sequence of integers separated by a space character. Make sure that the number of rows equals the number of columns. Otherwise display an error message.
(Bit Value Entries) Check if each entry of the matrix takes the bit value: 0 or 1. If not, display an error message.
(No Self-Loops) Although a directed graph is allowed to have a self-loop, a DAG cannot have any self-loop. We just check that all the diagonal entries must be 0. Otherwise display an error message.
3.(Detecting a cycle) When we apply the DFS algorithm in finding a topological order, we need to add a step to check if there is a cycle. The cycle detection step is based on the following observations:
The DFS algorithm will not miss any cycle. That means, whichever vertex you start with, if you hit one vertex in a cycle, the DFS will go through the whole cycle in certain way.
When you traverse a DFS tree, sometimes you need to backtrack to some previous vertices. A backtracking action may add some complexity if you want to recover a cycle. (I will explain this observation in a video.)
After you find a cycle, print out the vertex sequence of the cycle with an error message and stop the program.
4.(Output) If you do not encounter any cycle when you traverse the DFS forest, you have a valid DAG, and you can find a valid topological order. At the end, you print out the vertices in the order of a topological order as your solution.
5.(Testing) I will give you my testing file.