|
1
17
18 package org.apache.avalon.fortress.util.dag.test;
19
20 import junit.framework.TestCase;
21
22 import java.util.ArrayList  ;
23 import java.util.Collections ;
24 import java.util.Iterator ;
25 import java.util.List ;
26 import org.apache.avalon.fortress.util.dag.*;
27
28
29
35 public class DirectedAcyclicGraphVerifierTestCase extends TestCase
36 {
37 public DirectedAcyclicGraphVerifierTestCase( String 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 }
76 }
77
78
83 public void testCycleTest() throws Exception
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 vertices = new ArrayList ( 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 );
105 try
106 {
107 DirectedAcyclicGraphVerifier.topologicalSort( vertices );
108 fail( "Did not detect the expected cyclic dependency" );
109 }
110 catch ( CyclicDependencyException cde )
111 {
112 }
114 }
115
116
117 public void testSortDAG() throws Exception
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 vertices = new ArrayList ( 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 }
161 }
162
163 private void verifyGraphOrders( List vertices )
164 {
165 for ( Iterator iter = vertices.iterator(); iter.hasNext(); )
166 {
167 Vertex v = (Vertex)iter.next();
168
169 for ( Iterator 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 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 |
Java API By Example, From Geeks To Geeks.