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.sanfoundry.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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - Java Program to Remove the Edges in a Cyclic Graph such that its Linear Extension can be Found

» Next - Java Program to Check if Graph is DAG

Related Posts:

Check Java Books
Practice BCA MCQs
Practice Programming MCQs
Check Programming Books
Apply for Java Internship

Recommended Articles: