Java Program to Create a Random Linear Extension for a DAG

«
»
This is a java program to create a random linear extension of DAG. Linear extension of DAG is nothing but topological sorting in simple terms.

Here is the source code of the Java Program to Create a Random Linear Extension for a DAG. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1.  
  2. package com.sanfoundry.graph;
  3.  
  4. import java.util.InputMismatchException;
  5. import java.util.Scanner;
  6. import java.util.Stack;
  7.  
  8. public class DAGLinearExtension
  9. {
  10.     private Stack<Integer> stack;
  11.  
  12.     public DAGLinearExtension()
  13.     {
  14.         stack = new Stack<Integer>();
  15.     }
  16.  
  17.     public int[] topological(int adjacency_matrix[][], int source)
  18.             throws NullPointerException
  19.     {
  20.         int number_of_nodes = adjacency_matrix[source].length - 1;
  21.         int[] topological_sort = new int[number_of_nodes + 1];
  22.         int pos = 1;
  23.         int j;
  24.         int visited[] = new int[number_of_nodes + 1];
  25.         int element = source;
  26.         int i = source;
  27.         visited[source] = 1;
  28.         stack.push(source);
  29.         while (!stack.isEmpty())
  30.         {
  31.             element = stack.peek();
  32.             while (i <= number_of_nodes)
  33.             {
  34.                 if (adjacency_matrix[element][i] == 1 && visited[i] == 1)
  35.                 {
  36.                     if (stack.contains(i))
  37.                     {
  38.                         System.out.println("TOPOLOGICAL SORT NOT POSSIBLE");
  39.                         return null;
  40.                     }
  41.                 }
  42.                 if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
  43.                 {
  44.                     stack.push(i);
  45.                     visited[i] = 1;
  46.                     element = i;
  47.                     i = 1;
  48.                     continue;
  49.                 }
  50.                 i++;
  51.             }
  52.             j = stack.pop();
  53.             topological_sort[pos++] = j;
  54.             i = ++j;
  55.         }
  56.         return topological_sort;
  57.     }
  58.  
  59.     public static void main(String... arg)
  60.     {
  61.         int number_no_nodes, source;
  62.         Scanner scanner = null;
  63.         int topological_sort[] = null;
  64.         System.out
  65.                 .println("Linear extension of a DAG is its topological reperesentation.");
  66.         try
  67.         {
  68.             System.out.println("Enter the number of nodes in the graph");
  69.             scanner = new Scanner(System.in);
  70.             number_no_nodes = scanner.nextInt();
  71.             int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];
  72.             System.out.println("Enter the adjacency matrix");
  73.             for (int i = 1; i <= number_no_nodes; i++)
  74.                 for (int j = 1; j <= number_no_nodes; j++)
  75.                     adjacency_matrix[i][j] = scanner.nextInt();
  76.             System.out.println("Enter the source for the graph");
  77.             source = scanner.nextInt();
  78.             System.out
  79.                     .println("The Topological sort for the graph is given by ");
  80.             DAGLinearExtension toposort = new DAGLinearExtension();
  81.             topological_sort = toposort.topological(adjacency_matrix, source);
  82.             for (int i = topological_sort.length - 1; i > 0; i--)
  83.             {
  84.                 if (topological_sort[i] != 0)
  85.                     System.out.print(topological_sort[i] + "\t");
  86.             }
  87.         }
  88.         catch (InputMismatchException inputMismatch)
  89.         {
  90.             System.out.println("Wrong Input format");
  91.         }
  92.         catch (NullPointerException nullPointer)
  93.         {
  94.         }
  95.         scanner.close();
  96.     }
  97. }

Output:

$ javac DAGLinearExtension.java
$ java DAGLinearExtension
 
Linear extension of a DAG is its topological reperesentation.
Enter the number of nodes in the graph
6
Enter the adjacency matrix
0 1 0 0 0 1
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 1
0 0 1 0 0 0 
Enter the source for the graph
1
The Topological sort for the graph is given by 
1	2	4	5	6	3

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.