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  import java.util.Set;
24  
25  /**
26   * @author <a href="michal.maczka@dimatics.com">Michal Maczka</a>
27   * @version $Id$
28   */
29  public class DAGTest
30      extends TestCase
31  {
32      public void testDAG()
33          throws CycleDetectedException
34      {
35          final DAG dag = new DAG();
36  
37          dag.addVertex( "a" );
38  
39          assertEquals( 1, dag.getVertices().size() );
40  
41          assertEquals( "a", dag.getVertex( "a" ).getLabel() );
42  
43          dag.addVertex( "a" );
44  
45          assertEquals( 1, dag.getVertices().size() );
46  
47          assertEquals( "a", dag.getVertex( "a" ).getLabel() );
48  
49          dag.addVertex( "b" );
50  
51          assertEquals( 2, dag.getVertices().size() );
52  
53          assertFalse( dag.hasEdge( "a", "b" ) );
54  
55          assertFalse( dag.hasEdge( "b", "a" ) );
56  
57          final Vertex a = dag.getVertex( "a" );
58  
59          final Vertex b = dag.getVertex( "b" );
60  
61          assertEquals( "a", a.getLabel() );
62  
63          assertEquals( "b", b.getLabel() );
64  
65          dag.addEdge( "a", "b" );
66  
67          assertTrue( a.getChildren().contains( b ) );
68  
69          assertTrue( b.getParents().contains( a ) );
70  
71          assertTrue( dag.hasEdge( "a", "b" ) );
72  
73          assertFalse( dag.hasEdge( "b", "a" ) );
74  
75          dag.addEdge( "c", "d" );
76  
77          assertEquals( 4, dag.getVertices().size() );
78  
79          final Vertex c = dag.getVertex( "c" );
80  
81          final Vertex d = dag.getVertex( "d" );
82  
83          assertEquals( "a", a.getLabel() );
84  
85          assertEquals( "b", b.getLabel() );
86  
87          assertEquals( "c", c.getLabel() );
88  
89          assertEquals( "d", d.getLabel() );
90  
91          assertFalse( dag.hasEdge( "b", "a" ) );
92  
93          assertFalse( dag.hasEdge( "a", "c" ) );
94  
95          assertFalse( dag.hasEdge( "a", "d" ) );
96  
97          assertTrue( dag.hasEdge( "c", "d" ) );
98  
99          assertFalse( dag.hasEdge( "d", "c" ) );
100 
101         final Set<String> labels = dag.getLabels();
102 
103         assertEquals( 4, labels.size() );
104 
105         assertTrue( labels.contains( "a" ) );
106 
107         assertTrue( labels.contains( "b" ) );
108 
109         assertTrue( labels.contains( "c" ) );
110 
111         assertTrue( labels.contains( "d" ) );
112 
113         dag.addEdge( "a", "d" );
114 
115         assertTrue( a.getChildren().contains( d ) );
116 
117         assertTrue( d.getParents().contains( a ) );
118 
119         // "b" and "d" are children of "a"
120         assertEquals( 2, a.getChildren().size() );
121 
122         assertTrue( a.getChildLabels().contains( "b" ) );
123 
124         assertTrue( a.getChildLabels().contains( "d" ) );
125 
126         // "a" and "c" are parents of "d"
127         assertEquals( 2, d.getParents().size() );
128 
129         assertTrue( d.getParentLabels().contains( "a" ) );
130 
131         assertTrue( d.getParentLabels().contains( "c" ) );
132     }
133 
134     public void testGetPredecessors()
135         throws CycleDetectedException
136     {
137         final DAG dag = new DAG();
138 
139         dag.addEdge( "a", "b" );
140 
141         //
142         // a --> b --> c --> e
143         // | | |
144         // | V V
145         // --> d <-- f --> g
146         // result d, g, f, c, b, a
147 
148         // force order of nodes
149 
150         dag.addVertex( "c" );
151 
152         dag.addVertex( "d" );
153 
154         dag.addEdge( "a", "b" );
155 
156         dag.addEdge( "b", "c" );
157 
158         dag.addEdge( "b", "d" );
159 
160         dag.addEdge( "c", "d" );
161 
162         dag.addEdge( "c", "e" );
163 
164         dag.addEdge( "f", "d" );
165 
166         dag.addEdge( "e", "f" );
167 
168         dag.addEdge( "f", "g" );
169 
170         final List<String> actual = dag.getSuccessorLabels( "b" );
171 
172         final List<String> expected = new ArrayList<String>();
173 
174         expected.add( "d" );
175 
176         expected.add( "g" );
177 
178         expected.add( "f" );
179 
180         expected.add( "e" );
181 
182         expected.add( "c" );
183 
184         expected.add( "b" );
185 
186         assertEquals( expected, actual );
187     }
188 }