1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.eclipse.jetty.deploy.graph;
20
21 import java.util.HashSet;
22 import java.util.Set;
23 import java.util.concurrent.CopyOnWriteArrayList;
24
25
26
27
28 public class Graph
29 {
30 private Set<Node> _nodes = new HashSet<Node>();
31 private Set<Edge> _edges = new HashSet<Edge>();
32
33 public void addEdge(Edge edge)
34 {
35 Node fromNode = getNodeByName(edge.getFrom().getName());
36 if (fromNode==null)
37 addNode(fromNode=edge.getFrom());
38 Node toNode = getNodeByName(edge.getTo().getName());
39 if (toNode==null)
40 addNode(toNode=edge.getTo());
41
42
43 if (edge.getFrom()!=fromNode || edge.getTo()!=toNode)
44 edge=new Edge(fromNode,toNode);
45
46 this._edges.add(edge);
47 }
48
49 public void addEdge(String from, String to)
50 {
51 Node fromNode = getNodeByName(from);
52 if (fromNode==null)
53 {
54 fromNode = new Node(from);
55 addNode(fromNode);
56 }
57
58 Node toNode = getNodeByName(to);
59 if (toNode==null)
60 {
61 toNode = new Node(to);
62 addNode(toNode);
63 }
64
65 addEdge(fromNode,toNode);
66 }
67
68 private void addEdge(Node fromNode, Node toNode)
69 {
70 Edge edge = new Edge(fromNode,toNode);
71 addEdge(edge);
72 }
73
74 public void addNode(Node node)
75 {
76 this._nodes.add(node);
77 }
78
79
80
81
82
83
84
85
86
87 public void insertNode(Edge edge, String nodeName)
88 {
89 Node node = getNodeByName(nodeName);
90 if (node==null)
91 {
92 node = new Node(nodeName);
93 }
94
95 insertNode(edge,node);
96 }
97
98
99
100
101
102
103
104
105
106 public void insertNode(Edge edge, Node node)
107 {
108
109 removeEdge(edge);
110
111 addNode(node);
112
113 addEdge(edge.getFrom(),node);
114
115 addEdge(node,edge.getTo());
116 }
117
118
119
120
121
122
123
124
125
126 public Set<Edge> findEdges(Node node)
127 {
128 Set<Edge> fromedges = new HashSet<Edge>();
129
130 for (Edge edge : this._edges)
131 {
132 if ((edge.getFrom() == node) || (edge.getTo() == node))
133 {
134 fromedges.add(edge);
135 }
136 }
137
138 return fromedges;
139 }
140
141
142
143
144
145
146
147
148 public Set<Edge> findEdgesFrom(Node from)
149 {
150 Set<Edge> fromedges = new HashSet<Edge>();
151
152 for (Edge edge : this._edges)
153 {
154 if (edge.getFrom() == from)
155 {
156 fromedges.add(edge);
157 }
158 }
159
160 return fromedges;
161 }
162
163
164
165
166
167
168
169
170
171
172 public Path getPath(String nodeNameOrigin, String nodeNameDest)
173 {
174 if (nodeNameOrigin.equals(nodeNameDest))
175 {
176 return new Path();
177 }
178
179 Node from = getNodeByName(nodeNameOrigin);
180 Node to = getNodeByName(nodeNameDest);
181 return getPath(from,to);
182 }
183
184
185
186
187
188
189
190
191
192
193 public Path getPath(Node from, Node to)
194 {
195 if (from == to)
196 {
197 return new Path();
198 }
199
200
201 Path path = breadthFirst(from,to,new CopyOnWriteArrayList<Path>(),new HashSet<Edge>());
202 return path;
203 }
204
205
206 private Path breadthFirst(Node from, Node destination, CopyOnWriteArrayList<Path> paths, Set<Edge> seen)
207 {
208
209 boolean edgesAdded = false;
210 if (paths.size()==0)
211 paths.add(new Path());
212
213 for (Path path : paths)
214 {
215 Set<Edge> next = findEdgesFrom(path.nodes()==0?from:path.lastNode());
216 if (next.size() == 0)
217 continue;
218
219
220 int splits=0;
221 for (Edge edge:next)
222 {
223 if (seen.contains(edge))
224 continue;
225 seen.add(edge);
226 Path nextPath = (++splits==next.size())?path:path.forkPath();
227
228 nextPath.add(edge);
229
230
231 if (destination.equals(edge.getTo()))
232 return nextPath;
233
234 edgesAdded = true;
235
236
237 if (nextPath!=path)
238 paths.add(nextPath);
239 }
240 }
241
242 if (edgesAdded)
243 return breadthFirst(from,destination,paths,seen);
244 return null;
245 }
246
247
248 public Set<Edge> getEdges()
249 {
250 return _edges;
251 }
252
253
254
255
256
257
258
259
260 public Node getNodeByName(String name)
261 {
262 for (Node node : _nodes)
263 {
264 if (node.getName().equals(name))
265 {
266 return node;
267 }
268 }
269 return null;
270 }
271
272 public Set<Node> getNodes()
273 {
274 return _nodes;
275 }
276
277 public void removeEdge(Edge edge)
278 {
279 this._edges.remove(edge);
280 }
281
282 public void removeEdge(String fromNodeName, String toNodeName)
283 {
284 Node fromNode = getNodeByName(fromNodeName);
285 Node toNode = getNodeByName(toNodeName);
286 Edge edge = new Edge(fromNode,toNode);
287 removeEdge(edge);
288 }
289
290 public void removeNode(Node node)
291 {
292 this._nodes.remove(node);
293 }
294
295 public void setEdges(Set<Edge> edges)
296 {
297 this._edges = edges;
298 }
299
300 public void setNodes(Set<Node> nodes)
301 {
302 this._nodes = nodes;
303 }
304 }