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:
Phương thức forEach() trong java 8
Luồng Daemon (Daemon Thread) trong Java
Java Program to Implement Gale Shapley Algorithm
Apache Tiles Integration with Spring MVC
Java Program to Implement vector
wait() and notify() Methods in Java
Hướng dẫn Java Design Pattern – Adapter
Quick Guide on Loading Initial Data with Spring Boot
Initialize a HashMap in Java
Lập trình đa luồng với CompletableFuture trong Java 8
Java Program to Implement AA Tree
Java Program for Topological Sorting in Graphs
How to Read a File in Java
Guide to Escaping Characters in Java RegExps
Versioning a REST API
Getting Started with Forms in Spring MVC
Spring @RequestMapping New Shortcut Annotations
Java Program to Implement the Edmond’s Algorithm for Maximum Cardinality Matching
Extra Login Fields with Spring Security
Spring Cloud – Securing Services
Posting with HttpClient
LinkedHashSet trong Java hoạt động như thế nào?
Java Program to Represent Graph Using Linked List
Java program to Implement Tree Set
Java Program to Implement the Binary Counting Method to Generate Subsets of a Set
Simultaneous Spring WebClient Calls
Stack Memory and Heap Space in Java
Java Optional as Return Type
A Guide to Apache Commons Collections CollectionUtils
File Upload with Spring MVC
Guide to Spring Cloud Kubernetes
Spring Boot - Google Cloud Platform