1 package org.codehaus.plexus.util.dag;
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 import java.util.Collections;
20 import java.util.HashMap;
21 import java.util.LinkedList;
22 import java.util.List;
23 import java.util.Map;
24
25
26
27
28
29 public class CycleDetector {
30
31 private static final Integer NOT_VISITED = 0;
32
33 private static final Integer VISITING = 1;
34
35 private static final Integer VISITED = 2;
36
37 public static List<String> hasCycle(final DAG graph) {
38 final List<Vertex> vertices = graph.getVertices();
39
40 final Map<Vertex, Integer> vertexStateMap = new HashMap<>();
41
42 List<String> retValue = null;
43
44 for (Vertex vertex : vertices) {
45 if (isNotVisited(vertex, vertexStateMap)) {
46 retValue = introducesCycle(vertex, vertexStateMap);
47
48 if (retValue != null) {
49 break;
50 }
51 }
52 }
53
54 return retValue;
55 }
56
57
58
59
60
61
62
63
64
65 public static List<String> introducesCycle(final Vertex vertex, final Map<Vertex, Integer> vertexStateMap) {
66 final LinkedList<String> cycleStack = new LinkedList<>();
67
68 final boolean hasCycle = dfsVisit(vertex, cycleStack, vertexStateMap);
69
70 if (hasCycle) {
71
72
73
74
75
76
77 final String label = cycleStack.getFirst();
78
79 final int pos = cycleStack.lastIndexOf(label);
80
81 final List<String> cycle = cycleStack.subList(0, pos + 1);
82
83 Collections.reverse(cycle);
84
85 return cycle;
86 }
87
88 return null;
89 }
90
91 public static List<String> introducesCycle(final Vertex vertex) {
92 final Map<Vertex, Integer> vertexStateMap = new HashMap<>();
93
94 return introducesCycle(vertex, vertexStateMap);
95 }
96
97 private static boolean isNotVisited(final Vertex vertex, final Map<Vertex, Integer> vertexStateMap) {
98 final Integer state = vertexStateMap.get(vertex);
99
100 return (state == null) || NOT_VISITED.equals(state);
101 }
102
103 private static boolean isVisiting(final Vertex vertex, final Map<Vertex, Integer> vertexStateMap) {
104 final Integer state = vertexStateMap.get(vertex);
105
106 return VISITING.equals(state);
107 }
108
109 private static boolean dfsVisit(
110 final Vertex vertex, final LinkedList<String> cycle, final Map<Vertex, Integer> vertexStateMap) {
111 cycle.addFirst(vertex.getLabel());
112
113 vertexStateMap.put(vertex, VISITING);
114
115 for (Vertex v : vertex.getChildren()) {
116 if (isNotVisited(v, vertexStateMap)) {
117 final boolean hasCycle = dfsVisit(v, cycle, vertexStateMap);
118
119 if (hasCycle) {
120 return true;
121 }
122 } else if (isVisiting(v, vertexStateMap)) {
123 cycle.addFirst(v.getLabel());
124
125 return true;
126 }
127 }
128 vertexStateMap.put(vertex, VISITED);
129
130 cycle.removeFirst();
131
132 return false;
133 }
134 }