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:
Getting Started with GraphQL and Spring Boot
Lập trình hướng đối tượng (OOPs) trong java
Guide to Spring 5 WebFlux
Java Program to Implement the One Time Pad Algorithm
Hướng dẫn Java Design Pattern – Strategy
Java Program to Perform Insertion in a 2 Dimension K-D Tree
Java Program to Implement Hash Tree
Simultaneous Spring WebClient Calls
A Guide to System.exit()
Registration – Password Strength and Rules
Introduction to the Java NIO Selector
Lập trình đa luồng với Callable và Future trong Java
Spring Boot - Tracing Micro Service Logs
Java Program to implement Bit Matrix
Java Program to Encode a Message Using Playfair Cipher
@Order in Spring
Java Program to Check Whether a Directed Graph Contains a Eulerian Cycle
Converting Java Date to OffsetDateTime
Java 8 Streams peek() API
Giới thiệu Google Guice – Aspect Oriented Programming (AOP)
Spring Data JPA @Modifying Annotation
Java Program to Implement the Binary Counting Method to Generate Subsets of a Set
Use Liquibase to Safely Evolve Your Database Schema
Java Program to Implement SimpeBindings API
Java Program to Implement D-ary-Heap
Java Program to Implement Find all Forward Edges in a Graph
Java Program to Perform Finite State Automaton based Search
Java Program to Perform Sorting Using B-Tree
Java Program to Print the Kind of Rotation the AVL Tree is Undergoing
Java Program to Implement Double Ended Queue
Tránh lỗi NullPointerException trong Java như thế nào?
Check whether a graph is bipartite