[1573] | 1 | // NodeUtils.java |
---|
| 2 | // |
---|
| 3 | // (c) 1999-2001 PAL Development Core Team |
---|
| 4 | // |
---|
| 5 | // This package may be distributed under the |
---|
| 6 | // terms of the Lesser GNU General Public License (LGPL) |
---|
| 7 | |
---|
| 8 | |
---|
| 9 | package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; |
---|
| 10 | |
---|
| 11 | |
---|
| 12 | import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier; |
---|
| 13 | |
---|
| 14 | |
---|
| 15 | /** |
---|
| 16 | * Helper routines for dealing with nodes. |
---|
| 17 | * |
---|
| 18 | * @version $Id: NodeUtils.java,v 1.19 2002/01/08 02:09:53 alexi Exp $ |
---|
| 19 | * |
---|
| 20 | * @author Alexei Drummond |
---|
| 21 | * @author Korbinian Strimmer |
---|
| 22 | */ |
---|
| 23 | public class NodeUtils { |
---|
| 24 | |
---|
| 25 | /** |
---|
| 26 | * Converts lengths to heights, *without* assuming contemporaneous |
---|
| 27 | * tips. |
---|
| 28 | */ |
---|
| 29 | public static void lengths2Heights(Node root) { |
---|
| 30 | |
---|
| 31 | lengths2Heights(root, getGreatestDistance(root)); |
---|
| 32 | } |
---|
| 33 | |
---|
| 34 | /** |
---|
| 35 | * Converts lengths to heights, but maintains tip heights. |
---|
| 36 | */ |
---|
| 37 | public static void lengths2HeightsKeepTips(Node node, boolean useMax) { |
---|
| 38 | |
---|
| 39 | if (!node.isLeaf()) { |
---|
| 40 | for (int i = 0; i < node.getChildCount(); i++) { |
---|
| 41 | lengths2HeightsKeepTips(node.getChild(i), useMax); |
---|
| 42 | } |
---|
| 43 | |
---|
| 44 | double totalHL = 0.0; |
---|
| 45 | double maxHL = 0.0; |
---|
| 46 | double hl = 0.0; |
---|
| 47 | double maxH = 0.0; |
---|
| 48 | double h = 0.0; |
---|
| 49 | for (int i = 0; i < node.getChildCount(); i++) { |
---|
| 50 | h = node.getChild(i).getNodeHeight(); |
---|
| 51 | hl = node.getChild(i).getBranchLength() + h; |
---|
| 52 | if (hl > maxHL) maxHL = hl; |
---|
| 53 | if (h > maxH) maxH = h; |
---|
| 54 | totalHL += hl; |
---|
| 55 | } |
---|
| 56 | if (useMax) { |
---|
| 57 | hl = maxHL; // set parent height to maximum parent height implied by children |
---|
| 58 | } else { |
---|
| 59 | hl = totalHL / node.getChildCount(); // get mean parent height |
---|
| 60 | if (hl < maxH) hl = maxHL; // if mean parent height is not greater than all children height, fall back on max parent height. |
---|
| 61 | } |
---|
| 62 | node.setNodeHeight(hl); // set new parent height |
---|
| 63 | |
---|
| 64 | // change lengths in children to reflect changes. |
---|
| 65 | for (int i = 0; i < node.getChildCount(); i++) { |
---|
| 66 | h = node.getChild(i).getNodeHeight(); |
---|
| 67 | node.getChild(i).setBranchLength(hl - h); |
---|
| 68 | } |
---|
| 69 | } |
---|
| 70 | } |
---|
| 71 | |
---|
| 72 | |
---|
| 73 | /** |
---|
| 74 | * sets this nodes height value to newHeight and all children's |
---|
| 75 | * height values based on length of branches. |
---|
| 76 | */ |
---|
| 77 | private static void lengths2Heights(Node node, double newHeight) { |
---|
| 78 | |
---|
| 79 | if (!node.isRoot()) { |
---|
| 80 | newHeight -= node.getBranchLength(); |
---|
| 81 | node.setNodeHeight(newHeight); |
---|
| 82 | } else { |
---|
| 83 | node.setNodeHeight(newHeight); |
---|
| 84 | } |
---|
| 85 | |
---|
| 86 | for (int i = 0; i < node.getChildCount(); i++) { |
---|
| 87 | lengths2Heights(node.getChild(i), newHeight); |
---|
| 88 | } |
---|
| 89 | } |
---|
| 90 | |
---|
| 91 | /** |
---|
| 92 | * Exchange field info between two nodes. Specifically |
---|
| 93 | * identifiers, branch lengths, node heights and branch length |
---|
| 94 | * SEs. |
---|
| 95 | */ |
---|
| 96 | public static void exchangeInfo(Node node1, Node node2) { |
---|
| 97 | |
---|
| 98 | Identifier swaps; |
---|
| 99 | double swapd; |
---|
| 100 | |
---|
| 101 | swaps = node1.getIdentifier(); |
---|
| 102 | node1.setIdentifier(node2.getIdentifier()); |
---|
| 103 | node2.setIdentifier(swaps); |
---|
| 104 | |
---|
| 105 | swapd = node1.getBranchLength(); |
---|
| 106 | node1.setBranchLength(node2.getBranchLength()); |
---|
| 107 | node2.setBranchLength(swapd); |
---|
| 108 | |
---|
| 109 | swapd = node1.getNodeHeight(); |
---|
| 110 | node1.setNodeHeight(node2.getNodeHeight()); |
---|
| 111 | node2.setNodeHeight(swapd); |
---|
| 112 | |
---|
| 113 | swapd = node1.getBranchLengthSE(); |
---|
| 114 | node1.setBranchLengthSE(node2.getBranchLengthSE()); |
---|
| 115 | node2.setBranchLengthSE(swapd); |
---|
| 116 | } |
---|
| 117 | |
---|
| 118 | |
---|
| 119 | |
---|
| 120 | |
---|
| 121 | /** |
---|
| 122 | * Get the distance to furthest leaf from this nodes parent. |
---|
| 123 | */ |
---|
| 124 | private static double getGreatestDistance(Node node) { |
---|
| 125 | |
---|
| 126 | double distance = 0.0; |
---|
| 127 | if (!node.isLeaf()) { |
---|
| 128 | if (!node.isRoot()) { |
---|
| 129 | distance = node.getBranchLength(); |
---|
| 130 | } |
---|
| 131 | double max = getGreatestDistance(node.getChild(0)); |
---|
| 132 | double posmax = 0.0; |
---|
| 133 | for (int i = 1; i < node.getChildCount(); i++) { |
---|
| 134 | posmax = getGreatestDistance(node.getChild(i)); |
---|
| 135 | if (posmax > max) max = posmax; |
---|
| 136 | } |
---|
| 137 | distance += max; |
---|
| 138 | |
---|
| 139 | return distance; |
---|
| 140 | } else { |
---|
| 141 | return node.getBranchLength(); |
---|
| 142 | } |
---|
| 143 | } |
---|
| 144 | |
---|
| 145 | /** |
---|
| 146 | * Finds the largest child (in terms of node height). |
---|
| 147 | */ |
---|
| 148 | public static double findLargestChild(Node node) { |
---|
| 149 | // find child with largest height |
---|
| 150 | double max = node.getChild(0).getNodeHeight(); |
---|
| 151 | for (int j = 1; j < node.getChildCount(); j++) |
---|
| 152 | { |
---|
| 153 | if (node.getChild(j).getNodeHeight() > max) |
---|
| 154 | { |
---|
| 155 | max = node.getChild(j).getNodeHeight(); |
---|
| 156 | } |
---|
| 157 | } |
---|
| 158 | return max; |
---|
| 159 | } |
---|
| 160 | |
---|
| 161 | /** |
---|
| 162 | * remove child |
---|
| 163 | * |
---|
| 164 | * @param node child node to be removed |
---|
| 165 | */ |
---|
| 166 | public static void removeChild(Node parent, Node child) |
---|
| 167 | { |
---|
| 168 | int rm = -1; |
---|
| 169 | for (int i = 0; i < parent.getChildCount(); i++) |
---|
| 170 | { |
---|
| 171 | if (child == parent.getChild(i)) |
---|
| 172 | { |
---|
| 173 | rm = i; |
---|
| 174 | break; |
---|
| 175 | } |
---|
| 176 | } |
---|
| 177 | |
---|
| 178 | parent.removeChild(rm); |
---|
| 179 | } |
---|
| 180 | |
---|
| 181 | /** |
---|
| 182 | * remove internal branch (collapse node with its parent) |
---|
| 183 | * |
---|
| 184 | * @param node node associated with internal branch |
---|
| 185 | */ |
---|
| 186 | public static void removeBranch(Node node) |
---|
| 187 | { |
---|
| 188 | if (node.isRoot() || node.isLeaf()) |
---|
| 189 | { |
---|
| 190 | throw new IllegalArgumentException("INTERNAL NODE REQUIRED (NOT ROOT)"); |
---|
| 191 | } |
---|
| 192 | |
---|
| 193 | Node parent = node.getParent(); |
---|
| 194 | |
---|
| 195 | // add childs of node to parent |
---|
| 196 | // (node still contains the link to childs |
---|
| 197 | // to allow later restoration) |
---|
| 198 | int numChilds = node.getChildCount(); |
---|
| 199 | for (int i = 0; i < numChilds; i++) |
---|
| 200 | { |
---|
| 201 | parent.addChild(node.getChild(i)); |
---|
| 202 | } |
---|
| 203 | |
---|
| 204 | // remove node from parent |
---|
| 205 | // (link to parent is restored and the |
---|
| 206 | // position is stored) |
---|
| 207 | int rm = -1; |
---|
| 208 | for (int i = 0; i < parent.getChildCount(); i++) |
---|
| 209 | { |
---|
| 210 | if (node == parent.getChild(i)) |
---|
| 211 | { |
---|
| 212 | rm = i; |
---|
| 213 | break; |
---|
| 214 | } |
---|
| 215 | } |
---|
| 216 | parent.removeChild(rm); |
---|
| 217 | node.setParent(parent); |
---|
| 218 | node.setNumber(rm); |
---|
| 219 | } |
---|
| 220 | |
---|
| 221 | /** |
---|
| 222 | * restore internal branch |
---|
| 223 | * |
---|
| 224 | * @param node node associated with internal branch |
---|
| 225 | */ |
---|
| 226 | public static void restoreBranch(Node node) |
---|
| 227 | { |
---|
| 228 | if (node.isRoot() || node.isLeaf()) |
---|
| 229 | { |
---|
| 230 | throw new IllegalArgumentException("INTERNAL NODE REQUIRED (NOT ROOT)"); |
---|
| 231 | } |
---|
| 232 | |
---|
| 233 | Node parent = node.getParent(); |
---|
| 234 | |
---|
| 235 | // remove childs of node from parent and make node their parent |
---|
| 236 | int numChilds = node.getChildCount(); |
---|
| 237 | for (int i = 0; i < numChilds; i++) |
---|
| 238 | { |
---|
| 239 | Node c = node.getChild(i); |
---|
| 240 | removeChild(parent, c); |
---|
| 241 | c.setParent(node); |
---|
| 242 | } |
---|
| 243 | |
---|
| 244 | // insert node into parent |
---|
| 245 | parent.insertChild(node, node.getNumber()); |
---|
| 246 | } |
---|
| 247 | |
---|
| 248 | |
---|
| 249 | |
---|
| 250 | /** |
---|
| 251 | * join two childs, introducing a new node/branch in the tree |
---|
| 252 | * that replaces the first child |
---|
| 253 | * |
---|
| 254 | * @param n1 number of first child |
---|
| 255 | * @param n2 number of second child |
---|
| 256 | */ |
---|
| 257 | public static void joinChilds(Node node, int n1, int n2) { |
---|
| 258 | |
---|
| 259 | if (n1 == n2) { |
---|
| 260 | throw new IllegalArgumentException("CHILDREN MUST BE DIFFERENT"); |
---|
| 261 | } |
---|
| 262 | |
---|
| 263 | int c1, c2; |
---|
| 264 | if (n2 < n1) |
---|
| 265 | { |
---|
| 266 | c1 = n2; |
---|
| 267 | c2 = n1; |
---|
| 268 | } |
---|
| 269 | else |
---|
| 270 | { |
---|
| 271 | c1 = n1; |
---|
| 272 | c2 = n2; |
---|
| 273 | } |
---|
| 274 | |
---|
| 275 | Node newNode = NodeFactory.createNode(); |
---|
| 276 | |
---|
| 277 | Node child1 = node.getChild(c1); |
---|
| 278 | Node child2 = node.getChild(c2); |
---|
| 279 | |
---|
| 280 | node.setChild(c1, newNode); |
---|
| 281 | newNode.setParent(node); |
---|
| 282 | node.removeChild(c2); // now parent of child2 = null |
---|
| 283 | |
---|
| 284 | newNode.addChild(child1); |
---|
| 285 | newNode.addChild(child2); |
---|
| 286 | } |
---|
| 287 | |
---|
| 288 | /** |
---|
| 289 | * determine preorder successor of this node |
---|
| 290 | * |
---|
| 291 | * @return next node |
---|
| 292 | */ |
---|
| 293 | public static Node preorderSuccessor(Node node) { |
---|
| 294 | |
---|
| 295 | Node next = null; |
---|
| 296 | |
---|
| 297 | if (node.isLeaf()) { |
---|
| 298 | Node cn = node, ln = null; // Current and last node |
---|
| 299 | |
---|
| 300 | // Go up |
---|
| 301 | do |
---|
| 302 | { |
---|
| 303 | if (cn.isRoot()) |
---|
| 304 | { |
---|
| 305 | next = cn; |
---|
| 306 | break; |
---|
| 307 | } |
---|
| 308 | ln = cn; |
---|
| 309 | cn = cn.getParent(); |
---|
| 310 | } |
---|
| 311 | while (cn.getChild(cn.getChildCount()-1) == ln); |
---|
| 312 | |
---|
| 313 | // Determine next node |
---|
| 314 | if (next == null) |
---|
| 315 | { |
---|
| 316 | // Go down one node |
---|
| 317 | for (int i = 0; i < cn.getChildCount()-1; i++) |
---|
| 318 | { |
---|
| 319 | if (cn.getChild(i) == ln) |
---|
| 320 | { |
---|
| 321 | next = cn.getChild(i+1); |
---|
| 322 | break; |
---|
| 323 | } |
---|
| 324 | } |
---|
| 325 | } |
---|
| 326 | } |
---|
| 327 | else |
---|
| 328 | { |
---|
| 329 | next = node.getChild(0); |
---|
| 330 | } |
---|
| 331 | |
---|
| 332 | return next; |
---|
| 333 | } |
---|
| 334 | |
---|
| 335 | /** |
---|
| 336 | * determine postorder successor of a node |
---|
| 337 | * |
---|
| 338 | * @return next node |
---|
| 339 | */ |
---|
| 340 | public static Node postorderSuccessor(Node node) { |
---|
| 341 | |
---|
| 342 | Node cn = null; |
---|
| 343 | Node parent = node.getParent(); |
---|
| 344 | |
---|
| 345 | if (node.isRoot()) |
---|
| 346 | { |
---|
| 347 | cn = node; |
---|
| 348 | } |
---|
| 349 | else |
---|
| 350 | { |
---|
| 351 | |
---|
| 352 | // Go up one node |
---|
| 353 | if (parent.getChild(parent.getChildCount()-1) == node) { |
---|
| 354 | return parent; |
---|
| 355 | } |
---|
| 356 | // Go down one node |
---|
| 357 | for (int i = 0; i < parent.getChildCount()-1; i++) |
---|
| 358 | { |
---|
| 359 | if (parent.getChild(i) == node) |
---|
| 360 | { |
---|
| 361 | cn = parent.getChild(i+1); |
---|
| 362 | break; |
---|
| 363 | } |
---|
| 364 | } |
---|
| 365 | } |
---|
| 366 | |
---|
| 367 | // Go down until leaf |
---|
| 368 | while (cn.getChildCount() > 0) |
---|
| 369 | { |
---|
| 370 | |
---|
| 371 | cn = cn.getChild(0); |
---|
| 372 | } |
---|
| 373 | |
---|
| 374 | return cn; |
---|
| 375 | } |
---|
| 376 | |
---|
| 377 | |
---|
| 378 | |
---|
| 379 | |
---|
| 380 | /** |
---|
| 381 | * Returns the first nodes in this tree that has the |
---|
| 382 | * required identifiers. |
---|
| 383 | * @return null if none of the identifiers names match nodes in tree, else return array which may have |
---|
| 384 | * null "blanks" for corresponding identifiers that do not match any node in the tree |
---|
| 385 | */ |
---|
| 386 | public static final Node[] findByIdentifier(Node node, String[] identifierNames) { |
---|
| 387 | Node[] nodes = new Node[identifierNames.length]; |
---|
| 388 | boolean foundSomething = false; |
---|
| 389 | for(int i = 0 ; i < nodes.length ; i++) { |
---|
| 390 | nodes[i] = findByIdentifier(node,identifierNames[i]); |
---|
| 391 | foundSomething = foundSomething||(nodes[i]!=null); |
---|
| 392 | } |
---|
| 393 | if(!foundSomething) { |
---|
| 394 | return null; |
---|
| 395 | } |
---|
| 396 | return nodes; |
---|
| 397 | } |
---|
| 398 | /** |
---|
| 399 | * Returns the first nodes in this tree that has the |
---|
| 400 | * required identifiers. |
---|
| 401 | */ |
---|
| 402 | public static final Node[] findByIdentifier(Node node, Identifier[] identifiers) { |
---|
| 403 | Node[] nodes = new Node[identifiers.length]; |
---|
| 404 | for(int i = 0 ; i < nodes.length ; i++) { |
---|
| 405 | nodes[i] = findByIdentifier(node,identifiers[i]); |
---|
| 406 | } |
---|
| 407 | return nodes; |
---|
| 408 | } |
---|
| 409 | /** |
---|
| 410 | * Returns the first node in this tree that has the |
---|
| 411 | * required identifier. |
---|
| 412 | */ |
---|
| 413 | public static final Node findByIdentifier(Node node, Identifier identifier) { |
---|
| 414 | return findByIdentifier(node,identifier.getName()); |
---|
| 415 | } |
---|
| 416 | /** |
---|
| 417 | * Returns the first node in this tree that has the |
---|
| 418 | * required identifier. |
---|
| 419 | */ |
---|
| 420 | public static final Node findByIdentifier(Node node, String identifierName) { |
---|
| 421 | |
---|
| 422 | |
---|
| 423 | if (node.getIdentifier().getName().equals(identifierName)) { |
---|
| 424 | return node; |
---|
| 425 | } else { |
---|
| 426 | Node pos = null; |
---|
| 427 | for (int i = 0; i < node.getChildCount(); i++) { |
---|
| 428 | pos = findByIdentifier(node.getChild(i), identifierName); |
---|
| 429 | if (pos != null) return pos; |
---|
| 430 | } |
---|
| 431 | |
---|
| 432 | return pos; |
---|
| 433 | } |
---|
| 434 | } |
---|
| 435 | |
---|
| 436 | /** |
---|
| 437 | * Root tree at this node. |
---|
| 438 | */ |
---|
| 439 | public static Node root(Node node) { |
---|
| 440 | |
---|
| 441 | if (!node.isRoot()) { |
---|
| 442 | |
---|
| 443 | Node myParent = node.getParent(); |
---|
| 444 | removeChild(myParent, node); |
---|
| 445 | |
---|
| 446 | root(myParent); |
---|
| 447 | |
---|
| 448 | while (myParent.getChildCount() == 1) { |
---|
| 449 | myParent = myParent.getChild(0); |
---|
| 450 | } |
---|
| 451 | |
---|
| 452 | node.addChild(myParent); |
---|
| 453 | lengths2Heights(node); |
---|
| 454 | } |
---|
| 455 | return node; |
---|
| 456 | } |
---|
| 457 | |
---|
| 458 | /** |
---|
| 459 | * Root the tree above the node with this identifier. |
---|
| 460 | */ |
---|
| 461 | public static Node rootAbove(Identifier id, Node root) { |
---|
| 462 | return rootAbove(findByIdentifier(root, id)); |
---|
| 463 | } |
---|
| 464 | |
---|
| 465 | /** |
---|
| 466 | * Root tree above this node; |
---|
| 467 | */ |
---|
| 468 | public static Node rootAbove(Node node) { |
---|
| 469 | |
---|
| 470 | if (!node.isRoot()) { |
---|
| 471 | |
---|
| 472 | Node root = NodeFactory.createNode(); |
---|
| 473 | |
---|
| 474 | Node myParent = node.getParent(); |
---|
| 475 | removeChild(myParent, node); |
---|
| 476 | |
---|
| 477 | root(myParent); |
---|
| 478 | |
---|
| 479 | while (myParent.getChildCount() == 1) { |
---|
| 480 | myParent = myParent.getChild(0); |
---|
| 481 | } |
---|
| 482 | |
---|
| 483 | root.addChild(myParent); |
---|
| 484 | root.addChild(node); |
---|
| 485 | |
---|
| 486 | lengths2Heights(root); |
---|
| 487 | |
---|
| 488 | return root; |
---|
| 489 | |
---|
| 490 | } else return node; |
---|
| 491 | } |
---|
| 492 | |
---|
| 493 | /** |
---|
| 494 | * determine distance to root |
---|
| 495 | * |
---|
| 496 | * @return distance to root |
---|
| 497 | */ |
---|
| 498 | public static double getDistanceToRoot(Node node) |
---|
| 499 | { |
---|
| 500 | if (node.isRoot()) |
---|
| 501 | { |
---|
| 502 | return 0.0; |
---|
| 503 | } |
---|
| 504 | else |
---|
| 505 | { |
---|
| 506 | return node.getBranchLength() + getDistanceToRoot(node.getParent()); |
---|
| 507 | } |
---|
| 508 | } |
---|
| 509 | |
---|
| 510 | /** |
---|
| 511 | * Return the number of terminal leaves below this node or 1 if this is |
---|
| 512 | * a terminal leaf. |
---|
| 513 | */ |
---|
| 514 | public static int getLeafCount(Node node) { |
---|
| 515 | |
---|
| 516 | int count = 0; |
---|
| 517 | if (!node.isLeaf()) { |
---|
| 518 | for (int i = 0; i < node.getChildCount(); i++) { |
---|
| 519 | count += getLeafCount(node.getChild(i)); |
---|
| 520 | } |
---|
| 521 | } else { |
---|
| 522 | count = 1; |
---|
| 523 | } |
---|
| 524 | return count; |
---|
| 525 | } |
---|
| 526 | /** |
---|
| 527 | * For two nodes in the tree true if the first node is the ancestor of the second |
---|
| 528 | * |
---|
| 529 | * @param possibleAncestor the node that may be the ancestor of the other node |
---|
| 530 | * @param node the node that may have the other node as it's ancestor |
---|
| 531 | */ |
---|
| 532 | public static boolean isAncestor(Node possibleAncestor, Node node) { |
---|
| 533 | if(node==possibleAncestor) { |
---|
| 534 | return true; |
---|
| 535 | } |
---|
| 536 | while(!node.isRoot()){ |
---|
| 537 | node = node.getParent(); |
---|
| 538 | if(node==possibleAncestor) { |
---|
| 539 | return true; |
---|
| 540 | } |
---|
| 541 | } |
---|
| 542 | return false; |
---|
| 543 | } |
---|
| 544 | |
---|
| 545 | /** |
---|
| 546 | * For a set of nodes in the tree returns the common ancestor closest to all nodes (most recent common ancestor) |
---|
| 547 | * |
---|
| 548 | * @param nodes the nodes to check, is okay if array elements are null! |
---|
| 549 | * @returns null if a at least one node is disjoint from the others nodes disjoint |
---|
| 550 | */ |
---|
| 551 | public static Node getFirstCommonAncestor(Node[] nodes) { |
---|
| 552 | Node currentCA = nodes[0]; |
---|
| 553 | for(int i = 1; i < nodes.length ;i++) { |
---|
| 554 | if(currentCA!=null&&nodes[i]!=null) { |
---|
| 555 | currentCA = getFirstCommonAncestor(currentCA,nodes[i]); |
---|
| 556 | if(currentCA==null) { |
---|
| 557 | return null; |
---|
| 558 | } |
---|
| 559 | } |
---|
| 560 | } |
---|
| 561 | return currentCA; |
---|
| 562 | } |
---|
| 563 | /** |
---|
| 564 | * For two nodes in the tree returns the common ancestor closest to both nodes (most recent common ancestor) |
---|
| 565 | * |
---|
| 566 | * @param nodeOne |
---|
| 567 | * @param nodeTwo |
---|
| 568 | * @returns null if two nodes disjoint (from different trees). May also return either nodeOne or nodeTwo if one node is an ancestor of the other |
---|
| 569 | */ |
---|
| 570 | public static Node getFirstCommonAncestor(Node nodeOne, Node nodeTwo) { |
---|
| 571 | if(isAncestor(nodeTwo, nodeOne)) { |
---|
| 572 | return nodeTwo; |
---|
| 573 | } |
---|
| 574 | if(isAncestor(nodeOne, nodeTwo)) { |
---|
| 575 | return nodeOne; |
---|
| 576 | } |
---|
| 577 | while(!nodeTwo.isRoot()) { |
---|
| 578 | nodeTwo = nodeTwo.getParent(); |
---|
| 579 | if(isAncestor(nodeTwo, nodeOne)) { |
---|
| 580 | return nodeTwo; |
---|
| 581 | } |
---|
| 582 | } |
---|
| 583 | return null; |
---|
| 584 | } |
---|
| 585 | |
---|
| 586 | /** returns number of branches centered around an internal node in an unrooted tree */ |
---|
| 587 | public static final int getUnrootedBranchCount(Node center) { |
---|
| 588 | if (center.isRoot()) { |
---|
| 589 | return center.getChildCount(); |
---|
| 590 | } |
---|
| 591 | else { |
---|
| 592 | return center.getChildCount()+1; |
---|
| 593 | } |
---|
| 594 | } |
---|
| 595 | |
---|
| 596 | /** Attempts to remove the root of a tree by making it polyficating (as opposed to bificating). |
---|
| 597 | */ |
---|
| 598 | public static final Node getUnrooted(Node root) { |
---|
| 599 | if(!root.isRoot()) { |
---|
| 600 | return root; //Already unrooted |
---|
| 601 | } |
---|
| 602 | Node left = root.getChild(0); |
---|
| 603 | Node right = root.getChild(1); |
---|
| 604 | /*if(left.getChildCount()==1) { |
---|
| 605 | if(l |
---|
| 606 | } */ |
---|
| 607 | if(left.getChildCount()>1) { |
---|
| 608 | return root(left); |
---|
| 609 | } |
---|
| 610 | if(right.getChildCount()>1) { |
---|
| 611 | return root(right); |
---|
| 612 | } |
---|
| 613 | return root; //Can't do much |
---|
| 614 | } |
---|
| 615 | } |
---|