Java Programming Write a Java program that performs a topological sort on a dire

Question

Java Programming

Write a Java program that performs a topological sort on a directed graph. The graph layout will be read using System.in as described below. You will store this graph in an adjacency matrix, and print output to System.out according to the directions below.

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.

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  

Sample Output

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

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

Explanation / Answer

// I have assumed user input here, and not file input. You can test it directly through concole :)

class Test
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter the number of nodes in the graph");
int number=sc.nextInt();
System.out.println("Enter the number of source dest pairs: ");
int number_2=sc.nextInt();
boolean graph[][] = new int[number + 1][number + 1];

for(int i=0;<number_2;i++)
{
String new_number=sc.nextLine();
String tokens[]=new_number.split(" ");
int source=tokens[0];
int destination=tokens[1];
graph[source][destination]=true;
}

//Calculating indegree of each node
int indegree[]new int[number];
for(int i=0;i<number;i++)
{
   for(int j=0;j<number;j++)
   {
           if(graph[i][j])
           {
                   indegree[j]=indegree[j]+1;
           }
   }
}

int output_list_number=0;
for(int i=0;i<number;i++)
{
   if(indegree[i]==0)
   {
       for(int j=0;j<n;j++)
       {
               if(graph[i][j])
                   {
                       indegree[j]=indegree[j]-1;
                   }
                   indegree[i]=-1;   // to say that we visited the node.
                   output_list_number=output_list_number+1;
       }
   }
}

if(output_list_number<number)
System.out.println("The cycle is detected. This graph is cyclic");

}
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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