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:
Guide to BufferedReader
Java Program to Implement wheel Sieve to Generate Prime Numbers Between Given Range
Checked and Unchecked Exceptions in Java
Check If a File or Directory Exists in Java
Working With Maps Using Streams
Sao chép các phần tử của một mảng sang mảng khác như thế nào?
Introduction to the Java NIO2 File API
Java Program to Implement D-ary-Heap
Java Program to Check the Connectivity of Graph Using BFS
Guide to Java OutputStream
Java Program to Implement Iterative Deepening
Hướng dẫn kết nối cơ sở dữ liệu với Java JDBC
Java Program to Implement Quick sort
Giới thiệu JDBC Connection Pool
Giới thiệu Google Guice – Injection, Scope
Java Program to find the maximum subarray sum O(n^2) time(naive method)
Java Program to Implement Coppersmith Freivald’s Algorithm
Java Program to Implement LinkedBlockingQueue API
A Guide to @RepeatedTest in Junit 5
A Custom Media Type for a Spring REST API
Custom Exception trong Java
Mapping a Dynamic JSON Object with Jackson
Spring Boot Change Context Path
Java Program to Check Whether Graph is DAG
Convert char to String in Java
Spring Boot - Eureka Server
Java Multi-line String
Deploy a Spring Boot App to Azure
Lập trình đa luồng với Callable và Future trong Java
A Guide to Apache Commons Collections CollectionUtils
Lớp Properties trong java
Java Program to Implement Interpolation Search Algorithm