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.io.Serializable;
20 import java.util.ArrayList;
21 import java.util.HashMap;
22 import java.util.List;
23 import java.util.Map;
24 import java.util.Set;
25
26
27
28
29
30
31
32
33 public class DAG implements Cloneable, Serializable {
34
35
36
37
38
39
40
41
42
43 private Map<String, Vertex> vertexMap = new HashMap<>();
44
45
46
47
48 private List<Vertex> vertexList = new ArrayList<>();
49
50
51
52
53
54
55
56
57 public DAG() {
58 super();
59 }
60
61
62
63
64
65
66
67
68 public List<Vertex> getVertices() {
69 return vertexList;
70 }
71
72
73
74
75
76 @Deprecated
77 public List<Vertex> getVerticies() {
78 return getVertices();
79 }
80
81 public Set<String> getLabels() {
82 return vertexMap.keySet();
83 }
84
85
86
87
88
89
90
91
92
93
94
95
96 public Vertex addVertex(final String label) {
97 Vertex retValue = null;
98
99
100 if (vertexMap.containsKey(label)) {
101 retValue = vertexMap.get(label);
102 } else {
103 retValue = new Vertex(label);
104
105 vertexMap.put(label, retValue);
106
107 vertexList.add(retValue);
108 }
109
110 return retValue;
111 }
112
113 public void addEdge(final String from, final String to) throws CycleDetectedException {
114 final Vertex v1 = addVertex(from);
115
116 final Vertex v2 = addVertex(to);
117
118 addEdge(v1, v2);
119 }
120
121 public void addEdge(final Vertex from, final Vertex to) throws CycleDetectedException {
122
123 from.addEdgeTo(to);
124
125 to.addEdgeFrom(from);
126
127 final List<String> cycle = CycleDetector.introducesCycle(to);
128
129 if (cycle != null) {
130
131
132 removeEdge(from, to);
133
134 final String msg = "Edge between '" + from + "' and '" + to + "' introduces to cycle in the graph";
135
136 throw new CycleDetectedException(msg, cycle);
137 }
138 }
139
140 public void removeEdge(final String from, final String to) {
141 final Vertex v1 = addVertex(from);
142
143 final Vertex v2 = addVertex(to);
144
145 removeEdge(v1, v2);
146 }
147
148 public void removeEdge(final Vertex from, final Vertex to) {
149 from.removeEdgeTo(to);
150
151 to.removeEdgeFrom(from);
152 }
153
154 public Vertex getVertex(final String label) {
155 final Vertex retValue = vertexMap.get(label);
156
157 return retValue;
158 }
159
160 public boolean hasEdge(final String label1, final String label2) {
161 final Vertex v1 = getVertex(label1);
162
163 final Vertex v2 = getVertex(label2);
164
165 final boolean retValue = v1.getChildren().contains(v2);
166
167 return retValue;
168 }
169
170
171
172
173
174 public List<String> getChildLabels(final String label) {
175 final Vertex vertex = getVertex(label);
176
177 return vertex.getChildLabels();
178 }
179
180
181
182
183
184 public List<String> getParentLabels(final String label) {
185 final Vertex vertex = getVertex(label);
186
187 return vertex.getParentLabels();
188 }
189
190
191
192
193 @Override
194 public Object clone() throws CloneNotSupportedException {
195
196 final Object retValue = super.clone();
197
198 return retValue;
199 }
200
201
202
203
204
205
206 public boolean isConnected(final String label) {
207 final Vertex vertex = getVertex(label);
208
209 final boolean retValue = vertex.isConnected();
210
211 return retValue;
212 }
213
214
215
216
217
218
219
220
221 public List<String> getSuccessorLabels(final String label) {
222 final Vertex vertex = getVertex(label);
223
224 final List<String> retValue;
225
226
227 if (vertex.isLeaf()) {
228 retValue = new ArrayList<>(1);
229
230 retValue.add(label);
231 } else {
232 retValue = TopologicalSorter.sort(vertex);
233 }
234
235 return retValue;
236 }
237 }