KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > avalon > fortress > util > dag > test > DirectedAcyclicGraphVerifierTestCase


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.test;
19
20 import junit.framework.TestCase;
21
22 import java.util.ArrayList JavaDoc;
23 import java.util.Collections JavaDoc;
24 import java.util.Iterator JavaDoc;
25 import java.util.List JavaDoc;
26 import org.apache.avalon.fortress.util.dag.*;
27
28
29 /**
30  * DirectedAcyclicGraphVerifierTestCase.java does XYZ
31  *
32  * @author <a HREF="mailto:dev@avalon.apache.org">Avalon Development Team</a>
33  * @version CVS $ Revision: 1.1 $
34  */

35 public class DirectedAcyclicGraphVerifierTestCase extends TestCase
36 {
37     public DirectedAcyclicGraphVerifierTestCase( String JavaDoc name )
38     {
39         super( name );
40     }
41
42     public void testIsDAG()
43     {
44         try
45         {
46             Vertex root = new Vertex( "Root" );
47             root.addDependency( new Vertex( "Child1" ) );
48             root.addDependency( new Vertex( "Child2" ) );
49
50             DirectedAcyclicGraphVerifier.verify( root );
51         }
52         catch ( CyclicDependencyException cde )
53         {
54             fail( "Incorrectly found a Cycle" );
55         }
56
57         try
58         {
59             Vertex root = new Vertex( "Root" );
60             root.addDependency( new Vertex( "Child1" ) );
61             root.addDependency( new Vertex( "Child2" ) );
62
63             Vertex child3 = new Vertex( "Child3" );
64             child3.addDependency( root );
65
66             root.addDependency( child3 );
67
68             DirectedAcyclicGraphVerifier.verify( root );
69
70             fail( "Incorrectly missed the Cycle" );
71         }
72         catch ( CyclicDependencyException cde )
73         {
74             // Success!
75
}
76     }
77
78     /**
79      * This test waas written to test the algorithm used to search for cycles.
80      * It makes sure that cycles that start a ways into the dependency tree
81      * are handled correctly.
82      */

83     public void testCycleTest() throws Exception JavaDoc
84     {
85         Vertex component1 = new Vertex( "Component1" );
86         Vertex component2 = new Vertex( "Component2" );
87         Vertex component3 = new Vertex( "Component3" );
88         Vertex component4 = new Vertex( "Component4" );
89         Vertex component5 = new Vertex( "Component5" );
90         
91         List JavaDoc vertices = new ArrayList JavaDoc( 5 );
92         vertices.add( component1 );
93         vertices.add( component2 );
94         vertices.add( component3 );
95         vertices.add( component4 );
96         vertices.add( component5 );
97         
98         component1.addDependency( component2 );
99         component2.addDependency( component3 );
100             
101         component3.addDependency( component4 );
102         component4.addDependency( component5 );
103         component5.addDependency( component3 ); // Cycle
104

105         try
106         {
107             DirectedAcyclicGraphVerifier.topologicalSort( vertices );
108             fail( "Did not detect the expected cyclic dependency" );
109         }
110         catch ( CyclicDependencyException cde )
111         {
112             //Success!
113
}
114     }
115         
116     
117     public void testSortDAG() throws Exception JavaDoc
118     {
119         Vertex component1 = new Vertex( "Component1" );
120         Vertex component2 = new Vertex( "Component2" );
121         Vertex component3 = new Vertex( "Component3" );
122         Vertex component4 = new Vertex( "Component4" );
123         Vertex component5 = new Vertex( "Component5" );
124
125         component1.addDependency( component2 );
126         component1.addDependency( component3 );
127
128         component3.addDependency( component4 );
129
130         component5.addDependency( component2 );
131         component5.addDependency( component4 );
132
133         List JavaDoc vertices = new ArrayList JavaDoc( 5 );
134         vertices.add( component1 );
135         vertices.add( component2 );
136         vertices.add( component3 );
137         vertices.add( component4 );
138         vertices.add( component5 );
139
140         DirectedAcyclicGraphVerifier.topologicalSort( vertices );
141         verifyGraphOrders( vertices );
142         verifyListOrder( vertices );
143
144         Collections.shuffle( vertices );
145         DirectedAcyclicGraphVerifier.topologicalSort( vertices );
146         verifyGraphOrders( vertices );
147         verifyListOrder( vertices );
148
149         component4.addDependency( component1 );
150         Collections.shuffle( vertices );
151
152         try
153         {
154             DirectedAcyclicGraphVerifier.topologicalSort( vertices );
155             fail( "Did not detect the expected cyclic dependency" );
156         }
157         catch ( CyclicDependencyException cde )
158         {
159             //Success!
160
}
161     }
162     
163     private void verifyGraphOrders( List JavaDoc vertices )
164     {
165         for ( Iterator JavaDoc iter = vertices.iterator(); iter.hasNext(); )
166         {
167             Vertex v = (Vertex)iter.next();
168             
169             // Make sure that the orders of all dependencies are less than
170
// the order of v.
171
for ( Iterator JavaDoc iter2 = v.getDependencies().iterator(); iter2.hasNext(); )
172             {
173                 Vertex dv = (Vertex)iter2.next();
174                 assertTrue( "The order of " + dv.getName() + " (" + dv.getOrder() + ") should be "
175                     + "less than the order of " + v.getName() + " (" + v.getOrder() + ")",
176                     dv.getOrder() < v.getOrder() );
177             }
178         }
179     }
180     
181     private void verifyListOrder( List JavaDoc vertices )
182     {
183         Vertex[] ary = new Vertex[vertices.size()];
184         vertices.toArray( ary );
185         for ( int i = 1; i < ary.length; i++ )
186         {
187             assertTrue( "The order of vertex #" + ( i - 1 ) + " (" + ary[i - 1].getOrder() + ") "
188                 + "should be <= the order of vertex #" + ( i ) + " (" + ary[i].getOrder() + ")",
189                 ary[i - 1].getOrder() <= ary[i].getOrder() );
190         }
191     }
192 }
193
Popular Tags