1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 */
19
20 package org.apache.myfaces.config.util;
21
22 import java.util.ArrayList;
23 import java.util.Collections;
24 import java.util.Iterator;
25 import java.util.List;
26
27 /**
28 * DirectedAcyclicGraphVerifier provides methods to verify that any set of
29 * vertices has no cycles. A Directed Acyclic Graph is a "graph" or set of
30 * vertices where all connections between each vertex goes in a particular
31 * direction and there are no cycles or loops. It is used to track dependencies
32 * and ansure that dependencies can be loaded and unloaded in the proper order.
33 *
34 * @author <a href="mailto:dev@avalon.apache.org">Avalon Development Team</a>
35 * @version CVS $ Revision: 1.1 $
36 */
37 public class DirectedAcyclicGraphVerifier
38 {
39 /**
40 * Verify that a vertex and its set of dependencies have no cycles.
41 *
42 * @param vertex The vertex we want to test.
43 *
44 * @throws CyclicDependencyException if there is a cycle.
45 */
46 public static <T> void verify(Vertex<T> vertex) throws CyclicDependencyException
47 {
48 // We need a list of vertices that contains the entire graph, so build it.
49 List<Vertex<T>> vertices = new ArrayList<Vertex<T>>();
50 addDependencies(vertex, vertices);
51
52 verify(vertices);
53 }
54
55 /**
56 * Recursively add a vertex and all of its dependencies to a list of
57 * vertices
58 *
59 * @param vertex Vertex to be added.
60 * @param vertices Existing list of vertices.
61 */
62 private static <T> void addDependencies(final Vertex<T> vertex, final List<Vertex<T>> vertices)
63 {
64 if (!vertices.contains(vertex))
65 {
66 vertices.add(vertex);
67
68 for (Vertex<T> v : vertex.getDependencies())
69 {
70 addDependencies(v, vertices);
71 }
72 }
73 }
74
75 /**
76 * Verify a set of vertices and all their dependencies have no cycles. All
77 * Vertices in the graph must exist in the list.
78 *
79 * @param vertices The list of vertices we want to test.
80 *
81 * @throws CyclicDependencyException if there is a cycle.
82 */
83 public static <T> void verify(List<Vertex<T>> vertices) throws CyclicDependencyException
84 {
85 // Reset the orders of all the vertices.
86 resetVertices(vertices);
87
88 // Assert that all vertices are in the vertices list and resolve each of their orders.
89 Iterator<Vertex<T>> it = vertices.iterator();
90 while (it.hasNext())
91 {
92 Vertex<T> v = it.next();
93
94 // Make sure that any dependencies are also in the vertices list. This adds
95 // a little bit to the load, but we don't test this and the test would have
96 // failed, this would lead to some very hard to track down problems elsewhere.
97 Iterator<Vertex<T>> dit = v.getDependencies().iterator();
98 while (dit.hasNext())
99 {
100 Vertex<T> dv = dit.next();
101 if (!vertices.contains(dv))
102 {
103 throw new IllegalStateException("A dependent vertex ("
104 + dv.getName() + ") of " + "vertex (" + v.getName()
105 + ") was not included in the vertices list.");
106 }
107 }
108
109 v.resolveOrder();
110 }
111 }
112
113 /**
114 * Sort a set of vertices so that no dependency is before its vertex. If
115 * we have a vertex named "Parent" and one named "Child" that is listed as
116 * a dependency of "Parent", we want to ensure that "Child" always comes
117 * after "Parent". As long as there are no cycles in the list, we can sort
118 * any number of vertices that may or may not be related. Both "Parent"
119 * and "Child" must exist in the vertices list, but "Child" will also be
120 * referenced as a dependency of "Parent".
121 *
122 * <p>
123 * <b>Implementation Detail:</b> This particular algorithm is a more
124 * efficient variation of the typical Topological Sort algorithm. It uses
125 * a Queue (Linked List) to ensure that each edge (connection between
126 * two vertices) or vertex is checked only once. The efficiency is
127 * O = (|V| + |E|).
128 * </p>
129 *
130 * @param vertices
131 * @throws CyclicDependencyException
132 */
133 public static <T> void topologicalSort(final List<Vertex<T>> vertices)
134 throws CyclicDependencyException
135 {
136 // Verify the graph and set the vertex orders in the process.
137 verify(vertices);
138
139 // We now that there are no cycles and that each of the vertices has an order
140 // that will allow them to be sorted.
141 Collections.sort(vertices);
142 }
143
144 /**
145 * Resets all the vertices so that the visitation flags and indegrees are
146 * reset to their start values.
147 *
148 * @param vertices
149 */
150 public static <T> void resetVertices(List<Vertex<T>> vertices)
151 {
152 Iterator<Vertex<T>> it = vertices.iterator();
153 while (it.hasNext())
154 {
155 it.next().reset();
156 }
157 }
158
159 public static <T> int findVertex(List<Vertex<T>> vertexList, String name)
160 {
161 for (int i = 0; i < vertexList.size(); i++)
162 {
163 Vertex<T> v = vertexList.get(i);
164 if (name.equals(v.getName()))
165 {
166 return i;
167 }
168 }
169 return -1;
170 }
171 }