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 Give an Implementation of the Traditional Chinese Postman Problem
Use Liquibase to Safely Evolve Your Database Schema
Java Program to Implement Gauss Jordan Elimination
Java Program to Create a Balanced Binary Tree of the Incoming Data
Hướng dẫn kết nối cơ sở dữ liệu với Java JDBC
Spring Boot - Tomcat Deployment
Java Program to Implement Borwein Algorithm
ExecutorService – Waiting for Threads to Finish
Uploading MultipartFile with Spring RestTemplate
Java Program to Check whether Directed Graph is Connected using BFS
Java – Reader to Byte Array
Spring Boot - Batch Service
Java Program to Find Whether a Path Exists Between 2 Given Nodes
Guide to java.util.Formatter
Custom HTTP Header with the HttpClient
Intro to Spring Boot Starters
Updating your Password
Life Cycle of a Thread in Java
Java Program to Implement Aho-Corasick Algorithm for String Matching
Object cloning trong java
Phương thức tham chiếu trong Java 8 – Method References
Control the Session with Spring Security
Java Program to Implement Double Ended Queue
A Guide to the ViewResolver in Spring MVC
Deque và ArrayDeque trong Java
Hướng dẫn Java Design Pattern – Bridge
Java Program to Implement ConcurrentHashMap API
Understanding Memory Leaks in Java
Java Program to Implement the Bin Packing Algorithm
Java Program to Implement the Vigenere Cypher
Guide to the Java Clock Class
Java Program to Find Strongly Connected Components in Graphs