Java program to find cycle in a directed graph

package com.sample.app.model;

import java.util.List;

public class Vertex<T extends Comparable<T>> {
 private int id;
 private List<T> adjacentVertices;

 public int getId() {
  return id;
 }

 public void setId(int id) {
  this.id = id;
 }

 public List<T> getAdjacentVertices() {
  return adjacentVertices;
 }

 public void setAdjacentVertices(List<T> adjacentVertices) {
  this.adjacentVertices = adjacentVertices;
 }

}

package com.sample.app.model;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class DirectedGraph<T extends Comparable<T>> {
 private Map<T, Set<T>> graph;
 private Map<T, Boolean> visited = new HashMap<>();

 private Set<T> distinctVertices = new HashSet<>();;

 public DirectedGraph() {
  graph = new HashMap<>();
 }

 public void addEdge(T from, T to) {

  Set<T> adjacencyList = graph.get(from);

  if (adjacencyList == null) {
   adjacencyList = new HashSet<T>();
  }

  adjacencyList.add(to);

  graph.put(from, adjacencyList);
  distinctVertices.add(from);
  distinctVertices.add(to);
 }

 public Map<T, Set<T>> getGraph() {
  return graph;
 }

 public void setGraph(Map<T, Set<T>> graph) {
  this.graph = graph;
 }

 public boolean isCycleExistDirectionalGraph() {
  Map<T, Boolean> visited = new HashMap<>();
  Map<T, Boolean> recStack = new HashMap<>();

  for (T key : distinctVertices) {
   visited.put(key, false);
   recStack.put(key, false);
  }

  for (T vertex : visited.keySet())
   if (isCyclicUtilDirectionalGraph(vertex, visited, recStack))
    return true;

  return false;

 }

 private boolean isCyclicUtilDirectionalGraph(T vertex, Map<T, Boolean> visited, Map<T, Boolean> recStack) {

  if (recStack.get(vertex))
   return true;

  if (visited.get(vertex))
   return false;

  visited.put(vertex, true);
  recStack.put(vertex, true);

  Set<T> children = graph.get(vertex);

  if (children != null)
   for (T c : children)
    if (isCyclicUtilDirectionalGraph(c, visited, recStack))
     return true;

  recStack.put(vertex, false);

  return false;
 }
}

package com.sample.app.model;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import org.junit.Test;

public class DirectedGraphTest {
 @Test
 public void testCase1() {
  DirectedGraph g1 = new DirectedGraph<Integer>();

  g1.addEdge(1, 0);
  g1.addEdge(0, 2);
  g1.addEdge(2, 1);
  g1.addEdge(0, 3);
  g1.addEdge(3, 4);

  assertTrue(g1.isCycleExistDirectionalGraph());
 }

 @Test
 public void testCase2() {
  DirectedGraph g1 = new DirectedGraph<Integer>();

  g1.addEdge(0, 1);
  g1.addEdge(1, 2);

  assertFalse(g1.isCycleExistDirectionalGraph());
 }

 @Test
 public void testCase3() {
  DirectedGraph g1 = new DirectedGraph<Integer>();

  assertFalse(g1.isCycleExistDirectionalGraph());
 }

 @Test
 public void testCase4() {
  DirectedGraph g1 = new DirectedGraph<Integer>();

  g1.addEdge(123, 0);
  g1.addEdge(0, 123);
  g1.addEdge(4232, 123);
  g1.addEdge(0, 3);
  g1.addEdge(3, 4);

  assertTrue(g1.isCycleExistDirectionalGraph());
 }

 @Test
 public void testCase5() {
  DirectedGraph g1 = new DirectedGraph<Integer>();

  g1.addEdge(1, 1);

  assertTrue(g1.isCycleExistDirectionalGraph());
 }

 @Test
 public void testCase6() {
  DirectedGraph g1 = new DirectedGraph<Integer>();

  g1.addEdge(1, 2);
  g1.addEdge(1, 1);

  assertTrue(g1.isCycleExistDirectionalGraph());
 }

 @Test
 public void testCase7() {
  DirectedGraph g1 = new DirectedGraph<Integer>();

  g1.addEdge(1, 2);
  g1.addEdge(1, 3);
  g1.addEdge(2, 3);

  assertFalse(g1.isCycleExistDirectionalGraph());
 }

 @Test
 public void testCase8() {
  DirectedGraph g1 = new DirectedGraph<Integer>();

  g1.addEdge(1, 2);
  g1.addEdge(1, 3);
  g1.addEdge(2, 3);
  g1.addEdge(3, 1);

  assertTrue(g1.isCycleExistDirectionalGraph());
 }

 @Test
 public void testCase9() {
  DirectedGraph g1 = new DirectedGraph<Integer>();

  g1.addEdge(1, 2);
  g1.addEdge(1, 3);
  g1.addEdge(2, 3);
  g1.addEdge(3, 4);
  g1.addEdge(3, 5);
  g1.addEdge(5, 2);

  assertTrue(g1.isCycleExistDirectionalGraph());
 }
 
 @Test
 public void testCase10() {
  DirectedGraph g1 = new DirectedGraph<Integer>();

  g1.addEdge(191, 232);
  g1.addEdge(340, 466);

  assertFalse(g1.isCycleExistDirectionalGraph());
 }
 
 @Test
 public void testCase11() {
  DirectedGraph g1 = new DirectedGraph<Integer>();

  g1.addEdge(191, 232);
  g1.addEdge(340, 466);
  g1.addEdge(466, 340);

  assertTrue(g1.isCycleExistDirectionalGraph());
 }
}

You may like

Design Patterns

Interview Questions

Programming Questions

Find the permutations of a string

Add element to the end of stack

Reverse the elements of stack

Suppose there are 'N' stairs, a person wants to reach the top. Person can climb either 1 (or) 2 stairs at a time.Count the number of ways that a person can reach the top.