Java

Design a program in Java that performs a topological sort on a directed graph. Read the graph using System.in. Store the graph in an adjacency matrix, and print output to System.out.

Input

The first line of input will contain the count of vertices in the graph, this is used to allocate the adjacency matrix.

For example: boolean graph[][] = new boolean[count][count];

The remainder of the file are lines, one for each edge. Each line contains only two integers: source vertex and destination vertex. When the user enters a blank line it should run the program. When the user enters no information at all, the program should terminate.

For each pair, set graph[source][destination]=true. For example, input like this:

5

0 1

2 4

1 4

0 3

Would correspond to a graph like this:

Data structure

You do not need to implement a Graph class. Simply write a main method that creates this boolean graph array and operates on it.

Topological sort algorithm

This algorithm proceeds by calculating the indegree of each vertex. Store this in an int[]. The indegree of a vertex is the number of incoming edges, calculable by adding up all the true values in that vertices matrix column (assuming the matrix rows indicate source vertices).

As your algorithm proceeds, take care not to modify the adjacency matrix.

Try building a list of vertices in the desired order. This will allow you to determine if a cycle exists before printing anything out.

The algorithm functions as follows:

while there is a vertex with indegree 0:

for each vertex V with indegree zero:

subtract 1 from the indegree of every vertex reachable from V

set indegree of V to -1 this indicates we visited V

if (length of the output list

Your program must either print out a valid topological sort of the graph, or print This graph is cyclic. Sample Output

With the input specified above, several outputs are valid. Two examples:

0

1

3

2

4

or...

2

0

3

1

4

But, if the input is like this:

4

0 1

1 2

2 3

3 1

The output should be

"This graph is cyclic."