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:
Java Program to Implement LinkedHashMap API
Java – Get Random Item/Element From a List
Reversing a Linked List in Java
Java Program to Check whether Directed Graph is Connected using DFS
Comparing Two HashMaps in Java
Tạo chương trình Java đầu tiên sử dụng Eclipse
Guide to java.util.concurrent.BlockingQueue
Spring Cloud Series – The Gateway Pattern
Quick Guide to Spring MVC with Velocity
The DAO with JPA and Spring
A Custom Data Binder in Spring MVC
Spring Cloud Bus
How to Delay Code Execution in Java
Java Program to Generate All Possible Combinations Out of a, b, c, d, e
How to Add a Single Element to a Stream
Spring MVC + Thymeleaf 3.0: New Features
Apache Commons Collections SetUtils
Calling Stored Procedures from Spring Data JPA Repositories
Converting Between an Array and a Set in Java
Consuming RESTful Web Services
Java Program to Solve the Fractional Knapsack Problem
A Guide to JUnit 5
Java Program to Implement RoleList API
Spring Security Basic Authentication
REST Web service: Upload và Download file với Jersey 2.x
Java – Delete a File
Java Program to Find the Nearest Neighbor Using K-D Tree Search
Spring WebClient Filters
Limiting Query Results with JPA and Spring Data JPA
Java Program to Implement Coppersmith Freivald’s Algorithm
Java Program to Create a Minimal Set of All Edges Whose Addition will Convert it to a Strongly Conne...
Java Program to Find Inverse of a Matrix