Java Design a program in Java that performs a topological sort on a directed gra

Question

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 < number of vertices) cycle detected

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."

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 < number of vertices) cycle detected

Explanation / Answer

program :

   import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;

public class TopologicalSort
{
private Stack<Integer> stack;

public TopologicalSort()
{
stack = new Stack<Integer>();
}

public int [] topological(int adjacency_matrix[][], int source) throws NullPointerException
{
int number_of_nodes = adjacency_matrix[source].length - 1;
int[] topological_sort = new int [number_of_nodes + 1];
int pos = 1;
int j ;
int visited[] = new int[number_of_nodes + 1];
int element = source;
int i = source;
visited[source] = 1;
stack.push(source);

while (!stack.isEmpty())
{
element = stack.peek();
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 1)
{
if (stack.contains(i))
{
System.out.println("TOPOLOGICAL SORT NOT POSSIBLE");
return null;
}
}
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
stack.push(i);
visited[i] = 1;
element = i;
i = 1;
continue;
}
i++;
}
j = stack.pop();  
topological_sort[pos++] = j;
i = ++j;
}
return topological_sort;
}  

public static void main(String...arg)
{
int number_no_nodes, source;
Scanner scanner = null;
int topological_sort[] = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
number_no_nodes = scanner.nextInt();

int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];
System.out.println("Enter the adjacency matrix");
   for (int i = 1; i <= number_no_nodes; i++)
for (int j = 1; j <= number_no_nodes; j++)
adjacency_matrix[i][j] = scanner.nextInt();

System.out.println("Enter the source for the graph");
source = scanner.nextInt();

System.out.println("The Topological sort for the graph is given by ");
TopologicalSort toposort = new TopologicalSort();
topological_sort = toposort.topological(adjacency_matrix, source);
System.out.println();
for (int i = topological_sort.length - 1; i > 0; i-- )
{
if (topological_sort[i] != 0)
System.out.print(topological_sort[i]+" ");
}   
}catch(InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}catch(NullPointerException nullPointer)
{
}
scanner.close();
}
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.