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