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:
Query Entities by Dates and Times with Spring Data JPA
Java Program to Check whether Graph is a Bipartite using 2 Color Algorithm
Convert XML to JSON Using Jackson
Vòng lặp for, while, do-while trong Java
Java Program to Implement Sorted Circular Doubly Linked List
Java Program to Implement Ternary Search Algorithm
Java Program to Implement LinkedBlockingQueue API
Spring Boot - OAuth2 with JWT
Tránh lỗi NullPointerException trong Java như thế nào?
Guide to java.util.concurrent.BlockingQueue
Java Program to Implement PriorityQueue API
Java Program to Implement Ternary Heap
Java Program to Find the GCD and LCM of two Numbers
Multipart Upload with HttpClient 4
Bootstrapping Hibernate 5 with Spring
Guide to java.util.concurrent.Locks
Java Program to Implement Adjacency List
HttpClient Connection Management
Java Program to Implement Bucket Sort
Java Program to Implement the Edmond’s Algorithm for Maximum Cardinality Matching
Java Program to Find Basis and Dimension of a Matrix
Java Program to Implement Efficient O(log n) Fibonacci generator
Date Time trong Java 8
Introduction to Spring Security Expressions
Getting Started with Stream Processing with Spring Cloud Data Flow
Apache Camel with Spring Boot
Setting a Request Timeout for a Spring REST API
HttpClient 4 – Send Custom Cookie
Java Program to Implement Kosaraju Algorithm
Summing Numbers with Java Streams
Java Program to implement Circular Buffer
Functional Interfaces in Java 8