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:
Spring Data JPA and Null Parameters
Spring Boot Actuator
Request a Delivery / Read Receipt in Javamail
Java Program to Implement VList
Java Program to Find Inverse of a Matrix
String Joiner trong Java 8
Java Program to Perform Stooge Sort
Split a String in Java
Programmatic Transaction Management in Spring
Functional Interface trong Java 8
Java Program to Implement Hash Tables with Linear Probing
Spring MVC Content Negotiation
A Quick Guide to Using Keycloak with Spring Boot
Spring Security OAuth Login with WebFlux
LinkedList trong java
Biến trong java
Arrays.asList vs new ArrayList(Arrays.asList())
ArrayList trong java
Java Program to Implement Stack
Java CyclicBarrier vs CountDownLatch
Spring Security – Reset Your Password
Java Program to Implement Extended Euclid Algorithm
Java Program to implement Array Deque
Spring Boot - Batch Service
ThreadPoolTaskExecutor corePoolSize vs. maxPoolSize
Java Program to Perform integer Partition for a Specific Case
REST Web service: HTTP Status Code và xử lý ngoại lệ RESTful web service với Jersey 2.x
Guide to CopyOnWriteArrayList
Primitive Type Streams in Java 8
Java 8 StringJoiner
Java Scanner hasNext() vs. hasNextLine()
Spring Boot Security Auto-Configuration