1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.apache.maven.model.building;
20
21 import java.util.Collection;
22 import java.util.Collections;
23 import java.util.HashMap;
24 import java.util.HashSet;
25 import java.util.LinkedHashMap;
26 import java.util.LinkedList;
27 import java.util.List;
28 import java.util.Map;
29 import java.util.Set;
30
31 class Graph {
32
33 final Map<String, Set<String>> graph = new LinkedHashMap<>();
34
35 synchronized void addEdge(String from, String to) throws CycleDetectedException {
36 if (graph.computeIfAbsent(from, l -> new HashSet<>()).add(to)) {
37 List<String> cycle = visitCycle(graph, Collections.singleton(to), new HashMap<>(), new LinkedList<>());
38 if (cycle != null) {
39
40 throw new CycleDetectedException(
41 "Edge between '" + from + "' and '" + to + "' introduces to cycle in the graph", cycle);
42 }
43 }
44 }
45
46 private enum DfsState {
47 VISITING,
48 VISITED
49 }
50
51 private static List<String> visitCycle(
52 Map<String, Set<String>> graph,
53 Collection<String> children,
54 Map<String, DfsState> stateMap,
55 LinkedList<String> cycle) {
56 if (children != null) {
57 for (String v : children) {
58 DfsState state = stateMap.putIfAbsent(v, DfsState.VISITING);
59 if (state == null) {
60 cycle.addLast(v);
61 List<String> ret = visitCycle(graph, graph.get(v), stateMap, cycle);
62 if (ret != null) {
63 return ret;
64 }
65 cycle.removeLast();
66 stateMap.put(v, DfsState.VISITED);
67 } else if (state == DfsState.VISITING) {
68
69 int pos = cycle.lastIndexOf(v);
70 List<String> ret = cycle.subList(pos, cycle.size());
71 ret.add(v);
72 return ret;
73 }
74 }
75 }
76 return null;
77 }
78
79 public static class CycleDetectedException extends Exception {
80 private final List<String> cycle;
81
82 CycleDetectedException(String message, List<String> cycle) {
83 super(message);
84 this.cycle = cycle;
85 }
86
87 public List<String> getCycle() {
88 return cycle;
89 }
90
91 @Override
92 public String getMessage() {
93 return super.getMessage() + " " + String.join(" --> ", cycle);
94 }
95 }
96 }