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.
package com.maixuanviet.graph; import java.util.InputMismatchException; import java.util.Scanner; import java.util.Stack; public class DAGLinearExtension { private Stack<Integer> stack; public DAGLinearExtension() { stack = new Stack<Integer>(); } public int[] topological(int adjacency_matrix[][], int source) throws NullPointerException { int number_of_nodes = adjacency_matrix.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 = 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; System.out .println("Linear extension of a DAG is its topological reperesentation."); 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 "); DAGLinearExtension toposort = new DAGLinearExtension(); topological_sort = toposort.topological(adjacency_matrix, source); for (int i = topological_sort.length - 1; i > 0; i--) { if (topological_sort[i] != 0) System.out.print(topological_sort[i] + "\t"); } } catch (InputMismatchException inputMismatch) { System.out.println("Wrong Input format"); } catch (NullPointerException nullPointer) { } scanner.close(); } }
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
Related posts:
Spring Boot - Tracing Micro Service Logs
Java Multi-line String
Spring Boot Actuator
Java Program to Print the Kind of Rotation the AVL Tree is Undergoing
Unsatisfied Dependency in Spring
Java Program to Find Strongly Connected Components in Graphs
Phương thức tham chiếu trong Java 8 – Method References
Java Program to Use the Bellman-Ford Algorithm to Find the Shortest Path
Java Program to Implement Quick Sort Using Randomization
Guide to the Volatile Keyword in Java
The Difference Between Collection.stream().forEach() and Collection.forEach()
Hướng dẫn Java Design Pattern – Null Object
Java Program to Construct K-D Tree for 2 Dimensional Data
Java Program to Implement Double Order Traversal of a Binary Tree
Spring Boot: Customize the Jackson ObjectMapper
Handling URL Encoded Form Data in Spring REST
Java Program to Perform Complex Number Multiplication
Exploring the Spring 5 WebFlux URL Matching
Converting Between a List and a Set in Java
Java Program to Implement Uniform-Cost Search
Java Program to Perform Quick Sort on Large Number of Elements
Apache Tiles Integration with Spring MVC
Converting a Stack Trace to a String in Java
Check If Two Lists are Equal in Java
Lớp TreeMap trong Java
Java Program to implement Associate Array
Java Program to Implement Caesar Cypher
Java – Combine Multiple Collections
Spring Data Java 8 Support
Biến trong java
Giới thiệu Json Web Token (JWT)
Understanding Memory Leaks in Java