Detect circle in directed graph — DFS

To detect circle in directed graph, it is important to mark the node with 3 types:
1. Node hasn’t been visited yet.
2. Node is being visiting which means node is processing, but it hasn’t finished DFS of all outgoing edges.
3. Node is visited, which means not only node itself, but also outgoing edges have been finished DFS.

1. package feb;
2. import java.util.HashMap;
3. import java.util.HashSet;
4. import java.util.Set;
5. public class DetectCircleInGraph_DFS {
6.     public static boolean hasCircle(HashMap graph) {
7.         HashMap visited = new HashMap();
8.         for (Node node : graph.values()) {
9.             if (hasCircleUtil(graph, visited, node)) {
10.                 return true;
11.             }
12.         }
13.         return false;
14.     }
15.     public static boolean hasCircleUtil(HashMap graph,
16.             HashMap visited, Node node) {
17.         if (visited.get(node.ch) == NodeStatus.VISITED) {
18.             return false;
19.         }
20.         if (visited.get(node.ch) == NodeStatus.ON_VISITING) {
21.             return true;
22.         }
23.         visited.put(node.ch, NodeStatus.ON_VISITING);
24.         for (Node nextNode : node.outgoing) {
25.             if (hasCircleUtil(graph, visited, nextNode)) {
26.                 return true;
27.             }
28.         }
29.         visited.put(node.ch, NodeStatus.VISITED);
30.         return false;
31.     }
32.     enum NodeStatus {
33.         ON_VISITING, VISITED
34.     }
35.     public static class Node {
36.         char ch;
37.         Set outgoing = new HashSet();
38.         int seq;
39.         char ancestry; // indicate ancestry of the node, led by back edge.
40.         Node(char ch) {
41.             this.ch = ch;
42.         }
43.     }
44.     public static void main(String[] args) {
45.         Node a = new Node(‘a’);
46.         Node b = new Node(‘b’);
47.         Node c = new Node(‘c’);
48.         Node d = new Node(‘d’);
49.         Node e = new Node(‘e’);
50.         a.outgoing.add(b);
51.         b.outgoing.add(c);
52.         b.outgoing.add(e);
53.         b.outgoing.add(d);
54.         c.outgoing.add(e);
55.         e.outgoing.add(d);
56.         d.outgoing.add(a);
57.         HashMap graph = new HashMap();
58.         graph.put(a.ch, a);
59.         graph.put(b.ch, b);
60.         graph.put(c.ch, c);
61.         graph.put(d.ch, d);
62.         graph.put(e.ch, e);
63.         boolean hasCircle = hasCircle(graph);
64.         System.out.println(hasCircle);
65.     }
66. }