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.ArrayList;
22  import java.util.List;
23  
24  /**
25   * @author <a href="michal.maczka@dimatics.com">Michal Maczka</a>
26   * @version $Id$
27   */
28  public class TopologicalSorterTest
29      extends TestCase
30  {
31      public void testDfs()
32          throws CycleDetectedException
33      {
34          // a --> b --->c
35          //
36          // result a,b,c
37          final DAG dag1 = new DAG();
38  
39          dag1.addEdge( "a", "b" );
40  
41          dag1.addEdge( "b", "c" );
42  
43          final List<String> expected1 = new ArrayList<String>();
44  
45          expected1.add( "c" );
46  
47          expected1.add( "b" );
48  
49          expected1.add( "a" );
50  
51          final List<String> actual1 = TopologicalSorter.sort( dag1 );
52  
53          assertEquals( "Order is different then expected", expected1, actual1 );
54  
55          //
56          // a <-- b <---c
57          //
58          // result c, b, a
59          final DAG dag2 = new DAG();
60  
61          dag2.addVertex( "a" );
62  
63          dag2.addVertex( "b" );
64  
65          dag2.addVertex( "c" );
66  
67          dag2.addEdge( "b", "a" );
68  
69          dag2.addEdge( "c", "b" );
70  
71          final List<String> expected2 = new ArrayList<String>();
72  
73          expected2.add( "a" );
74  
75          expected2.add( "b" );
76  
77          expected2.add( "c" );
78  
79          final List<String> actual2 = TopologicalSorter.sort( dag2 );
80  
81          assertEquals( "Order is different then expected", expected2, actual2 );
82  
83          //
84          // a --> b --> c --> e
85          // | | |
86          // | V V
87          // --> d <-- f --> g
88          // result d, g, f, c, b, a
89          final DAG dag3 = new DAG();
90  
91          // force order of nodes in the graph
92          dag3.addVertex( "a" );
93  
94          dag3.addVertex( "b" );
95  
96          dag3.addVertex( "c" );
97  
98          dag3.addVertex( "d" );
99  
100         dag3.addVertex( "e" );
101 
102         dag3.addVertex( "f" );
103 
104         dag3.addEdge( "a", "b" );
105 
106         dag3.addEdge( "b", "c" );
107 
108         dag3.addEdge( "b", "d" );
109 
110         dag3.addEdge( "c", "d" );
111 
112         dag3.addEdge( "c", "e" );
113 
114         dag3.addEdge( "f", "d" );
115 
116         dag3.addEdge( "e", "f" );
117 
118         dag3.addEdge( "f", "g" );
119 
120         final List<String> expected3 = new ArrayList<String>();
121 
122         expected3.add( "d" );
123 
124         expected3.add( "g" );
125 
126         expected3.add( "f" );
127 
128         expected3.add( "e" );
129 
130         expected3.add( "c" );
131 
132         expected3.add( "b" );
133 
134         expected3.add( "a" );
135 
136         final List<String> actual3 = TopologicalSorter.sort( dag3 );
137 
138         assertEquals( "Order is different then expected", expected3, actual3 );
139 
140         //
141         // a --> b --> c --> e
142         // | | |
143         // | V V
144         // --> d <-- f
145         // result d, f, e, c, b, a
146         final DAG dag4 = new DAG();
147         // force order of nodes in the graph
148 
149         dag4.addVertex( "f" );
150 
151         dag4.addVertex( "e" );
152 
153         dag4.addVertex( "d" );
154 
155         dag4.addVertex( "c" );
156 
157         dag4.addVertex( "a" );
158 
159         dag4.addVertex( "b" );
160 
161         dag4.addEdge( "a", "b" );
162 
163         dag4.addEdge( "b", "c" );
164 
165         dag4.addEdge( "b", "d" );
166 
167         dag4.addEdge( "c", "d" );
168 
169         dag4.addEdge( "c", "e" );
170 
171         dag4.addEdge( "f", "d" );
172 
173         dag4.addEdge( "e", "f" );
174 
175         final List<String> expected4 = new ArrayList<String>();
176 
177         expected4.add( "d" );
178 
179         expected4.add( "f" );
180 
181         expected4.add( "e" );
182 
183         expected4.add( "c" );
184 
185         expected4.add( "b" );
186 
187         expected4.add( "a" );
188 
189         final List<String> actual4 = TopologicalSorter.sort( dag4 );
190 
191         assertEquals( "Order is different then expected", expected4, actual4 );
192     }
193 }