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:
Spring Data JPA Delete and Relationships
An Intro to Spring Cloud Task
Java Program to Encode a Message Using Playfair Cipher
Creating a Custom Starter with Spring Boot
Lập trình hướng đối tượng (OOPs) trong java
Adding a Newline Character to a String in Java
Java Program to Solve the 0-1 Knapsack Problem
Tính đa hình (Polymorphism) trong Java
Static Content in Spring WebFlux
Java Program to Implement Knapsack Algorithm
Hướng dẫn sử dụng Lớp FilePermission trong java
REST Web service: Basic Authentication trong Jersey 2.x
Spring Boot - File Handling
Java Program to Implement Sorted Vector
Java Program to Implement Euler Circuit Problem
Weak References in Java
Java Program to Implement Stack using Linked List
Phương thức forEach() trong java 8
Serialization và Deserialization trong java
Spring Security Remember Me
Sử dụng CyclicBarrier trong Java
A Quick JUnit vs TestNG Comparison
Check if a String is a Palindrome in Java
Updating your Password
Simple Single Sign-On with Spring Security OAuth2
Java Program to Implement the Hungarian Algorithm for Bipartite Matching
Hướng dẫn sử dụng luồng vào ra ký tự trong Java
Batch Processing with Spring Cloud Data Flow
Java – Byte Array to Reader
Jackson Date
Java Program to Find Number of Articulation points in a Graph
Đồng bộ hóa các luồng trong Java