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 }