This is a java program to find feedback vertex set. This is the set which contains vertices when removed from graph, graph becomes Directed acuclic graph.
Here is the source code of the Java Program to Find a Good Feedback Vertex Set. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
package com.maixuanviet.hardgraph; import java.util.HashMap; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Scanner; class GraphLL { private Map<Integer, List<Integer>> adjacencyList; public GraphLL(int v) { adjacencyList = new HashMap<Integer, List<Integer>>(); for (int i = 1; i <= v; i++) adjacencyList.put(i, new LinkedList<Integer>()); } public void setEdge(int from, int to) { if (to > adjacencyList.size() || from > adjacencyList.size()) System.out.println("The vertices does not exists"); /* * List<Integer> sls = adjacencyList.get(to); * sls.add(from); */ List<Integer> dls = adjacencyList.get(from); dls.add(to); } public List<Integer> getEdge(int to) { /* * if (to > adjacencyList.size()) * { * System.out.println("The vertices does not exists"); * return null; * } */ return adjacencyList.get(to); } public GraphLL checkDAG() { Integer count = 0; Iterator<Integer> iteratorI = this.adjacencyList.keySet().iterator(); Integer size = this.adjacencyList.size() - 1; while (iteratorI.hasNext()) { Integer i = iteratorI.next(); List<Integer> adjList = this.adjacencyList.get(i); if (count == size) { return this; } if (adjList.size() == 0) { count++; Iterator<Integer> iteratorJ = this.adjacencyList.keySet() .iterator(); while (iteratorJ.hasNext()) { Integer j = iteratorJ.next(); List<Integer> li = this.adjacencyList.get(j); if (li.contains(i)) { li.remove(i); } } this.adjacencyList.remove(i); iteratorI = this.adjacencyList.keySet().iterator(); } } return this; } public void printGraph() { System.out.println("The Graph is: "); Iterator<Integer> iterator = this.adjacencyList.keySet().iterator(); while (iterator.hasNext()) { Integer i = iterator.next(); List<Integer> edgeList = this.getEdge(i); if (edgeList.size() != 0) { System.out.print(i); for (int j = 0; j < edgeList.size(); j++) { System.out.print(" -> " + edgeList.get(j)); } System.out.println(); } } } public boolean getFeedbackVertexSet(int v) { boolean flag = false; int[] visited = new int[v + 1]; Iterator<Integer> iterator = this.adjacencyList.keySet().iterator(); System.out.print("The set of vertices in feedback vertex set: "); while (iterator.hasNext()) { Integer i = iterator.next(); List<Integer> list = this.adjacencyList.get(i); visited[i] = 1; if (list.size() != 0) { for (int j = 0; j < list.size(); j++) { if (visited[list.get(j)] == 1) { flag = true; System.out.println(list.get(j) + " "); } else { visited[list.get(j)] = 1; } } } } return flag; } } public class FeedbackVertexSet { public static void main(String args[]) { int v, e, count = 1, to, from; Scanner sc = new Scanner(System.in); GraphLL glist; try { System.out.println("Enter the number of vertices: "); v = sc.nextInt(); System.out.println("Enter the number of edges: "); e = sc.nextInt(); glist = new GraphLL(v); System.out.println("Enter the edges in the graph : <from> <to>"); while (count <= e) { to = sc.nextInt(); from = sc.nextInt(); glist.setEdge(to, from); count++; } glist.printGraph(); GraphLL modified = glist.checkDAG(); if (modified.getFeedbackVertexSet(v) == false) { System.out.println("None"); } } catch (Exception E) { System.out .println("You are trying to access empty adjacency list of a node."); } sc.close(); } }
Output:
Enter the number of vertices: 6 Enter the number of edges: 7 Enter the edges in the graph : <from> <to> 1 2 2 3 2 4 4 5 5 6 6 4 6 3 The Graph is: 1 -> 2 2 -> 3 -> 4 4 -> 5 5 -> 6 6 -> 4 -> 3 The set of vertices in feedback vertex set: 4
Related posts:
Hướng dẫn Java Design Pattern – Abstract Factory
Java Program to Implement Shell Sort
Introduction to Spring Data REST
Spring – Injecting Collections
Comparing Two HashMaps in Java
Debug a JavaMail Program
Spring Boot - Sending Email
LinkedList trong java
Overflow and Underflow in Java
Java Program to Perform Searching Using Self-Organizing Lists
Convert String to Byte Array and Reverse in Java
Basic Authentication with the RestTemplate
A Guide to LinkedHashMap in Java
Spring Cloud – Adding Angular
Convert String to int or Integer in Java
Spring Cloud – Securing Services
Command-Line Arguments in Java
How to Break from Java Stream forEach
A Quick Guide to Spring Cloud Consul
Converting String to Stream of chars
A Comparison Between Spring and Spring Boot
Pagination and Sorting using Spring Data JPA
Hướng dẫn sử dụng luồng vào ra ký tự trong Java
Java Program to implement Priority Queue
Spring Cloud AWS – Messaging Support
Java Program to Implement Iterative Deepening
Spring Boot Tutorial – Bootstrap a Simple Application
Java Program to Implement Branch and Bound Method to Perform a Combinatorial Search
Lớp Properties trong java
Apache Commons Collections SetUtils
Spring Boot: Customize Whitelabel Error Page
Using the Map.Entry Java Class