View Javadoc
1   package org.codehaus.plexus.util.dag;
2   
3   /*
4    * Copyright The Codehaus Foundation.
5    *
6    * Licensed under the Apache License, Version 2.0 (the "License");
7    * you may not use this file except in compliance with the License.
8    * 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, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  
19  import junit.framework.TestCase;
20  
21  import java.util.List;
22  
23  /**
24   * @author <a href="michal.maczka@dimatics.com">Michal Maczka</a>
25   * @version $Id$
26   */
27  public class CycleDetectorTest
28      extends TestCase
29  {
30  
31      public void testCycyleDetection()
32      {
33          // No cycle
34          //
35          // a --> b --->c
36          //
37          try
38          {
39              final DAG dag1 = new DAG();
40  
41              dag1.addEdge( "a", "b" );
42  
43              dag1.addEdge( "b", "c" );
44  
45          }
46          catch ( CycleDetectedException e )
47          {
48  
49              fail( "Cycle should not be detected" );
50          }
51  
52          //
53          // a --> b --->c
54          // ^ |
55          // | |
56          // -----------|
57  
58          try
59          {
60              final DAG dag2 = new DAG();
61  
62              dag2.addEdge( "a", "b" );
63  
64              dag2.addEdge( "b", "c" );
65  
66              dag2.addEdge( "c", "a" );
67  
68              fail( "Cycle should be detected" );
69  
70          }
71          catch ( CycleDetectedException e )
72          {
73  
74              final List<String> cycle = e.getCycle();
75  
76              assertNotNull( "Cycle should be not null", cycle );
77  
78              assertTrue( "Cycle contains 'a'", cycle.contains( "a" ) );
79  
80              assertTrue( "Cycle contains 'b'", cycle.contains( "b" ) );
81  
82              assertTrue( "Cycle contains 'c'", cycle.contains( "c" ) );
83  
84          }
85  
86          // | --> c
87          // a --> b
88          // | | --> d
89          // --------->
90          try
91          {
92              final DAG dag3 = new DAG();
93  
94              dag3.addEdge( "a", "b" );
95  
96              dag3.addEdge( "b", "c" );
97  
98              dag3.addEdge( "b", "d" );
99  
100             dag3.addEdge( "a", "d" );
101 
102         }
103         catch ( CycleDetectedException e )
104         {
105             fail( "Cycle should not be detected" );
106         }
107 
108         // ------------
109         // | |
110         // V | --> c
111         // a --> b
112         // | | --> d
113         // --------->
114         try
115         {
116             final DAG dag4 = new DAG();
117 
118             dag4.addEdge( "a", "b" );
119 
120             dag4.addEdge( "b", "c" );
121 
122             dag4.addEdge( "b", "d" );
123 
124             dag4.addEdge( "a", "d" );
125 
126             dag4.addEdge( "c", "a" );
127 
128             fail( "Cycle should be detected" );
129 
130         }
131         catch ( CycleDetectedException e )
132         {
133             final List<String> cycle = e.getCycle();
134 
135             assertNotNull( "Cycle should be not null", cycle );
136 
137             assertEquals( "Cycle contains 'a'", "a", (String) cycle.get( 0 ) );
138 
139             assertEquals( "Cycle contains 'b'", "b", cycle.get( 1 ) );
140 
141             assertEquals( "Cycle contains 'c'", "c", cycle.get( 2 ) );
142 
143             assertEquals( "Cycle contains 'a'", "a", (String) cycle.get( 3 ) );
144         }
145 
146         // f --> g --> h
147         // |
148         // |
149         // a --> b ---> c --> d
150         // ^ |
151         // | V
152         // ------------ e
153 
154         final DAG dag5 = new DAG();
155 
156         try
157         {
158 
159             dag5.addEdge( "a", "b" );
160 
161             dag5.addEdge( "b", "c" );
162 
163             dag5.addEdge( "b", "f" );
164 
165             dag5.addEdge( "f", "g" );
166 
167             dag5.addEdge( "g", "h" );
168 
169             dag5.addEdge( "c", "d" );
170 
171             dag5.addEdge( "d", "e" );
172 
173             dag5.addEdge( "e", "b" );
174 
175             fail( "Cycle should be detected" );
176 
177         }
178         catch ( CycleDetectedException e )
179         {
180             final List<String> cycle = e.getCycle();
181 
182             assertNotNull( "Cycle should be not null", cycle );
183 
184             assertEquals( "Cycle contains 5 elements", 5, cycle.size() );
185 
186             assertEquals( "Cycle contains 'b'", "b", (String) cycle.get( 0 ) );
187 
188             assertEquals( "Cycle contains 'c'", "c", cycle.get( 1 ) );
189 
190             assertEquals( "Cycle contains 'd'", "d", cycle.get( 2 ) );
191 
192             assertEquals( "Cycle contains 'e'", "e", (String) cycle.get( 3 ) );
193 
194             assertEquals( "Cycle contains 'b'", "b", (String) cycle.get( 4 ) );
195 
196             assertTrue( "Edge exists", dag5.hasEdge( "a", "b" ) );
197 
198             assertTrue( "Edge exists", dag5.hasEdge( "b", "c" ) );
199 
200             assertTrue( "Edge exists", dag5.hasEdge( "b", "f" ) );
201 
202             assertTrue( "Edge exists", dag5.hasEdge( "f", "g" ) );
203 
204             assertTrue( "Edge exists", dag5.hasEdge( "g", "h" ) );
205 
206             assertTrue( "Edge exists", dag5.hasEdge( "c", "d" ) );
207 
208             assertTrue( "Edge exists", dag5.hasEdge( "d", "e" ) );
209 
210             assertFalse( dag5.hasEdge( "e", "b" ) );
211         }
212 
213     }
214 
215 }