KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > avalon > fortress > util > dag > DirectedAcyclicGraphVerifier


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