View Javadoc

1   /*
2    * Copyright 2013 University of Glasgow.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  package broadwick.phylo;
17  
18  import broadwick.graph.Edge;
19  import broadwick.graph.Tree;
20  import java.util.Collection;
21  import lombok.extern.slf4j.Slf4j;
22  import org.junit.After;
23  import org.junit.AfterClass;
24  import static org.junit.Assert.*;
25  import org.junit.Before;
26  import org.junit.BeforeClass;
27  import org.junit.ClassRule;
28  import org.junit.Rule;
29  import org.junit.Test;
30  import org.junit.rules.TestRule;
31  import org.junit.rules.TestWatcher;
32  import org.junit.runner.Description;
33  import org.junit.runners.model.Statement;
34  import org.slf4j.MarkerFactory;
35  
36  /**
37   * Test cases for broadwick.phylo.NewickTreeParserTest class.
38   */
39  @Slf4j
40  public class NewickTreeParserTest {
41  
42      public NewickTreeParserTest() {
43          testFileName = NewickTreeParserTest.class.getClass().getResource("/TestNewickFile.txt").getFile();
44  
45          // TODO BUG there is a bug in the windows implementation of java that prepends a 
46          // "/" to the file name. We need to strip it here
47          if (System.getProperty("os.name").startsWith("Windows") && testFileName.startsWith("/")) {
48              testFileName = testFileName.substring(1);
49          }
50      }
51  
52      @BeforeClass
53      public static void setUpClass() {
54      }
55  
56      @AfterClass
57      public static void tearDownClass() {
58      }
59  
60      @Before
61      public void setUp() {
62      }
63  
64      @After
65      public void tearDown() {
66      }
67  
68      @ClassRule // the magic is done here
69      public static TestRule classWatchman = new TestWatcher() {
70          @Override
71          protected void starting(Description description) {
72              log.info(MarkerFactory.getMarker("TEST"), "    Running tests from {} ...", description.getClassName());
73          }
74  
75      };
76      @Rule
77      public TestRule watchman = new TestWatcher() {
78          @Override
79          public Statement apply(Statement base, Description description) {
80              log.info(MarkerFactory.getMarker("TEST"), "        Running {} ...", description.getMethodName());
81              return base;
82          }
83  
84      };
85      @Test
86      public void testParse() {
87          NewickTreeParser newickTreeParser = new NewickTreeParser(testFileName);
88          Tree<PhyloNode, Edge<PhyloNode>> tree = newickTreeParser.parse();
89          checkTree(tree);
90      }
91  
92      @Test
93      public void testParseWithArg() {
94          NewickTreeParser newickTreeParser = new NewickTreeParser();
95  
96          // Test the trees we've already tested
97          Tree<PhyloNode, Edge<PhyloNode>> tree = newickTreeParser.parse("A:0.1,B:0.2,(C:0.3,D:0.4):0.5");
98          checkTree(tree);
99  
100         // now test the same tree with optional braces, semicolon
101         tree = newickTreeParser.parse("A:0.1,B:0.2,(C:0.3,D:0.4):0.5;");
102         checkTree(tree);
103 
104         tree = newickTreeParser.parse("(A:0.1,B:0.2,(C:0.3,D:0.4):0.5);");
105         checkTree(tree);
106 
107         // Now test it with more complicated tests.
108         // no nodes are named
109         //tree = newickTreeParser.parse("(,,(,));");
110 
111         // leaf nodes are named (but no branch length
112         tree = newickTreeParser.parse("(A,B,(C,D));");
113         checkTreeWithNoBranchLengths(tree);
114 
115         // all nodes are named
116 //        tree = newickTreeParser.parse("(A,B,(C,D)E)F;");
117 //        checkTreeWithWithBranchNamesWithoutBranchLengths(tree);
118 
119         // all but root node have a distance to parent
120         //tree = newickTreeParser.parse("(:0.1,:0.2,(:0.3,:0.4):0.5);");
121 
122         // all have a distance to parent
123         //tree = newickTreeParser.parse("(:0.1,:0.2,(:0.3,:0.4):0.5):0.0;");
124 
125         // distances and all names
126         //tree = newickTreeParser.parse("(A:0.1,B:0.2,(C:0.3,D:0.4)E:0.5)F;");
127 
128         // distances and all names
129         tree = newickTreeParser.parse("(A:0.1,B:0.2,(C:0.3,D:0.4)E:0.5)F:0.0;");
130         checkTreeWithBranchName(tree);
131 
132         // a tree rooted on a leaf node (rare)
133         //tree = newickTreeParser.parse("((B:0.2,(C:0.3,D:0.4)E:0.5)F:0.1)A;");
134 
135         tree = newickTreeParser.parse("A:0.1;");
136         checkTreeWithOnlyRootNode(tree);
137 
138         tree = newickTreeParser.parse("(A:0.1,((C:0.3,D:0.4)E:0.5,B:0.2),Q:1.8,R:0.6,(T:0.9,(U:0.1,V:0.15,Y:1.0))W:0.4)F:0.0;");
139         checkTreeWithNestedBranches(tree);
140     }
141 
142     /**
143      * Several of the methods here generate the same tree (using different optional braces etc in the Newick format),
144      * this method tests the outcomes.
145      * @param tree
146      */
147     private void checkTree(final Tree<PhyloNode, Edge<PhyloNode>> tree) {
148         assertEquals(6, tree.getVertexCount());
149         assertEquals(2, tree.getHeight());
150 
151         Collection<PhyloNode> vertices = tree.getVertices();
152 
153         PhyloNode rootNode = new PhyloNode("", 0.5);
154         PhyloNode aNode = new PhyloNode("A", 0.1);
155         PhyloNode bNode = new PhyloNode("B", 0.2);
156         PhyloNode cNode = new PhyloNode("C", 0.3);
157         PhyloNode dNode = new PhyloNode("D", 0.4);
158         PhyloNode branchNode = new PhyloNode("branch-0", 0.0);
159 
160         assertTrue(vertices.contains(rootNode));
161         assertTrue(vertices.contains(aNode));
162         assertTrue(vertices.contains(bNode));
163         assertTrue(vertices.contains(cNode));
164         assertTrue(vertices.contains(dNode));
165         assertTrue(vertices.contains(branchNode));
166 
167         assertEquals(1, tree.getDepth(aNode));
168         assertEquals(1, tree.inDegree(aNode));
169         assertEquals(0, tree.outDegree(aNode));
170 
171         assertEquals(1, tree.getDepth(bNode));
172         assertEquals(1, tree.inDegree(bNode));
173         assertEquals(0, tree.outDegree(bNode));
174 
175         assertEquals(2, tree.getDepth(cNode));
176         assertEquals(1, tree.inDegree(cNode));
177         assertEquals(0, tree.outDegree(cNode));
178 
179         assertEquals(2, tree.getDepth(dNode));
180         assertEquals(1, tree.inDegree(dNode));
181         assertEquals(0, tree.outDegree(dNode));
182 
183         assertEquals(0, tree.getDepth(rootNode));
184         assertEquals(0, tree.inDegree(rootNode));
185         assertEquals(3, tree.outDegree(rootNode));
186 
187         assertEquals(1, tree.getDepth(branchNode));
188         assertEquals(1, tree.inDegree(branchNode));
189         assertEquals(2, tree.outDegree(branchNode));
190     }
191 
192     private void checkTreeWithBranchName(final Tree<PhyloNode, Edge<PhyloNode>> tree) {
193         // This is the newwick string we're checking 
194         // (A:0.1,B:0.2,(C:0.3,D:0.4)E:0.5)F:0.0;
195         // i.e. it is the same as before but the branch name and root are specified.
196 
197         assertEquals(6, tree.getVertexCount());
198         assertEquals(2, tree.getHeight());
199 
200         Collection<PhyloNode> vertices = tree.getVertices();
201 
202         PhyloNode rootNode = new PhyloNode("F", 0.0);
203         PhyloNode aNode = new PhyloNode("A", 0.1);
204         PhyloNode bNode = new PhyloNode("B", 0.2);
205         PhyloNode cNode = new PhyloNode("C", 0.3);
206         PhyloNode dNode = new PhyloNode("D", 0.4);
207         PhyloNode branchNode = new PhyloNode("E", 0.5);
208 
209         assertTrue(vertices.contains(rootNode));
210         assertTrue(vertices.contains(aNode));
211         assertTrue(vertices.contains(bNode));
212         assertTrue(vertices.contains(cNode));
213         assertTrue(vertices.contains(dNode));
214         assertTrue(vertices.contains(branchNode));
215 
216         assertEquals(1, tree.getDepth(aNode));
217         assertEquals(1, tree.inDegree(aNode));
218         assertEquals(0, tree.outDegree(aNode));
219 
220         assertEquals(1, tree.getDepth(bNode));
221         assertEquals(1, tree.inDegree(bNode));
222         assertEquals(0, tree.outDegree(bNode));
223 
224         assertEquals(2, tree.getDepth(cNode));
225         assertEquals(1, tree.inDegree(cNode));
226         assertEquals(0, tree.outDegree(cNode));
227 
228         assertEquals(2, tree.getDepth(dNode));
229         assertEquals(1, tree.inDegree(dNode));
230         assertEquals(0, tree.outDegree(dNode));
231 
232         assertEquals(0, tree.getDepth(rootNode));
233         assertEquals(0, tree.inDegree(rootNode));
234         assertEquals(3, tree.outDegree(rootNode));
235 
236         assertEquals(1, tree.getDepth(branchNode));
237         assertEquals(1, tree.inDegree(branchNode));
238         assertEquals(2, tree.outDegree(branchNode));
239     }
240 
241     private void checkTreeWithOnlyRootNode(final Tree<PhyloNode, Edge<PhyloNode>> tree) {
242         assertEquals(1, tree.getVertexCount());
243         assertEquals(0, tree.getHeight());
244         PhyloNode rootNode = new PhyloNode("A", 0.1);
245         assertTrue(tree.getVertices().contains(rootNode));
246         assertEquals(0, tree.getDepth(rootNode));
247         assertEquals(0, tree.inDegree(rootNode));
248         assertEquals(0, tree.outDegree(rootNode));
249     }
250     
251     private void checkTreeWithNoBranchLengths(Tree<PhyloNode, Edge<PhyloNode>> tree) {
252         
253         assertEquals(6, tree.getVertexCount());
254         assertEquals(2, tree.getHeight());
255 
256         Collection<PhyloNode> vertices = tree.getVertices();
257 
258         PhyloNode rootNode = new PhyloNode("", 0.0);
259         PhyloNode aNode = new PhyloNode("A", 0.0);
260         PhyloNode bNode = new PhyloNode("B", 0.0);
261         PhyloNode cNode = new PhyloNode("C", 0.0);
262         PhyloNode dNode = new PhyloNode("D", 0.0);
263         PhyloNode branchNode = new PhyloNode("branch-0", 0.0);
264 
265         assertTrue(vertices.contains(rootNode));
266         assertTrue(vertices.contains(aNode));
267         assertTrue(vertices.contains(bNode));
268         assertTrue(vertices.contains(cNode));
269         assertTrue(vertices.contains(dNode));
270         assertTrue(vertices.contains(branchNode));
271 
272         assertEquals(1, tree.getDepth(aNode));
273         assertEquals(1, tree.inDegree(aNode));
274         assertEquals(0, tree.outDegree(aNode));
275 
276         assertEquals(1, tree.getDepth(bNode));
277         assertEquals(1, tree.inDegree(bNode));
278         assertEquals(0, tree.outDegree(bNode));
279 
280         assertEquals(2, tree.getDepth(cNode));
281         assertEquals(1, tree.inDegree(cNode));
282         assertEquals(0, tree.outDegree(cNode));
283 
284         assertEquals(2, tree.getDepth(dNode));
285         assertEquals(1, tree.inDegree(dNode));
286         assertEquals(0, tree.outDegree(dNode));
287 
288         assertEquals(0, tree.getDepth(rootNode));
289         assertEquals(0, tree.inDegree(rootNode));
290         assertEquals(3, tree.outDegree(rootNode));
291 
292         assertEquals(1, tree.getDepth(branchNode));
293         assertEquals(1, tree.inDegree(branchNode));
294         assertEquals(2, tree.outDegree(branchNode));
295     } 
296     
297     private void checkTreeWithWithBranchNamesWithoutBranchLengths(Tree<PhyloNode, Edge<PhyloNode>> tree) {
298         assertEquals(6, tree.getVertexCount());
299         assertEquals(2, tree.getHeight());
300 
301         Collection<PhyloNode> vertices = tree.getVertices();
302 
303         PhyloNode rootNode = new PhyloNode("F", 0.0);
304         PhyloNode aNode = new PhyloNode("A", 0.0);
305         PhyloNode bNode = new PhyloNode("B", 0.0);
306         PhyloNode cNode = new PhyloNode("C", 0.0);
307         PhyloNode dNode = new PhyloNode("D", 0.0);
308         PhyloNode branchNode = new PhyloNode("E", 0.0);
309 
310         assertTrue(vertices.contains(rootNode));
311         assertTrue(vertices.contains(aNode));
312         assertTrue(vertices.contains(bNode));
313         assertTrue(vertices.contains(cNode));
314         assertTrue(vertices.contains(dNode));
315         assertTrue(vertices.contains(branchNode));
316 
317         assertEquals(1, tree.getDepth(aNode));
318         assertEquals(1, tree.inDegree(aNode));
319         assertEquals(0, tree.outDegree(aNode));
320 
321         assertEquals(1, tree.getDepth(bNode));
322         assertEquals(1, tree.inDegree(bNode));
323         assertEquals(0, tree.outDegree(bNode));
324 
325         assertEquals(2, tree.getDepth(cNode));
326         assertEquals(1, tree.inDegree(cNode));
327         assertEquals(0, tree.outDegree(cNode));
328 
329         assertEquals(2, tree.getDepth(dNode));
330         assertEquals(1, tree.inDegree(dNode));
331         assertEquals(0, tree.outDegree(dNode));
332 
333         assertEquals(0, tree.getDepth(rootNode));
334         assertEquals(0, tree.inDegree(rootNode));
335         assertEquals(3, tree.outDegree(rootNode));
336 
337         assertEquals(1, tree.getDepth(branchNode));
338         assertEquals(1, tree.inDegree(branchNode));
339         assertEquals(2, tree.outDegree(branchNode));
340     }
341     
342     private void checkTreeWithNestedBranches(final Tree<PhyloNode, Edge<PhyloNode>> tree) {
343         assertEquals(15, tree.getVertexCount());
344         assertEquals(3, tree.getHeight());
345         
346         PhyloNode rootNode = new PhyloNode("F", 0.0);
347         PhyloNode aNode = new PhyloNode("A", 0.1);
348         PhyloNode bNode = new PhyloNode("B", 0.2);
349         PhyloNode cNode = new PhyloNode("C", 0.3);
350         PhyloNode dNode = new PhyloNode("D", 0.4);
351         PhyloNode eNode = new PhyloNode("E", 0.5);
352         PhyloNode qNode = new PhyloNode("Q", 1.8);
353         PhyloNode rNode = new PhyloNode("R", 0.6);
354         PhyloNode tNode = new PhyloNode("T", 0.9);
355         PhyloNode uNode = new PhyloNode("U", 0.1);
356         PhyloNode vNode = new PhyloNode("V", 0.15);
357         PhyloNode wNode = new PhyloNode("W", 0.4);
358         PhyloNode yNode = new PhyloNode("Y", 1.0);
359         PhyloNode branch0 = new PhyloNode("branch-0", 0.0);
360         PhyloNode branch1 = new PhyloNode("branch-1", 0.0);
361         
362         Collection<PhyloNode> vertices = tree.getVertices();
363         assertTrue(vertices.contains(rootNode));
364         assertTrue(vertices.contains(aNode));
365         assertTrue(vertices.contains(bNode));
366         assertTrue(vertices.contains(cNode));
367         assertTrue(vertices.contains(dNode));
368         assertTrue(vertices.contains(eNode));
369         assertTrue(vertices.contains(qNode));
370         assertTrue(vertices.contains(rNode));
371         assertTrue(vertices.contains(tNode));
372         assertTrue(vertices.contains(uNode));
373         assertTrue(vertices.contains(vNode));
374         assertTrue(vertices.contains(wNode));
375         assertTrue(vertices.contains(yNode));
376         assertTrue(vertices.contains(branch0));
377         assertTrue(vertices.contains(branch1));
378 
379         assertEquals(0, tree.getDepth(rootNode));
380         assertEquals(0, tree.inDegree(rootNode));
381         assertEquals(5, tree.outDegree(rootNode));
382 
383         assertEquals(1, tree.getDepth(aNode));
384         assertEquals(1, tree.inDegree(aNode));
385         assertEquals(0, tree.outDegree(aNode));
386 
387         assertEquals(2, tree.getDepth(bNode));
388         assertEquals(1, tree.inDegree(bNode));
389         assertEquals(0, tree.outDegree(bNode));
390 
391         assertEquals(3, tree.getDepth(cNode));
392         assertEquals(1, tree.inDegree(cNode));
393         assertEquals(0, tree.outDegree(cNode));
394 
395         assertEquals(3, tree.getDepth(dNode));
396         assertEquals(1, tree.inDegree(dNode));
397         assertEquals(0, tree.outDegree(dNode));
398 
399         assertEquals(2, tree.getDepth(eNode));
400         assertEquals(1, tree.inDegree(eNode));
401         assertEquals(2, tree.outDegree(eNode));
402 
403         assertEquals(1, tree.getDepth(qNode));
404         assertEquals(1, tree.inDegree(qNode));
405         assertEquals(0, tree.outDegree(qNode));
406 
407         assertEquals(1, tree.getDepth(rNode));
408         assertEquals(1, tree.inDegree(rNode));
409         assertEquals(0, tree.outDegree(rNode));
410 
411         assertEquals(2, tree.getDepth(tNode));
412         assertEquals(1, tree.inDegree(tNode));
413         assertEquals(0, tree.outDegree(tNode));
414 
415         assertEquals(3, tree.getDepth(uNode));
416         assertEquals(1, tree.inDegree(uNode));
417         assertEquals(0, tree.outDegree(uNode));
418 
419         assertEquals(3, tree.getDepth(vNode));
420         assertEquals(1, tree.inDegree(vNode));
421         assertEquals(0, tree.outDegree(vNode));
422 
423         assertEquals(1, tree.getDepth(wNode));
424         assertEquals(1, tree.inDegree(wNode));
425         assertEquals(2, tree.outDegree(wNode));
426 
427         assertEquals(3, tree.getDepth(yNode));
428         assertEquals(1, tree.inDegree(yNode));
429         assertEquals(0, tree.outDegree(yNode));
430 
431         assertEquals(1, tree.getDepth(branch0));
432         assertEquals(1, tree.inDegree(branch0));
433         assertEquals(2, tree.outDegree(branch0));
434 
435         assertEquals(2, tree.getDepth(branch1));
436         assertEquals(1, tree.inDegree(branch1));
437         assertEquals(3, tree.outDegree(branch1));
438     }
439 
440     private static String testFileName;
441 }