I may have misunderstood our question, but there are several programs that can reroot a tree, as shown in our figures, e.g. FigTree, Geneious and Mesquite

If you have a good data structure for string the tree, this should be simple. Many data structures are possible. I remember that I saw one proposed in the book "Inferring phylogenies" by J.Felsenstein. A diffucult point is to assign the correct bootstrap values to all branches. Several widely used programs have done this in a wrong way over years. The important point is: The bootstrap value is a property of the branch and not a property of the node. If you save the bootstrap value as a property of the node and assign it to the branch coming from the root to the node, the value will be wrong if you reroot the tree.

You can post hoc re-root the tree in almost any tree viewing program (FigTree, Mega, SeaView, Ape/Phangorn in R, etc.) and save the rooted version of the tree to a file. Most phylogenetic inference software also allow you to declare an outgroup taxon or taxa as part of the inference. RAxML, for example, allows you to specifiy an outgroup through a flag and the name of the taxon. You can also add more separated by commas. If all OGs are monophyletic, the entire group will be the OG. If they are not it will walk back towards the first listed until all are monophyletic and place the root there.

Do I understand this correlty: I are a software developer and whan to implement this feature in your own program? Or do you search for a program that can do this?

Thank you all for the answers.  

Svante and Christoph, yes many programs including Mega will root the tree, but I want to implement this feature in a program that we are writing.  Sorry for not making this clear.  Christoph, I will look at the data structure suggested by Felsentein, but I would still need an algorithm...by the way, thanks for the note about bootstrapping - you are right.

Matthew, yes, Mega and other programs can post-hoc root the tree, but when I export a Newick formatted tree, it is already rooted and these programs (at least Mega) then disables the rooting tool.  That is why I want to implement a way to root the tree in my program.  What would also work is if there ways to export an unrooted tree so that post-hoc rooting can be done.  I am not aware of ways of doing this.

That is very kind of you, Jan De Laet.  Thank you very much.  I'm not sure I got the second subroutine but I will consult with my associate.  Thanks again!

Have you tried looking at the source for programs (like Figtree) which have already implemented this? 

Anyways, it is hard to suggest an algorithm without knowing more about your current implementation of a tree and its data structure, but I've attached some Java-style pseudocode which demonstrates one way to do it. 

The code includes pseudocode for a class RootedTree, where the root is considered to be an arbitrary branch from within the tree. In order to keep track of a "branch", I have two member variables giving the two nodes connected by that edge (forming the right and left sides of the tree- ingroup and outgroup). Each side of the tree is the root node (class Node) of a non-binary tree (allowing polytomies to be represented if you want- you could easily make it binary instead) And also note that in this implementation, the root will be drawn as a bifurcation- so you can't make a polytomy root (you could also change this if you want but it makes the code more messy so I did it this way). 

class RootedTree{

    Node right;

    Node left;

        rerootTree(Node newRight, Node newLeft){

            newRight.reroot(newRight, newLeft, this.left, null);

            newLeft.reroot(newLeft, newRight, this.right, null);

            //Not invoking copy constructor, but copying object address

            this.right = newRight;

            this.left = newLeft;

        }

}

Within each Node object, we track 1) The parent Node (in the case of the root node, this is null); 2) a LinkedList of child Nodes (this is what makes it non-binary); and 3) some data (I show this as class Data- this would include any annotations you want, branch lengths, support values, a taxon name if this is a terminal node).

So, getting to the re-rooting algorithm. I assume that your program has the ability to detect a branch that the user wishes to re-root the tree with, and that you can provide the Node objects connected by this branch. These are inputs to the rerootTree function. Remember that we are representing out phylogeny as two non-binary trees which make up each side of the root. To perform the re-rooting, we will first call Node.reroot() on each of our Nodes which are adjacent to the branch which we are rooting on. The function takes the inputs: new root (for this side of tree), previous root (for OTHER side of tree), and new parent node (NULL for root node).

Within this function we follow this progression: 1) If this.parent is not null (meaning current Node is not a previous root), we push this.parent into our list of children. We then recursively traverse "up" the tree by calling the same function on this.parent. 2) If the current Node is the PREVIOUS root, we assign the other side of the tree as a child (push otherRoot into this.Children), and assign ourselves as the parent of that node. 3) If we are not the previous root, than our new parent is the node which invoked the reroot() function for us. 

class Node{

    Node parent

    LinkedList Children

    Data dat //Assuming you have some information to store, branch length etc

        reroot(Node newRoot, Node otherNewRoot, Node oldRoot, Node newParent){

            if (this.parent == otherNewRoot){

                this.parent = null;

                return 0;

            }

            while (this.parent != null){ //Null if previous root

                Children.add(new Node(this.parent));

                this.parent.reroot(newRoot, oldRoot, this);

            }

            if (this.parent == null){

                oldRoot.parent = this;

                this.Children.add(new Node(oldRoot));

            }else{

                this.parent = newParent;

            }

      }

}

If you are not familiar with recursion, this can be really confusing. Basically what we do is start at the new root node (for one side of the target re-rooted tree), traverse UP (recursively call reroot for our parent, or set our parent to null if our parent is the base node on the other side of the new rooted branch), until we reach the previous root (which had parent == null). When we hit the OLD "root" node, we re-incorporate the other side of the (old rooted) tree, and then traverse back DOWN from there, re-assigning each Node.parent to the child which invoked its reroot function when we were traversing UP the tree in the recursive part. 

Hopefully that makes sense. Of course I have not tested any of this, so I can't guarantee that it works- and you will need to fill in many parts (for example in my pseudocode I assume the presence of constructors, etc)... Let me know if you need any clarification.  

Jan and Tyler, you guys have been very generous.  Thanks!  I believe we are making some progress based on your suggestions.  Will let you know!  Thanks again.

Check out Newick utils: https://github.com/tjunier/newick_utils. It's a set of command-line tools, one of which is nw_reroot. The package can also be used as a python module: https://github.com/tjunier/newick_utils/blob/614bf6c686b02b5970f1f47eb5642fea5616c4f5/src/nw_reroot.py

Hmm, this looks like it can bypass the graphical rearranging of the tree.  Thanks, Andrey.  Will definitely look into it.

 You can also use figtree software

http://tree.bio.ed.ac.uk/software/figtree/  

Thank you, Ibrahim, but as I mentioned earlier, I want to implement the feature into my program, and so am looking for an easy algorithm to implement.  I realize that a number of programs have already implemented a rooting feature, but that doesn't help me unless I know how they coded it.

For those programs which have already implemented this (like figtree), you can easily investigate how they coded it. For example, the source code for FigTree can be found here: https://github.com/rambaut/figtree

Same goes for any other functions you might want to implement. You can always check out the source code for open source projects. Just be sure that if you use code from another project, that you check how that code was licensed, e.g. under the GNU Public License, code can be used for any non-commercial purpose, as long as the resulting product is also licensed under the GPL (thus also freely distributable and open).