What is this algorithm? Create a tree's equivalent hierarchical network This question was originally posted here: https://stackoverflow.com/q/20735339/2305618

I am surely not the first to have implemented code to perform the following graph transformation. But try as I might, I can't find a previous reference to it. 

The transformation arises when creating a single graph that simultaneously models hierarchical inclusion relationships and other pairwise relationships between nodes.

The algorithm transforms a rooted directed tree DAG into an equivalent hierarchical network DAG. Equivalence in this sense - if the meaning of the tree structure is that parents 'consist of' or 'contain' their children the equivalent network structure would carry the same 'consisting of' or 'containment' information.

The tree hierarchy is represented in the network as sub-networks and sub-sub-networks. The tree's exterior nodes are copied across and each interior node X is represented by the pair: X' and X''

Does anyone know the name/reference of this transformation/ algorithm? :-)

Illustration image of this transformation:


Thanks

David
Your question contains the implicit assumption/premise that this transformation has a name.  I don't know why you would expect it to have a special name.  The transformation is not anything special or complicated and as far as I know it does not have any special name.  It appears that you are just taking a tree, and making a second copy of it (with all edges reversed; with all nodes cloned), and then just gluing the two copies together (identifying both copies of each leaf). 

For future reference, I don't think questions like "please tell me if this function has a special name" are a good fit for this site.  This site is for technical questions that admit an objectively evaluable answer and that relate to a real problem you have.  How do you expect to evaluate an answer that says "No, it doesn't have a special name"?  There is no reference one can cite to back up that answer, and no objectively verifiable evidence one can provide to support such an answer.  Moreover, questions about naming aren't a very good fit.  How will knowing whether there is a special name help  you solve a real problem?  (If you were thinking "it might help me find references that help me solve problem X", then you would be better off by just describing problem X.)