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:
Inheritance and Composition (Is-a vs Has-a relationship) in Java
Using Spring ResponseEntity to Manipulate the HTTP Response
Create a Custom Auto-Configuration with Spring Boot
Java Program to Implement Direct Addressing Tables
Java Program to Implement IdentityHashMap API
A Guide to Apache Commons Collections CollectionUtils
Java Program to Implement Threaded Binary Tree
Introduction to Java 8 Streams
Java Program to Find Number of Articulation points in a Graph
Java Program to Implement Bloom Filter
Java Program to Perform LU Decomposition of any Matrix
Spring Cloud – Securing Services
Java Program to Implement Shoelace Algorithm
Check If a File or Directory Exists in Java
Java Program to Find the Vertex Connectivity of a Graph
SOAP Web service: Upload và Download file sử dụng MTOM trong JAX-WS
Java Program to Implement Ternary Tree
A Quick JUnit vs TestNG Comparison
HashSet trong java
Spring Cloud Connectors and Heroku
Java Program to Implement Find all Cross Edges in a Graph
Java Program to Implement Suffix Array
Java Program to Construct a Random Graph by the Method of Random Edge Selection
OAuth2 Remember Me with Refresh Token
Java – Create a File
Java Program to Represent Graph Using Linked List
Java Program to Implement RoleList API
Java Program to Implement WeakHashMap API
Java Program to Implement Regular Falsi Algorithm
Java Program to Implement Efficient O(log n) Fibonacci generator
Java Program to Implement Extended Euclid Algorithm
Introduction to Spring Cloud Rest Client with Netflix Ribbon