Java Program to Find a Good Feedback Edge Set in a Graph

This is a java program to find feednack arc set. This is the set which contains edges which when removed from the graph, graph becomes directed acyclic graph.

Here is the source code of the Java Program to Find a Good Feedback Edge Set in a Graph. 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 Graph
{
    private Map<Integer, List<Integer>> adjacencyList;
 
    public Graph(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 Graph 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 getFeedbackArcSet(int v)
    {
        boolean flag = false;
        int[] visited = new int[v + 1];
        Iterator<Integer> iterator = this.adjacencyList.keySet().iterator();
        System.out.print("The set of edges in feedback arc 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(i + " - " + list.get(j));
                    }
                    else
                    {
                        visited[list.get(j)] = 1;
                    }
                }
            }
        }
        return flag;
    }
}
 
public class FeedbackArcSet
{
    public static void main(String args[])
    {
        int v, e, count = 1, to, from;
        Scanner sc = new Scanner(System.in);
        Graph 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 Graph(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();
            Graph modified = glist.checkDAG();
            if (modified.getFeedbackArcSet(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:

$ javac FeedbackArcSet.java
$ java FeedbackArcSet	
 
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 edges in feedback arc set: 6 - 4

Related posts:

Java Program to Implement Dijkstra’s Algorithm using Priority Queue
Java InputStream to String
Java Program to Implement Hash Tables with Linear Probing
Jackson – JsonMappingException (No serializer found for class)
Java Program to Check Whether a Given Point is in a Given Polygon
Documenting a Spring REST API Using OpenAPI 3.0
Abstract class và Interface trong Java
Introduction to the Java NIO2 File API
Explain about URL and HTTPS protocol
Reading an HTTP Response Body as a String in Java
Tìm hiểu về xác thực và phân quyền trong ứng dụng
TreeSet và sử dụng Comparable, Comparator trong java
Java Program to Implement Brent Cycle Algorithm
Send an email with an attachment
Java Program to Create a Minimal Set of All Edges Whose Addition will Convert it to a Strongly Conne...
Java Program to Implement Bubble Sort
XML Serialization and Deserialization with Jackson
Spring Cloud Series – The Gateway Pattern
Semaphore trong Java
Java Program to Implement Doubly Linked List
Hướng dẫn Java Design Pattern – Strategy
Java Program to Implement Maximum Length Chain of Pairs
Java Program to Check whether Directed Graph is Connected using DFS
Java Program to Implement Find all Back Edges in a Graph
Java Program to Perform Quick Sort on Large Number of Elements
How to Store Duplicate Keys in a Map in Java?
Overflow and Underflow in Java
Spring @RequestParam Annotation
Spring Boot - Apache Kafka
Giới thiệu Design Patterns
Java Program to Implement Stack API
Spring Data JPA Delete and Relationships