Method rootTreeAtCenter

src/figtree/treeviewer/ReRootedTree.java:609–660

Root any tree by locating the "center" of tree and adding a new root node at that point for any point on the tree x let D(x) = Max{distance between x and t : for all tips t} The "center" c is the point with the smallest distance, i.e. D(c) = min{ D(x) : x in tree } @param tree to root @return

(RootedTree tree)

     * @return rooted tree
     */
    public static RootedTree rootTreeAtCenter(RootedTree tree) {
        // Method - find the pair of tips with the longest distance. It is easy to see that the center
        // is at the midpoint of the path between them.

        HashMap<HashPair<Node>, Double> dists = new LinkedHashMap<HashPair<Node>, Double>();
        try {
            double maxDistance = -Double.MAX_VALUE;
            // node on maximal path
            Node current = null;
            // next node on maximal path
            Node direction = null;

            // locate one terminal node of longest path
            for (Node e : tree.getExternalNodes()) {
                for (Node n : tree.getAdjacencies(e)) {
                    final double d = dist(tree, e, n, dists);
                    if (d > maxDistance) {
                        maxDistance = d;
                        current = e;
                        direction = n;
                    }
                }
            }

            // traverse along maximal path to it's middle
            double distanceLeft = maxDistance / 2.0;

            while (true) {
                final double len = tree.getEdgeLength(current, direction);
                if (distanceLeft <= len) {
                    //System.out.println(toNewick(rtree));
                    return new ReRootedTree(tree, current, direction, distanceLeft);
                }
                distanceLeft -= len;

                maxDistance = -Double.MAX_VALUE;
                Node next = null;
                for (Node n : tree.getAdjacencies(direction)) {
                    if (n == current) continue;
                    final double d = dist(tree, direction, n, dists);
                    if (d > maxDistance) {
                        maxDistance = d;
                        next = n;
                    }
                }
                current = direction;
                direction = next;
            }
        } catch (Graph.NoEdgeException e1) {
            return null; // serious bug, should not happen
        }
    }

    private static double dist(Tree tree, Node root, Node node, Map<HashPair<Node>, Double> dists) throws Graph.NoEdgeException {
        HashPair<Node> p = new HashPair<Node>(root, node);