1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.apache.maven.internal.impl;
20
21 import java.util.*;
22
23 import org.apache.maven.project.CycleDetectedException;
24
25 class Graph {
26 private enum DfsState {
27 VISITING,
28 VISITED
29 }
30
31 final Map<String, Vertex> vertices = new LinkedHashMap<>();
32
33 public Vertex getVertex(String id) {
34 return vertices.get(id);
35 }
36
37 public Collection<Vertex> getVertices() {
38 return vertices.values();
39 }
40
41 Vertex addVertex(String label) {
42 return vertices.computeIfAbsent(label, Vertex::new);
43 }
44
45 void addEdge(Vertex from, Vertex to) throws CycleDetectedException {
46 from.children.add(to);
47 to.parents.add(from);
48 List<String> cycle = findCycle(to);
49 if (cycle != null) {
50
51 removeEdge(from, to);
52 throw new CycleDetectedException(
53 "Edge between '" + from.label + "' and '" + to.label + "' introduces to cycle in the graph", cycle);
54 }
55 }
56
57 void removeEdge(Vertex from, Vertex to) {
58 from.children.remove(to);
59 to.parents.remove(from);
60 }
61
62 List<String> visitAll() {
63 return visitAll(vertices.values(), new HashMap<>(), new ArrayList<>());
64 }
65
66 List<String> findCycle(Vertex vertex) {
67 return visitCycle(Collections.singleton(vertex), new HashMap<>(), new LinkedList<>());
68 }
69
70 private static List<String> visitAll(
71 Collection<Vertex> children, Map<Vertex, DfsState> stateMap, List<String> list) {
72 for (Vertex v : children) {
73 DfsState state = stateMap.putIfAbsent(v, DfsState.VISITING);
74 if (state == null) {
75 visitAll(v.children, stateMap, list);
76 stateMap.put(v, DfsState.VISITED);
77 list.add(v.label);
78 }
79 }
80 return list;
81 }
82
83 private static List<String> visitCycle(
84 Collection<Vertex> children, Map<Vertex, DfsState> stateMap, LinkedList<String> cycle) {
85 for (Vertex v : children) {
86 DfsState state = stateMap.putIfAbsent(v, DfsState.VISITING);
87 if (state == null) {
88 cycle.addLast(v.label);
89 List<String> ret = visitCycle(v.children, stateMap, cycle);
90 if (ret != null) {
91 return ret;
92 }
93 cycle.removeLast();
94 stateMap.put(v, DfsState.VISITED);
95 } else if (state == DfsState.VISITING) {
96
97 int pos = cycle.lastIndexOf(v.label);
98 List<String> ret = cycle.subList(pos, cycle.size());
99 ret.add(v.label);
100 return ret;
101 }
102 }
103 return null;
104 }
105
106 static class Vertex {
107 final String label;
108 final List<Vertex> children = new ArrayList<>();
109 final List<Vertex> parents = new ArrayList<>();
110
111 Vertex(String label) {
112 this.label = label;
113 }
114
115 String getLabel() {
116 return label;
117 }
118
119 List<Vertex> getChildren() {
120 return children;
121 }
122
123 List<Vertex> getParents() {
124 return parents;
125 }
126 }
127
128 static class CycleDetectedException extends RuntimeException {
129 private final List<String> cycle;
130
131 CycleDetectedException(String message, List<String> cycle) {
132 super(message);
133 this.cycle = cycle;
134 }
135
136 public List<String> getCycle() {
137 return cycle;
138 }
139
140 @Override
141 public String getMessage() {
142 return super.getMessage() + " " + String.join(" --> ", cycle);
143 }
144 }
145 }